Table of Contents

Last modified on January 31st, 2024

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.

It is done in two steps:

**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.**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.

Let us assume a recursive sequence f_{n} given by f_{1} = 1, f_{2} = 2, f_{3} = 6, and f_{n} = (n^{3} – 3n^{2} + 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} = 1 (given) = 1!, which is true.

For n = 2, f_{2} = 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} – 3(k + 1)^{2} + 2(k + 1)] f_{(k + 1) – 3}

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

= [k^{3} – 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!

**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)