Glossary: Proof by induction

Proof by induction

Proof by induction, or proof by mathematical induction, is a method of proving statements or results that depend on a positive integer n. The result is first shown to be true for n = 1. Next comes the induction step: the result is shown to be true for all successive positive integers by proving the statement for an arbitrary n, assuming it holds for the case (n 1). The assumption that the statement holds for the case (n 1) is called the induction hypothesis.

Example: we prove De Moivre’s theorem using induction:

We want to prove that, for all positive integers n,


Step 1: case n = 1

Trivially, . So the result holds for n = 1.

Step 2: arbitrary n

We assume the induction hypothesis, that is, we assume


Now we have


using the compound angle formulae. This proves the induction step, so by the principle of mathematical induction,


for all positive integers, n.