Strong Induction

Strong mathematical induction takes the principle of induction a step further by allowing us to assume that the statement holds not only for all natural numbers ‘n ≥1’ but also for (n + 1) or (n+1)th iteration. Thus, it differs from mathematical induction in the inductive step. 

Principle

It is done in two steps:

1. Base Step: It is the same as in weak mathematical induction, proving whether a statement is true for the initial value (n), usually the smallest natural number.
2. Inductive Step: It proves that when the statement is true for the number n (or n^th iteration) and all the values before n, then it is also true for the number (n + 1) (or (n+1)^th iteration.

Proof

Let us assume a recursive sequence f_n given by f₁ = 1, f₂ = 2, f₃ = 6, and f_n = (n³ – 3n² + 2n)f_n-3, for all n ≥ 4. 

Using strong induction, let us prove the statement: For all the natural numbers, n, f_n = n!

For the initial value, n = 1, f₁ = 1 (given) = 1!, which is true.

For n = 2, f₂ = 2 = 2!, which is also true.

Assuming the statement is true for 1 ≤ i ≤ k, f_i = i!

Now, we have to prove that the statement is also true for n = k + 1, and since 1 ≤ k – 2 ≤ k, we get f_{k – 2} = (k – 2)! and

f_{k + 1} = [(k + 1)³ – 3(k + 1)² + 2(k + 1)] f_{(k + 1) – 3}

= [k³ + 3k² + 3k + 1 – 3k² – 6k – 3 + 2k + 2] f_{k – 2}

= [k³ – k] (k – 2)!

= k(k + 1)(k – 1)(k – 2)!

= (k+1)!, which is true.

Thus, f_n = n! for all the natural numbers n.

Hence, the method of strong induction proves the given statement: For all the natural numbers, n, f_n = n!

Solved Examples

Using strong mathematical induction, show that every natural number (n ≥ 8) can be written as the sum of 3s and 5s.

Solution:

For n = 8, n is written as 8 = 3 + 5, which is true.
Now, assuming the value 8 ≤ n ≤ k, each of the numbers 8, …, k can be written as the sum of 3s and 5s.
We have to prove the statement for n = k + 1. Since 1 ≤ k – 2 ≤ k (k – 2 can be written as the sum of 3’s and 5’s).
k + 1 = (k – 2) + 3, the sum of 3s and 5s.
Thus, every number (n ≥ 8) can be written as the sum of 3s and 5s.

Using the method of strong induction, prove that for all (n ≥ 2), 2(n – 1) – (n – 2) = n.

Solution:

For n = 2, 2(2 – 1) – (2 – 2) = 4 – 2 = 2, which is true.
Similarly, for the value 2 ≤ n ≤ k, the given statement is also true, that is, 2(n – 1) – (n – 2) = n
Now, we have to prove the statement for n = k + 1, and since 1 ≤ k ≤ k + 1, we get 2(k – 1) – (k – 2) = k
Here, 2[(k + 1) – 1] – [(k + 1) – 2]
= 2(k – 1 + 1) – (k – 2 + 1)
= 2(k – 1) + 2 – (k – 2) – 1
= 2(k – 1) – (k – 2) + 1
= k + 1, which proves the given statement is true for n = k + 1
Thus, 2(n – 1) – (n – 2) = n for all the natural numbers (n ≥ 2)