Strong mathematical induction is a variant of mathematical induction that makes the induction step easier to prove by using a stronger hypothesis, additionally it also usually includes multiple base cases instead of a single one. Strong induction is most useful when several instances of the inductive hypothesis are required for each induction step.

A proof by strong induction consists of two cases. The first called the base case, proves the predicate for where and natural numbers and where . The second step called the induction step then proves that if the predicate holds for for all natural numbers from to , where then it must also hold for .

The two steps in the proof (the base case and the induction step) establish that the predicate holds for for all natural numbers greater than or equal to the lower bound of the base case proving where is the base case chosen earlier.

Example

Statement to Prove

Given that is the fibonacci number defined as , for every natural number greater than 1, with and .

For all natural numbers such that

Where , and .

Hint: and , as and are both solutions to .

Base Cases

let

Since both sides are equal the base case holds for .

let

Since both sides are equal the base case holds for as well.

Inductive Step

Consider the arbitrary natural number , where .

Assume that the the formula holds for every arbitrary natural number , i.e., assume:

This is called the inductive hypothesis.

We need to prove that the formula also holds for , i.e.,

Starting on the left side we can replace the and with our inductive hypothesis.

Combining the fractions on the left side

Moving around the terms in the numerator on the left side

Factoring on the left side

Substituting using the hint that and the left becomes

Multiplying the terms on the left side we get

As both sides are now equivalent the hypothesis can be concluded for and therefore for all naturals greater than or equal to .