A good informal analogy of mathematical induction is a line of up-ended dominos - if you can show that both of the following are true:

- If
**any**one of the dominos fall, then the next domino will also fall - The first domino must fall

then you can say with certainty that **all the dominos will fall**.

The "line of dominos" here is in fact some sequence of mathematical statements. For example, to assert the truth of the binomial theorem:

is to assert the truth of each item of the sequence:

and so on. So if you can:

- Show that
**IF**the \(k\)th item in the sequence is true, then the \(k + 1\)th case must also be true **AND**show that the first item in the sequence is true (when \(n = 0\))

then it can be said that the proposed theorem is true for all \(n \in \mathbb{N} \).

## Strong Induction

The two parts of an Inductive proof are the **base case** and the **inductive
step**. The base case is, as stated, the proof of the given statement for the
first item in the sequence - typically when \(n = 0\) but, in general, when
\(n\) is some lowest positive integer. And the inductive step is the assumption
of the \(k\)th case and the subsequent proof of the \(k+1\)th case.

It may be the case that assumption of the \(k\)th case is insufficient in
achieving the inductive step, and so invoking **strong induction** is called
for. With strong induction you assume, not just the \(k\)th case, but each case
up to and including the \(k\)th.

see also: | Wikipedia, NRICH, The Method of Descent, proofwiki.org |
---|