Proof:Strong induction is equivalent to weak induction

From CS2800 wiki

You may think that strong induction is stronger than weak induction in the sense that you can prove more things using strong induction than you could using only weak induction (the names certainly suggest that!). In fact, this is false: you can systematically convert a proof by strong induction to a proof by weak induction by strengthening the inductive hypothesis. Here is a formal statement of this fact:

Suppose you know the following:
  1. You can prove [math]P(0) [/math]
  2. You can prove [math]P(n+1) [/math] for an arbitrary [math]n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Natural_number}{\mathbb{N}} [/math], assuming [math]P(k) [/math] for all [math]k \leq n [/math],
Then you can conclude [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Natural_number}{\mathbb{N}}, P(n) [/math], using only the basic weak induction principle.
Assume the statements that are given in the claim. Let [math]Q(n) [/math] be the statement "for all [math]k \leq n [/math], P(k)." We will show [math]Q(0) [/math] and [math]Q(n+1) [/math] for an arbitrary [math]n \geq 0 [/math], assuming [math]Q(n) [/math].


To see [math]Q(0) [/math], we want to show that for any [math]k \leq 0 [/math], [math]P(k) [/math] holds. But the only [math]k \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Natural_number}{\mathbb{N}} [/math] that is less than or equal to 0 is [math]k = 0 [/math]. The first assumption given in the claim is that [math]P(0) [/math] holds, so [math]P(k) [/math] holds for all [math]k \leq 0 [/math], and thus [math]Q(0) [/math] holds.


Now we will prove [math]Q(n+1) [/math], assuming [math]Q(n) [/math]. So we want to show that for all [math]k \leq n+1 [/math], that [math]P(k) [/math] holds. Choose an arbitrary [math]k \leq n+1 [/math]. There are two cases to consider:

  • if [math]k \lt n+1 [/math], then [math]k \leq n [/math]. Thus we can apply [math]Q(n) [/math] to conclude [math]P(k) [/math].
  • the only remaining case is [math]k = n+1 [/math]. In this case, [math]Q(n) [/math] gives us [math]P(0) [/math], [math]P(1) [/math], [math]P(2) [/math], ..., [math]P(n) [/math]. Thus we can use the second proof given in the assumptions to conclude [math]P(n+1) [/math], which is the same as [math]P(k) [/math].
This completes the weak induction proof that [math]\forall n, Q(n) [/math]. We can then use this to prove the actual claim (that [math]\forall n, P(n) [/math]) as follows: choose an arbitrary [math]n \href{/cs2800/wiki/index.php/%5Cin}{\in} \mathbb{N} [/math]; we want to show [math]P(n) [/math]. We know [math]Q(n) [/math] is true, so for every [math]k \leq n, P(k) [/math] holds. In particular, for [math]k = n [/math], we can conclude [math]P(k) [/math], which is the same thing as [math]P(n) [/math]. Thus [math]P(n) [/math] is true.