1
The step is a conditional, proved for arbitrary k
You are not assuming P(k) is true for all k. You are proving the implication P(k) → P(k+1), which is a direct proof of a conditional.
Lesson · Induction and Recursion · Induction
Mathematical Induction
The technique in full: what each part does, how to write it, and the three ways an induction proof is wrong — no base case, an unused hypothesis, and a step proved only for a particular k.
1. BASE CASE: prove P(n₀)
2. INDUCTIVE STEP: assume P(k) for arbitrary k ≥ n₀, prove P(k+1)
3. CONCLUDE: P(n) holds for all n ≥ n₀
The step must USE P(k). A step that does not is not induction.
Three parts, all required
Core ideas
What this lesson establishes
Induction proves infinitely many statements by proving two: one specific case, and one implication that holds generally.
2
The base case anchors the chain
Without it the implications form a chain with nothing at the start. n = k+1 provable from n = k proves nothing on its own.
3
The hypothesis must actually be used
If the step never invokes P(k), you have proved P(k+1) outright and written induction around a direct proof. That is usually a sign the statement was easier than it looked — or that the proof is wrong.
The material
The technique
The three parts, the standard example, and the three failure modes.
Theorem · Principle of mathematical induction
Let P(n) be a statement about integers n ≥ n₀. If P(n₀) holds, and P(k) → P(k+1) for every k ≥ n₀, then P(n) holds for every n ≥ n₀.
The domino picture is standard and slightly misleading. It is right that the base case tips the first domino and the step is the guarantee that each knocks over the next. It is misleading in suggesting a process that takes time: the conclusion is not that every P(n) will eventually be proved, but that every P(n) is true.
Theorem · Sum of the first n positive integers
For every n ≥ 1, 1 + 2 + ⋯ + n = n(n+1)/2.
Base case. For n = 1 the left side is 1 and the right is 1 · 2 / 2 = 1. They agree.
Inductive step. Let k ≥ 1 be arbitrary and assume 1 + 2 + ⋯ + k = k(k+1)/2 — the inductive hypothesis. Then
1 + 2 + ⋯ + k + (k+1) = k(k+1)/2 + (k+1) — here the hypothesis was used to replace the first k terms — = (k+1)(k+2)/2, which is the claim at k+1.
Conclusion. By induction the formula holds for every n ≥ 1.
□
The sentence "here the hypothesis was used" is not padding. It is the sentence a reader checks for, and a proof that cannot point to it is not an induction proof.
Three ways to get it wrong
- No base case. Consider P(n): "n = n + 1". The step is fine — if k = k+1 then adding 1 gives k+1 = k+2 — and the statement is false for every n. The base case is what fails.
- The hypothesis is never used. If the step proves P(k+1) from scratch, the proof is a direct proof with an induction wrapper. Not wrong, but not induction — and often it means the step was misread.
- The step is proved for one k. Verifying P(3) → P(4) is not the inductive step. k must be arbitrary, exactly as in any universally quantified proof.
Example · The classic bogus proof
"All horses are the same colour." Base: one horse, trivially. Step: given k+1 horses, the first k are the same colour by hypothesis, and the last k are too, so all k+1 agree. The flaw is at k = 1: the two groups of one horse do not overlap, so nothing links them. The step fails for exactly one value of k, and one failure breaks the chain.
That example is worth more than its joke. It shows that an inductive step can be correct for every k but one, and that the whole proof collapses at that point. Checking the step at the smallest values is a cheap and effective habit.
Interactive
Check P(n), then notice checking is not proving
Two of these statements are false
Method
Writing an induction proof
Four sentences, in this order, every time.
1
State P(n) precisely
Write the statement being proved as a formula in n. Vague statements produce proofs that cannot be checked.
2
Prove the base case
Evaluate both sides at n₀ and show they agree. Say which n₀ you are using, especially when it is not 1.
3
Assume P(k) for arbitrary k ≥ n₀, and say so
Write the hypothesis out in full. A hypothesis you did not write is one you will not notice failing to use.
4
Derive P(k+1), pointing at where the hypothesis entered
The algebra usually splits off the (k+1) term and replaces the rest using the hypothesis. Name that substitution.
Induction
Score 0 / 0Choose the answer you can justify.
Prove 1 + 3 + 5 + ⋯ + (2n − 1) = n²
The sum of the first n odd numbers.
BASE n = 1: left = 1, right = 1² = 1. ✓
STEP Let k ≥ 1 and assume 1 + 3 + … + (2k−1) = k².
The sum to k+1 adds the next odd number, 2(k+1)−1 = 2k+1:
1 + 3 + … + (2k−1) + (2k+1)
= k² + (2k+1) ← hypothesis used HERE
= k² + 2k + 1
= (k+1)² ← the claim at k+1
CONCLUDE By induction the identity holds for every n ≥ 1. ∎
The step has exactly one interesting move: recognising k² + 2k + 1 as (k+1)². Every induction proof of a sum formula has this shape — peel off the last term, substitute, and recognise the target.
Common mistakes
1
Omitting the base caseWithout it the implications prove nothing. It is one line and it is the line that makes the rest mean something.
2
Never using the inductive hypothesisIf the step does not invoke P(k), ask what you have actually proved. Sometimes it is a stronger direct result; more often the step is wrong.
3
Assuming what is to be proved"Assume P(k+1)" is circular. The hypothesis is P(k), and the distinction is the whole technique.
Check your understanding
✓
Finish when you can point at the line where the hypothesis was used.
Prove 2 + 4 + ⋯ + 2n = n(n+1) and then mark the exact substitution that used the hypothesis. If you cannot mark it, the proof is either not induction or not finished.
Note: Induction proves statements about ℕ. Extending it to other structures — lists, trees, formulas — requires structural induction, which is “Structural Induction” and is the same idea over a different well-founded order.