# 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) = 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+1
Thus, the statement is true at x = k+1.
```