# 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 for`k+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.