Proof by Strong Induction

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.