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
- Base Cases: Identify multiple smallest possible cases for which the statement is true.
- Induction Hypothesis: Suppose that the statement is true for some integer
k
, then the statement must be true fork+1
. - 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) = kThen 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+1Thus, the statement is true at x = k+1.
Looking to contribute?
- Learn more about how to get involved.
- Edit this page on GitHub to fix an error or make an improvement.
- Submit feedback to let us know how we can improve Docs.