discrete mathematics chapter 4 mathematical induction

Even though this proposition may have an infinite number of cases, I shall give a very short proof of it assuming two lemmas. The first, which is self evident, is that the proposition is valid for the second row. The second is that if the proposition is valid for any row then it must necessarily be valid for the following row. From this it can be seen that it is necessarily valid for all rows; for it is valid for the second row by the first lemma; then by the second lemma it must be true for the third row and hence for the fourth row and so on to infinity. —Pascal

The Principle of Mathematical Induction: The statement
$$
begin{equation}
forall n in Bbb N, P(n): text{for every positive integer}; n, P(n).
end{equation}
$$
is true if (1)$P(1)$ is true and (2)the statement $forall k in Bbb N, P(k) ⇒ P(k+1)$ is true.

Induction Proof: a proof (often of statements of the type $forall n in Bbb N, P(n)$) using the Principle of Mathematical Induction or the Strong Principle of Mathematical Induction.

Base: or basis step, anchor, the step in an induction proof that establishes the truth of a statement for a specific value, which is the first step of an induction proof.

Inductive hypothesis, or induction hypothesis, the hypothesis of the implication in the inductive step of an induction proof, which is the second step of an induction proof.

Inductive step: the step in an induction proof that establishes the truth of a certain required statement expressed as an implication.

Example of using this induction principle:
$$
text{
For every positive integer $n$, 1 + 2 + … + $n$ = $n(n+1)over2$.
}
$$
Proof:
$$
begin{align}
text{Base}:&; 1 = {1(1+1)over 2} \
text{Hypothesis}:&; 1 + 2 + 3 + … + k = {k(k+1)over2 }; text{for a positive integer $k = n ge 1$} \
text{Step}:&; text{for $n=k+1$,}; 1 + 2 + 3 + … + (k+1) = {(k+1)(k+2)over2} \
&= 1 + 2 + 3 + … + (k+1) = (1+2+3 + … + k) + (k+1) \
&= {k(k+1)over2} + (k+1) = {k(k+1)+2(k+1)over2} \
&= {(k+1)(k+2)over2}. □
end{align}
$$

The Principle of Mathematical Induction: For a fixed integer $m$, let $S = lbrace i in Bbb Z: i ge m rbrace$. Then the statement
$$
text{
$forall n in S, P(n)$: For evert integer $n ge m$, $P(n)$.
}
$$
is true if (1)$P(1)$ is true and (2)the statement $forall k in Bbb N, P(k) ⇒ P(k+1)$ is true.

Example of using this induction principle:
$$
text{
For every positive integer $n$, $2^n > n$.
}
$$
Proof:
$$
begin{align}
text{Base}:&; 2^1 > 1 \
text{Hypothesis}:&; 2^k > k; text{for a positive integer $k = n ge 1$} \
text{Step}:&; text{for $k = n + 1$},; 2^{k+1} = 2 times 2^k > 2k = k+k ge k+1 \
& ⇒ 2^{k+1} > k+1 ⇒ 2^n > n; text{for every positive integer $n$}. □
end{align}
$$

Sequence: a listing (finite or infinite) of elements of some set.

Geometric sequence: a sequence $lbrace a_n rbrace$ in which the ratio of every two consecutive terms $a_n$ and $a_{n+1}$ is some constant $r$, that is, ${a_{n+1}over a_n} = r$. For example, $lbrace 2, 4, 8, 16, 32, …, 2^n, 2^{n+1} rbrace$ is a geometric sequence.

Arithmetic sequence: a sequence $lbrace a_n rbrace$ in which the difference of every two consecutive terms $a_n$ and $a_{n+1}$ is some constant $k$, that is, $a_{n+1} - a_n = k$. For example, $lbrace 3, 5, 7, 9, 11, 13, …, n, n+2 rbrace$ is an arithmetic sequence.

String: a finite sequence.

length: the number of terms in the string.

Bit: or binary digit, is a 0 or 1.

Bit string: a finite sequence of 0s and 1s.

Recursively defined sequence: a sequence defined in terms of initial values and a recurrence relation.

Initial value: some specified values for a recursively defined sequence.

Recurrence relation: a relation that defines $a_n (n in Bbb N)$ in terms of $a_1, a_2, …, a_{n-1}$, where the sequence $lbrace a_n rbrace$ is defined recursively.

Fibonacci Numbers: $F_n: F_1 = 1, F_2 = 1$ and $F_n = F_{n-2} + F_{n-1}$ for $n ge 3$.

Example of proof of Fibonacci sequence:
$$
text{
For every integer $n ge 2$, $F_{n-1}F_{n+1}$ = $F^2_n + (-1)^2$.
}
$$
Proof:
$$
begin{align}
text{Base}:&; n = 2 ⇒ F_1F_3 = 1 times 2 = 1^2 + 1 = F^2_2 + (-1)^2 = 2 \
text{Hypothesis}:&; F_{k-1}F_{k+1} = F^2_k + (-1)^k; text{for $n = k ge 2$} \
text{Step}:&; text{for some $n=k+1$},; F_{k}F_{k+2} = F_k(F_k + F_{k+1}) = F^2_k + F_kF_{k+1} \
&= [F_{k-1}F_{k+1} - (-1)^k] + F_kF_{k+1} \
&= F_{k-1}F_{k+1} + F_kF_{k+1} + (-1)^{k+1} \
&= (F_{k-1} + F_k)F_{k+1} + (-1)^{k+1} \
&= F_{k+1}F_{k+1} + (-1)^{k+1} \
&= F^2_{k+1} + (-1)^{k+1}. □
end{align}
$$

The Strong Principle of Mathematical Induction (1): The statement
$$
text{
$forall n in Bbb N, P(n)$: for every positive integer $n, P(n)$.
}
$$
is true if (1) $P(1)$ is true and (2) the statement $forall k in Bbb N, P(1) ∧ P(2) ∧ … ∧ P(k) ⇒ P(k+1)$ is true.

Example of proof by the strong principle of mathematical induction (1):
$$
text{
If {$a_n$} is a sequence defined recursively by
}
$$

$$
text{
$a_1 = 3$ and $a_n = 2a_{n-1} + 1$
}
$$

$$
text{
for $n ge 2$, then $a_n = 2^{n+1} - 1$ for every positive integer $n$.
}
$$

Proof:
$$
begin{align}
text{Base}:&; a_1 = 2^{1+1} - 1 = 3 \
text{Hypothesis}:&; a_k = 2^{k+1} - 1; text{for a positive integer $k = n ge 3$} \
text{Step}:&; text{for k = n + 1},; a_{k+1} = 2^{(k+1)+1} - 1 = 2^{k+2}-1 \
&= 2a_k + 1 = 2(2^{k+1}- 1)+1 = 2^{k+2} - 1 = 2^{n+1}-1. □
end{align}
$$
The Strong Principle of Mathematical Induction (2): For a fixed integer $m$, let $S = lbrace i in Bbb Z: i ge m rbrace$. Then the statement
$$
text{
$forall n in S, P(n)$: For every integer $n ge m, P(n)$.
}
$$
is true if (1)$P(m)$ is true and (2)the statement $forall k in S, P(m) ∧ P(m+1) ∧ … ∧ P(k) ⇒ P(k+1)$ is true.