Recipe

Prove a statement by mathematical induction

Use when: you need to establish a claim P(n) for every integer n starting at some fixed n0, and each new case only ever depends on the single case right before it

Goal: a complete proof establishing P(n) for every n at or above n0, with both obligations verified

Taught in Anatomy of an induction proof

Quick recipe

State the claim and the starting value
Prove the base case
Write the inductive hypothesis
Derive P(k+1) from the hypothesis
Conclude by induction

1
Write $P(n)$ out exactly as the statement to be proved. Identify the smallest $n_0$ for which the claim is being made.

Example

For " $1+3+5+\cdots+(2n-1)=n^2$ for every $n\ge1$ ," $P(n)$ is that equation and $n_0=1$ .

Why: naming both up front tells the base case which value to check and the conclusion which range it actually covers.
2
Substitute $n=n_0$ into $P(n)$ directly and confirm the two sides actually match.

Example

At $n=1$ : the left side is just $1$ , and the right side is $1^2=1$ . They agree, so $P(1)$ holds.

Why: the base case is the one confirmed starting point; without it, the inductive step has nothing to start a chain from.
3
Fix an arbitrary $k\ge n_0$ . Write $P(k)$ out in full as a trusted assumption, not a vague reference to "the formula."

Example

Assume $1+3+\cdots+(2k-1)=k^2$ .

Why: every line of the next step has to trace back to this exact written statement, or the step only assumes what it is trying to prove.
4
Start from the inductive hypothesis, then use ordinary algebra, or the object's own recursive definition, to reach $P(k+1)$ specifically. The exact algebra varies by claim: adding a term for a sum, bounding a term for an inequality, factoring for a divisibility fact.

Example

Add the next term, $2(k+1)-1$ , to both sides of the hypothesis: $k^2+(2k+1)=(k+1)^2$ , which is exactly $P(k+1)$ .

Why: this step is the entire chain reaction the base case sets off; nothing is proved for $n>n_0$ until $P(k+1)$ is actually derived.
5
State that since the base case holds, and the inductive step holds for an arbitrary $k$ , $P(n)$ is true for every $n\ge n_0$ , by the principle of mathematical induction.

Why: the conclusion turns two separately verified facts into a claim about infinitely many values of $n$ .

Common mistakes

Skipping the base case because it looks obviously true.
Writing "assume $P(n)$ " instead of the specific hypothesis $P(k)$ for one arbitrary $k$ .
Trying to reach $P(k+1)$ without ever using the inductive hypothesis inside the derivation.
Concluding "true for all $n$ " without having actually derived $P(k+1)$ from $P(k)$ .