The method of proof ‘by mathematical induction’ is based on the following principle:

Principle of mathematical induction

Let there be associated, with each positive integer n, a proposition P(n), which is either true or false. If

1. (i) P(1) is true,

2. (ii) for all k, P(k) implies P(k + 1),

then P(n) is true for all positive integers n.

The following are typical of results that can be proved by induction:

1. (a) For all positive integers n, ${\displaystyle \sum _{r=1}^n}{r}^2=\frac{1}{6}n(n+1)(2n+1)$.

2. (b) For all positive integers n, the nth derivative of $\frac{1}{x}$ is ${\left(-1\right)}^n\frac{n!}{x^{n+1}}.$

3. (c) For all positive integers n, (cosθ‎ + i sinθ‎)ⁿ = cosnθ‎+i sinnθ‎. See De Moivre’s Theorem.

In each case, it is clear what the proposition P(n) should be and that (i), the base case, can be verified. The method by which the so‐called inductive step (ii), where the inductive hypothesis P(k) is assumed, is proved depends upon the particular result to be established.

There is a so-called ‘strong form’ of the principle of induction which is equivalent. It states:

If

1. (i’) P(1) is true,

2. (ii’) for all k, the truth of P(1), P(2), …, P(k–1), P(k) implies P(k + 1),

then P(n) is true for all positive integers n.

This is a useful alternative when the inductive step proving P(k + 1) relies on the truth of some previous proposition P(i) which is not necessarily P(k).