# Proof by Strong Induction

Published Aug 23, 2023Updated May 15, 2024
Contribute to Docs

Proof by strong induction is a mathematical technique for proving universal generalizations. It differs from ordinary mathematical induction (also known as weak mathematical induction) with respect to the inductive step.

In a weak mathematical induction, the inductive step involves showing that if some element n has a property, then the successor element n + 1 must also have that property. In a strong mathematical induction, the inductive step involves showing that if all elements up to and including n have some property, then n + 1 has that property as well.

## Steps for Strong Induction

1. Base Step: Prove that the first element or elements in the series have some property.
2. Inductive Step: Prove that if n and all elements before n have the relevant property, then n + 1 has that property.

## Example

The following proposition will be proven by strong induction:

```For all x such that x ≥ 2, 2(x-1) - (x-2) = x.
```

Base Step:

The first element is where x = 2. Therefore, it must be shown that 2(x - 1) - (x - 2) = x, where x = 2:

```2(2 - 1) - (2 - 2) = 2(1) - (0) = 2 - 0 = 2Both sides are equal to 2. Thus, the statement is true at x = 2.
```

Inductive Step:

In the inductive step, it must be shown that if, for any value x between 2 and k (inclusive), 2(x - 1) - (x - 2) = x, then at x = k + 1, 2(x - 1) - (x - 2) = x.

This conditional will be proven by assuming the antecedent (this assumption is called the inductive hypothesis) and showing the consequent:

```Inductive Hypothesis: Suppose that for all x such that 2 ≤ x ≤ k, 2(x - 1) - (x - 2) = x.To be proven: 2((k + 1) - 1) - ((k + 1) - 2) = k + 1.
First, we will rearrange the left-hand of the expression above: 2((k + 1) - 1) - ((k + 1) - 2) = 2(k + 1 - 1) - (k + 1 - 2) [removing extra parentheses]           = 2(k - 1 + 1) - (k - 2 + 1) [rearranging within parentheses]           = 2(k - 1) + 2 - (k - 2 + 1) [factoring 2 into the left parenthesis]           = 2(k - 1) + 2 - (k - 2) - 1 [rearranging the right parenthesis]           = 2(k - 1) - (k - 2) + 1  [adding numerical terms]
Now, by the Inductive Hypothesis, 2(k - 1) - (k - 2) = k. We therefore substitute 'k' for '2(k-1) - (k-2)' in the rearranged expression above: 2((k + 1) - 1) - ((k + 1) - 2) = k + 1    [substitution from Inductive Hypothesis]
Having shown that 2((k + 1) - 1) - ((k + 1) - 2) = k + 1, this completes the inductive step and the proof.
```

Although the example above uses strong mathematical induction, the same strategy could be applied using weak mathematical induction, since the only value of the inductive hypothesis used was at x = k (there was no need to use any values smaller than k).

## The Logic of Strong Induction

Why do the base step and the inductive step together demonstrate the truth of a universal generalization?

The base step shows that the first n elements in the series have the relevant property. Since all the elements prior to the element at n + 1 have the property, it then follows by the inductive step that the element at n + 1 also has the property. Similarly, since all elements prior to the element at n + 2 have the property, the inductive step shows that the element at n + 2 does as well. Since this can be done indefinitely, the entire series is shown to have the relevant property.