Proof by Induction

A proof by induction proves a statement is true for every whole number n — not just a few — using just two steps:

the base case — show the statement is true for n = 1;
the inductive step — assume it is true for n = k, and show it then follows for n = k + 1.

Picture a line of dominoes. The base case pushes the first one over. The inductive step guarantees that whenever a domino falls it knocks over the next. Put those two together and every domino falls — the statement holds for all n \ge 1.

Worked example

Claim: for every whole number n \ge 1,

1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.

Base case (n = 1). The left-hand side is just 1. The right-hand side is

\frac{1(1+1)}{2} = \frac{1 \times 2}{2} = 1. \quad\checkmark

So the formula is true for n = 1.

Inductive step. Assume it is true for n = k — that is, assume

1 + 2 + \cdots + k = \frac{k(k+1)}{2}.

Now add the next term, k + 1, to both sides and simplify the right:

1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.

That last expression is exactly the formula with n = k + 1: replacing n by k + 1 in \frac{n(n+1)}{2} gives \frac{(k+1)(k+2)}{2}. So truth at k forces truth at k + 1. With the base case, the dominoes all fall — the formula holds for every n \ge 1.

To prove a statement for all whole numbers n \ge 1:

base case — show it is true for n = 1;
inductive step — assume it is true for n = k and prove it is then true for n = k + 1;
together these prove it for all n \ge 1;
state your assumption clearly, and aim to manipulate it into the k + 1 form.