Induction underpins much of mathematics, and allows us to prove infinite families of statements in a finite number of steps.
More specifically, we have a statement \(P(n)\) about the whole number \(n\), and we want to prove that \(P(n)\) is true for every value of \(n\). To prove this using induction, we do the following:
The base case. We prove that \(P(1)\) is true (or occasionally \(P(0)\) or some other \(P(n)\), depending on the problem).
The induction step. We prove that if \(P(k)\) is true, then \(P(k+1)\) must also be true. In this step, \(P(k)\) is called the inductive hypothesis.
Together, these imply that \(P(n)\) is true for all whole numbers \(n\).
(For if it is not, there must be a smallest \(n\) for which \(P(n)\) is false, say \(n=n_0\). We cannot have \(n_0=1\) as \(P(1)\) is true by step 1. And as \(P(n_0-1)\) is true, \(P(n_0)\) must be true by step 2, contradicting our assumption that \(P(n_0)\) is false.)
See also strong induction for a closely related proof technique.
