Proof:Weak induction principle starting at k is equivalent to weak induction

From CS2800 wiki

Suppose you have an inductive proof in the following style:

To prove [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \geq k, P(n) [/math] using weak induction, you can prove [math]P(k) [/math] and prove [math]P(n+1) [/math] for an arbitrary [math]n \geq k [/math], assuming [math]P(n) [/math].

But you are only willing to accept the basic weak induction principle:

To prove "[math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \href{/cs2800/wiki/index.php/%5Cin}{\in} \mathbb{N},P(n) [/math]" using weak induction, you must prove [math]P(0) [/math] (this is often called the base case), and then you must prove [math]P(n+1) [/math] for an arbitrary [math]n [/math], assuming [math]P(n) [/math] (this is called the inductive step).

You can systematically convert from the first style to the second:

Suppose you know the following:
  1. [math]P(k) [/math]
  2. [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \geq k, P(n) [/math] implies [math]P(n+1) [/math]
Then you can conclude [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \geq k, P(n) [/math], using only the basic weak induction principle.

We actually give two different proofs:

Proof: Using vacuous truth
We will assume that [math]k \gt 0 [/math], because if [math]k = 0 [/math] then the two inductive principles are identical.


Assume the statements that are given in the claim. Let [math]\href{/cs2800/wiki/index.php/Inductive_hypothesis}{Q(n)} [/math] be the statement "if [math]n \geq k [/math] then [math]P(n) [/math]." 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].


[math]Q(0) [/math] is vacuously true, since [math]0 \ngeq k [/math].

Now choose an arbitrary [math]n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Natural_number}{\mathbb{N}} [/math], and assume [math]Q(n) [/math]; we will show [math]Q(n+1) [/math], i.e. that if [math]n+1 \geq k [/math] then [math]P(n+1) [/math]. Assume that [math]n+1 \geq k [/math]; we want to show [math]P(n+1) [/math]. There are two cases to consider:

  • if [math]n+1 = k [/math], then we will use assumption 1 that is given in the claim. We are given [math]P(k) = P(n+1) [/math].
  • on the other hand, if [math]n+1 \gt k [/math] then [math]n \geq k [/math]. This means we can apply [math]Q(n) [/math] to conclude [math]P(n) [/math]. Now we know [math]n \geq k [/math] and [math]P(n) [/math] so we can apply the second assumption given in the claim to conclude [math]P(n+1) [/math].


This concludes the inductive proof that [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}}, Q(n) [/math]. This means that [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}} [/math], if [math]n \geq k [/math] then [math]P(n) [/math]. This is just another way of saying [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \geq k, P(n) [/math], which is what we were trying to prove.

Here is the second proof, which uses the fact that [math]n \geq k [/math] is the same as [math]n -k \geq 0 [/math]:

Proof: By changing variables
Assume the statements that are given in the claim. Let [math]\href{/cs2800/wiki/index.php/Inductive_hypothesis}{Q(n)} := P(n+k) [/math]. 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].

[math]Q(0) [/math] is the same as [math]P(0+k) = P(k) [/math]; the first assumption in the claim is [math]P(k) [/math], so we are done.

Now, choose an arbitrary [math]n \geq 0 [/math]; we want to show [math]Q(n+1) [/math], assuming [math]Q(n) [/math]. In other words, we want to show [math]P(n+k+1) [/math] assuming [math]P(n+k) [/math]. Since [math]n \geq 0 [/math], we have [math]n+k \geq k [/math]. Thus we can apply the second assumption from the claim to conclude that if [math]P(n+k) [/math] holds then [math]P(n+k+1) [/math] holds, and since we know [math]P(n+k) [/math] holds, we can conclude that [math]P(n+k+1) [/math] holds. But this is the same thing as saying that [math]Q(n+1) [/math] holds.

This concludes the weak induction proof that for all [math]n [/math], [math]Q(n) [/math]. Now, to show the original claim (that for all [math]n \geq k, P(n) [/math] holds), we choose an arbitrary [math]n \geq k [/math]; we will show that [math]P(n) [/math] holds. Since [math]n \geq k [/math], we have [math]n - k \geq 0 [/math], so [math]Q(n-k) [/math] holds. But [math]Q(n-k) = P(n-k+k) = P(n) [/math] so [math]P(n) [/math] holds, as required.