How to Write an Induction Proof

A row of dominoes#

Stand a long row of dominoes on end. You want every single one to fall over. You cannot push them one at a time, because there are infinitely many.

So we check two things instead:

1. Knock the first one over.
2. Make sure each domino is close enough to hit the one after it.

Those two facts together guarantee the whole row falls, and you never had to check them individually. The first one falls because you pushed it. The second falls because the first hit it. The third falls because the second hit it — and so on forever.

That is proof by induction, entirely. Everything below is the same two checks written in a form a grader will accept.

What P(n) means, and why you write it down first#

Induction proves a statement that is really infinitely many statements — one for each whole number. We write P(n) for “the statement, with the number n in it”. That is one domino.

If the claim is the first n whole numbers add up to n(n+1)/2, then P(3) is the specific sentence “1 + 2 + 3 = 3·4/2”. P(4) is a different sentence. There is one for every n, which is exactly why you cannot check them one at a time.

Before doing anything else, write the sentence “Let P(n) be ___” and fill in an actual statement — an equation, an inequality, a divisibility claim. Most of the marks lost in this topic are lost in the first two lines, not the last two. Once P(n) is written down, the other two things you need are just substitutions:

That last row is where the algebra errors start. In a sum formula, n appears twice — as the last number you add, and inside the formula on the right. Both of them change.

The skeleton to copy every time#

Copy this shape every time. The labels are not decoration; a grader looks for them, and the proof reads as unfinished without them.

Four labelled parts. If one is missing, the proof is incomplete even when every line of algebra is perfect.

One word in there is load-bearing: arbitrary. It means you picked a k but assumed nothing special about it, so whatever you prove holds for every k. That is what turns one argument into infinitely many.

Worked example — a sum#

Claim. For all n ≥ 1,   1³ + 2³ + ⋯ + n³ = [n(n+1)/2]².

Let P(n) be that equation.

Basis step. P(1) says 1³ = [1·2/2]². The left side is 1. The right side is 1² = 1. They agree, so P(1) holds. First domino down.

Inductive step. Let k ≥ 1 and assume P(k):

1³ + 2³ + ⋯ + k³ = [k(k+1)/2]²

We must reach P(k+1):

1³ + 2³ + ⋯ + k³ + (k+1)³ = [(k+1)(k+2)/2]²

Start from the left side of P(k+1) and peel off the last term. This is the move that lets the assumption in — and it is the only clever step in the whole proof:

1³ + ⋯ + k³ + (k+1)³
= [k(k+1)/2]² + (k+1)³   (this is where P(k) gets used)
= k²(k+1)²/4 + (k+1)³
= (k+1)²[ k²/4 + (k+1) ]   (factor out (k+1)²)
= (k+1)² · (k² + 4k + 4)/4
= (k+1)²(k+2)²/4
= [(k+1)(k+2)/2]²

That is exactly the right side of P(k+1). So P(k) → P(k+1). Each domino hits the next. By induction the formula holds for all n ≥ 1. ∎

Worked example — a divisibility claim#

Claim. For all n ≥ 0,   3 divides n³ − n.

Let P(n) be “3 divides n³ − n”.

Basis step. P(0): 0³ − 0 = 0, and 3 divides 0. Holds.

Inductive step. Assume P(k). Here is the habit that makes this work: turn the word “divides” into an equation. “3 divides k³ − k” means k³ − k = 3m for some whole number m. An equation can be substituted; a word cannot.

(k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1
= (k³ − k) + 3k² + 3k
= 3m + 3(k² + k)   (P(k) used here)
= 3(m + k² + k)

Since m + k² + k is a whole number, 3 divides (k+1)³ − (k+1). So P(k) → P(k+1). ∎

The mistake that costs the most#

If your inductive step never uses the assumption, you did not write an induction proof — you proved P(k+1) from scratch, and the whole structure was theatre.

Check it directly: point at the line where P(k) enters. In the sum above it is the line marked “this is where P(k) gets used”. In the divisibility one it is where 3m replaced k³ − k. If you cannot point at such a line, the proof is broken however tidy the algebra looks.

Where the first domino goes#

The basis step looks like the trivial part. It is not — it is the push that starts everything, and without it a chain of perfectly good dominoes just stands there.

Here is a claim with a flawless inductive step and no basis step: the first n whole numbers add up to (n² + n + 2)/2. Assume it for k, add k+1, and the algebra goes through cleanly. But P(1) says 1 = 2, which is false — so the formula is wrong for every n. The inductive step only ever says “if one domino falls, the next one does”. If none of them ever falls, that is still true and completely useless.

And check where the first domino actually stands. The inequality 2ⁿ > n² is false at n = 2, 3 and 4, and first becomes true at n = 5. So the proof starts at n = 5, and the inductive step only needs to work for k ≥ 5.

Where these go wrong#

• Never using the assumption. The defining error. Point at the line where P(k) enters.
• Assuming P(k+1). Circular. You assume P(k), and only P(k).
• Substituting k+1 in only some places. Every n changes, including inside the formula on the right.
• Skipping the basis step. Cheap to write, fatal to leave out — the (n² + n + 2)/2 example above is exactly what it costs.
• Starting at the wrong number. Check where the claim first becomes true. For 2ⁿ > n² that is n = 5, not n = 1.
• Leaving a divisibility assumption as words. Turn “3 divides k³ − k” into “k³ − k = 3m” so you can substitute it.
• Stopping before the target. The step ends when your expression matches the right side of P(k+1) exactly. Write that target down first so you know when you have arrived.
• Forgetting the word “arbitrary”. It is what makes one argument cover every number.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.