Recipe

Prove a statement by mathematical induction

Use when: you're asked to prove a statement $P(n)$ true for every integer $n$ from some fixed starting point $n_0$ onward, and testing every case individually is impossible

Goal: a complete proof that $P(n)$ holds for every integer $n \ge n_0$ , resting on exactly two checked facts

Taught in The induction principle

Quick recipe

State the claim $P(n)$
Verify the base case(s)
State the inductive hypothesis
Prove the inductive step
State the conclusion

1
Write down exactly what you're proving, as a statement about an arbitrary integer $n$ , and identify the smallest value $n_0$ where it's supposed to start being true.

Example

For "every integer $n \ge 1$ satisfies $n < 2^n$ ," $P(n)$ is the statement " $n < 2^n$ ," and $n_0 = 1$ .

Why: an imprecise $P(n)$ makes every later step ambiguous. You can't check whether $P(1)$ holds until you've pinned down exactly what $P(n)$ says.
2
Plug $n = n_0$ directly into $P(n)$ and confirm it's true by direct computation. This is arithmetic, not algebra.

Example

$P(1)$ for " $n < 2^n$ ": is $1 < 2^1$ ? Yes, $1 < 2$ , so $P(1)$ holds.

Why: the base case is the one confirmed link the whole chain hangs from. A flawless inductive step proves nothing if $P(n_0)$ is false. That's exactly the situation in "A flawless inductive step with no base case" above, where the step never breaks yet the claim is false for every $n$ .
3
Assume $P(k)$ is true for one arbitrary, but fixed and unspecified, integer $k \ge n_0$ .
- the inductive step (Step 4) only ever needs the single previous case $P(k)$ — assume just $P(k)$ ; ordinary induction is enough.
- the inductive step needs an earlier case that isn't necessarily $k$ itself, or more than one earlier case at once — assume every case from $n_0$ through $k$ is true; switch to strong induction.
Why: this is the "if" half of the domino chain. Assuming one arbitrary, fixed $k$ , never " $P(n)$ for every $n$ ," is what keeps the argument from being circular. See "A common point of confusion" above.
4
Starting from the inductive hypothesis, derive $P(k+1)$ using ordinary algebra or logic. This is the step where the real work happens, and it must go through for every $k$ , using nothing specific to any one number.

Example

For the postage-stamp problem ("every integer $\ge 8$ is $3a+5b$ for nonnegative integers $a,b$ "), the strong hypothesis gives $k - 2 = 3a + 5b$ for some nonnegative $a, b$ , since $8 \le k-2 \le k$ . Adding one more 3-cent stamp: $k+1 = (k-2)+3 = 3(a+1)+5b$ , which is exactly $P(k+1)$ .

Why: this is the load-bearing link, the guarantee that ties an arbitrary fallen domino to the very next one, proven once for every $k$ instead of domino by domino.
5
Write the closing sentence explicitly: the base case holds, and the inductive step holds for every $k \ge n_0$ ; therefore, by the Principle of (Strong) Induction, $P(n)$ holds for every integer $n \ge n_0$ .

Why: naming the principle by name is what licenses the jump from two checked facts to a claim about infinitely many integers. The proof isn't finished until this sentence is written down.

Common mistakes

Treating the inductive hypothesis as assuming $P(n)$ for every $n$ . That would be circular: you're assuming exactly one arbitrary, fixed $k$ , and only that.
Skipping the base case because the inductive step "obviously works." A valid inductive step with a false or missing base case certifies nothing, no matter how solid the step is.
Reaching for strong induction's stronger hypothesis and then never actually using anything beyond $P(k)$ . That's ordinary induction with extra bookkeeping, not a different proof.
Forgetting that a strong-induction step reaching back several cases needs that many consecutive base cases anchored first, not just one. The postage-stamp problem needed three ( $n=8,9,10$ ), because its step always reaches back exactly 3.