Or search by topic
Published 2011 Revised 2018
Have you ever played that game with dominoes where you line them up on end and then, by knocking over the first one, knock over the whole lot? You can think of proof by induction as the mathematical equivalent (although it does involve infinitely many dominoes!).
Suppose that we have a statement $P(n)$, and that we want to show that it's true for all $n$. So in our example above, $P(n)$ is: $$\sum_{i=1}^n i^2 = \frac{1}{6}n(n+1) (2n+1)$$ Think of each $P(n)$ as a domino. If we can show that $P(1)$ is true (that is, we can knock over the first domino)and that if $P(n)$ is true then so is $P(n+1)$ (knocking over one domino means the next one will also
fall over), do you agree that we've then shown that $P(n)$ is true for all $n\geq 1$ (because all of the dominoes will fall over)?

We'll know that $P(1)$ is true,
so we'll know that $P(1+1)=P(2)$ is true,
so we'll know that $P(2+1)=P(3)$ is true,
so we'll know that $P(3+1)=P(4)$ is true,
$\ldots$
You get the idea.
