Book of Proof, third edition
Richard Hammack · Free textbook
Read §9.1 for counterexamples and chapter 10 opening and §10.1, printed pp.180–183 / PDF pp.192–195, for induction.
Open the sourceFrom seeing a pattern to proving it
Examples suggest. A proof must cover the cases you have not seen.
Prerequisites: 03 · Sets: the grammar of selection, 04 · Functions and what they forget
Understand
Objectives
- State the base case and arbitrary induction step for the odd-sum theorem.
- Compute the next border and sum from an assumed square.
- Use a counterexample to reject an overbroad universal claim.
Start with something you can see
Arrange one dot in a square, then add an L-shaped border of three dots to make a two-by-two square. Predict the next border: it has five dots. The visible cases suggest a rule, but a drawing of the first few squares cannot cover every positive integer. The MIT induction lecture separates the first case and the general step at 29:10. [1]
Give the idea a precise name
A conjecture is a precise claim proposed from evidence. A counterexample refutes a universal claim. Mathematical induction proves a claim P(n) for every integer n starting at 1 by proving P(1), then proving P(n)⇒P(n+1) for an arbitrary n≥1. The base case starts the chain; the step carries it forward. For the odd-number sum, the theorem is:
1+3+⋯+(2n−1)=n²
Here n is a positive integer, the ellipsis continues the odd-number pattern, 2n−1 is its nth term, and n² is the area of an n-by-n dot square. The proof below supplies both induction jobs; checking many cases alone does not.
Work one small world
At n=1, the sum and square are both 1. Assume the formula for one arbitrary positive integer n. The next odd term is 2n+1, so the next sum is n²+(2n+1)=(n+1)². The base case and step prove the claim for all positive integers. For n=7, the sum is 49, and the next border has 15 dots, giving 64.
| n | Previous square | New border | New square |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 1 | 3 | 4 |
| 3 | 4 | 5 | 9 |
| 4 | 9 | 7 | 16 |
Counterexample to “every prime is odd”: 2 is prime and even. The repaired claim “every prime greater than 2 is odd” follows because an even integer greater than 2 has 2 as a proper divisor and so is not prime. A single valid counterexample defeats a universal statement, while a finite sweep of favorable cases does not prove one.
THE BRIDGELater numerical inequalities need structural proofs; plots and examples can suggest them but do not supply the missing universal argument.
WHERE THIS IDEA STOPSThe induction theorem begins at n=1. A step without a base proves no starting case, and a finite calculation does not establish infinitely many cases.
Experiment
Draw dot squares for n=1 through 4. Predict each new odd border, then check whether your drawing itself proves the rule for all n.
What hidden “for every” is concealed in the sentence you are trying to prove?
Check & explain
What is missing after verifying the odd-sum rule for n=1 through n=100?
- Nothing; 100 cases cover all integers
- A step from arbitrary n to n+1
- Another drawing of n=101
If the first eight odd numbers total 64, what is their sum after the next odd term?
Teach back
Prove the odd-sum theorem using its base and step, then refute “every prime is odd” and repair the claim.
- Quantify n over positive integers.
- Use the induction hypothesis in the step.
- Show that 2 meets the prime hypothesis and violates oddness.
Read deeper
Lecture 2 · Induction
MIT OpenCourseWare · Lecture · 79 min
Start at 19:00. Watch the short core 29:10–33:10; then the longer passage 19:00–38:00. The full 79-minute lecture is available from the same link.
Open the source