Proof by Strong Induction

Published Aug 23, 2023
Contribute to Docs

Proof by Strong Induction is an induction technique that proves a statement by providing multiple base cases, assuming the statement is true for all integers from the largest base case to some even larger integer k, and then proving the statement is true for k+1 using that assumption.

Steps for Strong Induction

  1. Base Cases: Identify multiple smallest possible cases for which the statement is true.
  2. Induction Hypothesis: Suppose that the statement is true for some integer k, then the statement must be true for k+1.
  3. Proof: Prove that the induction hypothesis is true for k+1.

Example

Statement: 2(x-1) - (x-2) = x for x >= 2

Base Cases:

At x = 2 , 2(2 - 1) - (2 - 2) = 2(1) - (0) = 2 + 0 = 2 and x = 2. Thus, the statement is true at x = 2.
At x = 3, 2(3 - 1) - (3 - 2) = 2(2) - (1) = 4 - 1 = 3 and x = 3. Thus, the statement is true at x = 3.

Induction Hypothesis:

Suppose at x = k, 2(k-1) - (k-2) = k
Then at x = k+1, prove that 2((k+1)-1) - ((k+1)-2) = k+1

Proof:

2((k+1)-1) - ((k+1)-2) = 2(k+1-1) - (k+1-2)
= 2(k-1+1) - (k-2+1)
= 2(k-1) + 2(1) - (k-2) -(+1)
= 2(k-1) - (k-2) + 2 - 1
= 2(k-1) - (k-2) + 1
= k + 1 [Substituting from x = k, which states that 2(k-1) - (k-2) = k]
2((k+1)-1) - ((k+1)-2) = k+1
Thus, the statement is true at x = k+1.

All contributors

Looking to contribute?

Learn Discrete Math on Codecademy