How to Write an Induction Proof

Induction is the most template-driven proof you will ever write. The mathematics varies; the skeleton does not. Learn the skeleton and the only hard part left is the algebra.

The skeleton

Copy this shape every time. The labels are not decoration — a grader is looking for them, and the proof reads as incomplete without them.

Four labeled parts. If any is missing, the proof is incomplete even when the algebra is perfect.

Say what P(n) is before you start

Most of the credit lost in this topic is lost in the first two lines, not the last two. Before anything else, write the sentence "Let P(n) be the statement ___" and fill it in with an actual statement — an equation, an inequality, a divisibility claim. Then P(k) and P(k+1) are just substitutions into that sentence, and you can produce them without thinking.

That last parenthetical is where the algebra errors start. In a summation formula, n appears both as the top index of the sum and inside the right-hand expression. Both change.

Worked example: a summation

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.

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

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

We must show P(k+1):

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

Start from the left side of P(k+1) and split off the last term — this is the move that lets the hypothesis in:

1³ + ⋯ + k³ + (k+1)³ = [k(k+1)/2]² + (k+1)³   (by the inductive hypothesis)

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

Conclusion. 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 | (n³ − n)".

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

Inductive step. Assume P(k): k³ − k = 3m for some integer m. Consider

(k+1)³ − (k+1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3k² + 3k = 3m + 3(k² + k) = 3(m + k² + k).

Since m + k² + k is an integer, 3 divides (k+1)³ − (k+1). So P(k) → P(k+1). ∎

Two habits are doing the work here. The hypothesis was written as an equation — k³ − k = 3m — rather than left as the word "divides", which makes it substitutable. And the expansion was rearranged to expose the (k³ − k) chunk instead of being simplified into an unrecognizable polynomial. Look for the previous case inside the new one; it is almost always there.

The mistake that costs the most

Proving P(k+1) directly, without ever using P(k).

If your inductive step never substitutes the hypothesis, you have not proved P(k) → P(k+1); you have proved P(k+1) on its own, and the assumption was decoration. Sometimes that even works out — some claims really are provable directly — but it is not an induction, and it is marked as one.

The check takes five seconds: point at the line where the inductive hypothesis was used. In the summation proof it is the substitution of [k(k+1)/2]². In the divisibility proof it is replacing k³ − k with 3m. If you cannot point at such a line, the proof is not finished.

The mirror-image error is assuming P(k+1) — assuming what you are trying to show. A proof that starts "assume 1³ + ⋯ + (k+1)³ = [(k+1)(k+2)/2]²" has assumed its own conclusion. Assume P(k). Show P(k+1).

Where the basis case actually goes

The starting value is whatever the claim says, and it is not always 1. The inequality 2ⁿ > n² is false at n = 2, 3, and 4, and first becomes true at n = 5 — so a proof of it must begin at n = 5, and the inductive step only needs to work for k ≥ 5. Checking n = 1 there proves nothing about the chain you actually want.

Skipping the basis is not a formality either. Consider "1 + 2 + ⋯ + n = (n² + n + 2)/2". Its inductive step is completely valid — assume it at k, add k+1, and the algebra genuinely produces the formula at k+1. But the basis fails: at n = 1 the right side is 2, not 1. The chain is sound and anchored to nothing, so the claim is false for every n. An induction with no basis proves exactly as much as a row of dominoes nobody pushed.

The famous illustration runs the other way. The "all horses are the same color" argument has a fine basis — one horse is the same color as itself — and an inductive step that splits k+1 horses into two overlapping groups of k. That step is valid for every k ≥ 2. At k = 1 the two groups are single horses with no overlap, so nothing connects them, and one broken link breaks the whole chain. The lesson is that "the inductive step works" means it works at every k from the basis up, small cases included.

Where these go wrong

• Never using the hypothesis. The defining error. Point at the line where P(k) enters.
• Assuming P(k+1). Circular. The assumption is P(k) and only P(k).
• Substituting k+1 in only some places. Every occurrence of n changes, including inside the closed form on the right.
• Omitting the basis step. Cheap to write, fatal to skip — and the "(n² + n + 2)/2" example above is exactly what it costs.
• Starting at the wrong n. Check where the claim actually first holds. For 2ⁿ > n² that is n = 5, not n = 1.
• Leaving a divisibility hypothesis in words. Turn "3 | (k³ − k)" into "k³ − k = 3m for some integer m" so it can be substituted.
• Stopping before the target. The inductive 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.
• Not saying "arbitrary". The k in the inductive step is a fixed but arbitrary integer ≥ n₀. That word is what makes the conclusion universal.

Frequently asked questions