Last modified on January 31st, 2024

chapter outline

 

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’, for example, for (n + 1) or (n+1)th iteration. It thus differs from the 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 nth 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 fn given by f1 = 1, f2 = 2, f3 = 6, and fn = (n3 – 3n2 + 2n)fn-3, for all n ≥ 4. 

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

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

For n = 2, f2 = 2 = 2!, which is also true.

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

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

fk + 1 = [(k + 1)3 – 3(k + 1)2 + 2(k + 1)] f(k + 1) – 3

= [k3 + 3k2 + 3k + 1 – 3k2 – 6k – 3 + 2k + 2] fk – 2

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

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

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

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

Hence, the method of strong induction proves the given statement: For all the natural numbers, n, fn = 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)

Comments are closed.