Proof by Induction
Suppose you want to prove something is true for every positive whole number
— for n = 1, and n = 2, and
n = 1{,}000{,}000, and every number after that, forever. You can
never check them one by one: there are infinitely many. So how can a finite argument
pin down an infinite list of cases?
Picture a long line of dominoes, stretching off further than you can see. You
want to be sure all of them fall. You don't need to push each one. You only need
two things to be true:
- the first domino falls;
- whenever a domino falls, it knocks over the next one.
Put those together and the conclusion is unstoppable: the first falls, so the second falls, so
the third falls… and every domino in the whole infinite line goes down. That is exactly
proof by induction — the domino principle made rigorous.
The method: two steps
A proof by induction proves a statement P(n) for every whole number
n \ge 1 using precisely two steps:
-
the base case — show P(1) is true (push the
first domino over);
-
the inductive step — assume P(k) is true
for some k (this assumption is called the
induction hypothesis), and use it to show P(k+1)
must then be true too (each falling domino knocks the next).
If both steps succeed, you may conclude that P(n)
holds for all n \ge 1. The base case starts the
chain; the inductive step carries it forward one rung at a time, forever.
Worked example 1 — a sum formula
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 — the first domino falls.
Inductive step. Assume it is true for n = k — that
is, assume the induction hypothesis
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.
Seeing it — two staircases make a rectangle
Induction proves the sum formula, but here is why it is true, as a picture (for
n = 5). First a staircase of
1 + 2 + 3 + 4 + 5 squares. Then flip a second copy upside down and
slot it in: the two staircases interlock into a perfect rectangle,
5 wide and 6 tall. One staircase is
exactly half of 5 \times 6 — that is
\frac{n(n+1)}{2}.
Worked example 2 — a divisibility result
Induction isn't only for sums. Claim: for every whole number
n \ge 1, the number 5^n - 1 is
divisible by 4.
Base case (n = 1):
5^1 - 1 = 4, which is divisible by 4.
\checkmark
Inductive step. Assume 5^k - 1 is divisible by
4 — say 5^k - 1 = 4m for some whole number
m. Look at the next case:
5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(5^k - 1) + (5 - 1) = 5(4m) + 4 = 4(5m + 1).
The result is 4 times a whole number, so
5^{k+1} - 1 is divisible by 4 as well.
Base case plus inductive step: it holds for all n \ge 1. Notice how
the trick was to peel off a copy of 5^k - 1 so the induction
hypothesis could do its job.
Worked example 3 — the odd numbers
Add up the first few odd numbers and something magical happens:
1 = 1, 1 + 3 = 4,
1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16. Perfect
squares! Claim: the sum of the first n odd numbers
is n^2:
1 + 3 + 5 + \cdots + (2n - 1) = n^2.
Base case: for n = 1 the sum is
1 = 1^2. \checkmark
Inductive step: assume
1 + 3 + \cdots + (2k - 1) = k^2. The next odd number is
2(k+1) - 1 = 2k + 1, so
1 + 3 + \cdots + (2k - 1) + (2k + 1) = k^2 + (2k + 1) = (k + 1)^2.
which is the claim for n = k + 1. The chain is complete.
To prove a statement P(n) for all whole numbers
n \ge 1:
-
base case — show P(1) is true;
-
inductive step — assume P(k) (the induction
hypothesis) and prove P(k+1) follows;
-
together these prove P(n) for all
n \ge 1;
-
state your assumption clearly, and aim to manipulate it into the
k + 1 form.
The two steps are a team; drop either one and the proof collapses.
-
No base case? Then no domino is ever pushed, so none fall — even if
each would knock the next. You can build a perfectly valid inductive step for a
false statement. Take “n = n + 1”: if
k = k + 1 then adding 1 gives
k + 1 = k + 2, so the step “works”. But it is nonsense,
because the base case is false and the chain never starts. Always check the base
case.
-
Didn't use the assumption? The inductive step must actually use the
induction hypothesis P(k) to reach P(k+1)
— that is the link between one domino and the next. If your working for
k + 1 never mentions the k case, you have
just re-proved a single case, not built a chain.
-
Assuming what you want to prove. The hypothesis is “true for
this k” — one domino — not “true for all
n”. Assuming the whole claim up front is circular and proves
nothing.
That is the quiet wonder of induction: two short paragraphs settle infinitely many cases at
once. And the same “knock the first, guarantee each knocks the next” idea —
recursion, or self-reference — shows up all over the place once you spot it.
-
Computer loops and recursion. A program that repeats a step until it's done
is running an inductive argument. Proving a loop is correct means checking it's right the
first time round (base case) and that each pass keeps it right (inductive step) — programmers
call this a loop invariant.
-
Fractals. A shape like the Koch snowflake is defined by “start with a
triangle, then replace every edge with a smaller kinked copy, forever.” Base case plus a
repeated rule — building infinite detail from a finite recipe.
-
Anything with a “next step”. Whenever a structure is built one
rung at a time, induction is the natural way to reason about all of it. It is one of the most
powerful tools a mathematician owns.
See it explained