# Induction

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:

1. The base case. We prove that $P(1)$ is true (or occasionally $P(0)$ or some other $P(n)$, depending on the problem).

2. 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.)