Home / Courses / Intro to Proofs / Unit 6

Intro to Proofs Unit 6: Mathematical Induction

Induction proves a statement for infinitely many integers with two finite checks: a base case and an inductive step. It is the standard method for sums, divisibility patterns, inequalities and recursively defined sequences.

Covers: Principle of mathematical induction, Base case and inductive step, Summation formulas, Divisibility by induction, Inequalities by induction, Strong induction, Well-ordering principle and flawed inductions

Study guide

To prove P(n) for every integer n ≥ a, ordinary induction has two parts. The base case shows P(a) is true. The inductive step shows that for an arbitrary k ≥ a, if P(k) is true (the inductive hypothesis), then P(k + 1) is true. Together these give P(a), then P(a + 1), then P(a + 2), and so on, like a line of dominoes. Before doing any algebra in the step, write out P(k + 1) explicitly, so you know exactly what target you need to reach. Then find where P(k) is hiding inside P(k + 1) and use the hypothesis there.

For summation formulas, add the next term to both sides of P(k). For 1 + 2 + ⋯ + n = n(n + 1)/2, the step is k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2. For divisibility, rewrite the k + 1 expression to contain the k expression: 4ᵏ⁺¹ − 1 = 4(4ᵏ − 1) + 3 shows 3 | (4ⁿ − 1). For inequalities, use the hypothesis and then a separate simple inequality: (k + 1)! = (k + 1)k! > (k + 1)2ᵏ > 2 · 2ᵏ when k + 1 > 2. The base case must match where the claim starts; 2ⁿ > n² is false at n = 3 and 4, so it starts at n = 5.

Strong induction lets the inductive hypothesis be P(a), P(a + 1), ..., P(k) all at once. Use it when P(k + 1) depends on cases further back than P(k): factoring n = ab into smaller factors, recurrences like the Fibonacci numbers, or postage problems where the step jumps back by 4. Include as many base cases as the step reaches back. The well-ordering principle, that every nonempty set of positive integers has a least element, is equivalent to induction. A typical use is 'let m be the smallest counterexample' and then show a smaller counterexample exists, or that m is not a counterexample after all.

Flawed induction proofs teach a lot. If the base case is false, a perfectly valid step proves nothing: 'n² + n is odd' has a correct step but fails at n = 1. If the step fails for even one k, the chain breaks: the 'all horses are the same color' argument fails only when moving from 1 to 2 horses, because the two groups do not overlap. Also avoid assuming P(n) for all n in the step, since that is circular. Finally, check that your algebra truly produces P(k + 1), not something that merely resembles it.

Key ideas

• Induction needs both a base case and an inductive step.
• The inductive hypothesis assumes P(k) for one arbitrary k, not for all n.
• Write P(k + 1) explicitly before starting the algebra.
• The base case must match the starting value of the claim.
• Strong induction assumes all earlier cases and needs as many base cases as the step reaches back.
• Well-ordering arguments take a least counterexample and contradict its minimality.
• A step that fails at even one value breaks the entire proof.

Formulas and rules

Common mistakes

• Skipping the base case or checking the wrong starting value.
• Assuming P(k + 1) or P(n) for all n in the inductive step, which is circular.
• Doing algebra without first writing what P(k + 1) says.
• Using too few base cases in strong induction when the step reaches back several values.
• Not checking that the inductive step works for the smallest k, as in the horses paradox.

Before the test, make sure you can

• Write the base case, inductive hypothesis and target P(k + 1) for a given claim.
• Prove summation formulas by induction.
• Prove divisibility statements by rewriting the k + 1 expression.
• Prove inequalities by induction, choosing the correct base case.
• Decide when strong induction is needed and how many base cases to check.
• Prove a closed form for a recursively defined sequence.
• Use the well-ordering principle with a least counterexample.
• Find the error in a flawed induction argument.

Words to know

Mathematical induction

A proof method: verify P(a), then show P(k) → P(k + 1) for all k ≥ a.

Base case

The verification that the statement holds at the starting value.

Inductive step

The proof that P(k) implies P(k + 1) for arbitrary k.

Inductive hypothesis

The assumption, during the inductive step, that P(k) is true.

Strong induction

Induction in which the hypothesis is that P(a), ..., P(k) are all true.

Well-ordering principle

Every nonempty set of positive integers has a least element.

Least counterexample

The smallest value where a claim fails, used in well-ordering proofs.

Recurrence relation

A rule defining each term of a sequence from earlier terms.

Closed form

A direct formula for the nth term, such as aₙ = 2ⁿ − 1.

Summation notation

Σ from i = 1 to n of aᵢ means a₁ + a₂ + ⋯ + aₙ.

Fibonacci numbers

F₁ = F₂ = 1 and Fₙ₊₂ = Fₙ₊₁ + Fₙ.

Bernoulli's inequality

(1 + x)ⁿ ≥ 1 + nx for x ≥ −1 and n ≥ 1.

Telescoping sum

A sum whose terms cancel in pairs, such as Σ (1/i − 1/(i + 1)).

Domino analogy

The base case knocks over the first domino; the step makes each domino knock over the next.

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.