The following two principles of mathematical induction are equivalent:
|
The Principle of Mathematical Induction (i.e., Regular Induction).
|
|
The (Second) Principle of Mathematical Induction (i.e., Strong Induction).
|
Proof:
For the following arguments, suppose $n$ is some integer greater than or equal to $1$.
Also, let us denote some statement about $n$ by $P(n)$.
If strong induction holds, then regular induction holds...
"$P(n)$ is true whenever $n \le k$" certainly implies "$P(k)$ is true", since $k \le k$.
Therefore, whenever $(*)$ is true, $(**)$ is true.
To see this, suppose $(*)$ is true.
If "$P(k)$ is true whenever $k \le n$" is true, then $P(n)$ is true when $n=k$, and by $(*)$ we have $P(n)$ true when $n=k+1$. This verifies $(**)$.
Now suppose strong induction holds.
Then by our earlier argument, If the hypotheses (1) and (2) for regular induction are met, then the hypotheses (1) and (2) for strong induction are met. [Note: hypothesis (1) is the same in both cases.]
We can conclude, via strong induction, that the statement holds for all positive integers $n$, but this is the exact same conclusion that regular induction would have.
Thus, regular induction will hold whenever strong induction holds.
If induction holds, then strong induction holds...
Let us assume that for statement $P(n)$, hypotheses (1) and (2) for strong induction have been met.
Let $Q(k)$ be the statement "$P(n)$ is true for all $n \le k$".
We will attempt to prove the statement $Q(n)$ is true for all positive integers $n$ by regular induction, which will then tell us that $P(n)$ is true for all positive integers $n$ (the same conclusion strong induction applied to $P(n)$ would make).
Since we have assumed $P(1)$ is true, it must also be the case that $Q(1)$ is true. This establishes the basis step (1) for our regular induction argument.
We have also assumed that hypothesis (2) for strong induction on $P(n)$ was met, so if "$P(n)$ is true for all $n \le k$" then "$P(k+1)$ will be true.
Saying the same thing another way: if $Q(k)$ is true, then $P(k+1)$ is true.
However, $P(k+1)$ being true, in combination with $Q(k)$ being true, implies $Q(k+1)$ is true.
So if $Q(k)$ is true, then $Q(k+1)$ must also be true. This establishes the inductive step (2) of our regular induction argument.
We have satisfied they hypotheses (1) and (2) for regular induction with regard to statement $Q(n)$, so $Q(n)$ must be true for all positive integers $n$.
But then, $P(n)$ must also be true for all positive integers $n$.
This is the same conclusion that strong induction would make regarding $P(n)$, so strong induction holds, so strong induction will hold whenever induction holds