Mark some points on a circle and join every pair of them with a straight line. Then count the regions inside the circle. Before you read on, make a prediction.
Five cases agreed with the doubling rule, and the sixth did not. Nothing in the first five warned that the rule would fail. This is the difference between a pattern and a proof, and it is the reason mathematics asks for proofs at all.
A pattern is a guess
A statement that looks true but has not been proved is called a conjecture (a guess, before proving). The doubling rule was a conjecture. Checking more cases can make a conjecture more convincing, but it cannot make it certain.
The formula $n^2 + n + 41$ shows how far this can go. Try some values of $n$ below. A cell outlined in red is a value of $n$ that does not give a prime.
The formula gives a prime for $n = 0, 1, 2, \ldots, 39$: forty primes in a row. At $n = 40$ it gives $1681 = 41^2$, which is not prime. One case is enough to show that a claim about every $n$ is false. That case is called a counterexample. Forty agreeing cases were not enough to show that the claim was true.
From the history of mathematics
In 1919 George Pólya conjectured that, for every $N > 1$, at least half of the numbers from 1 to $N$ have an odd number of prime factors. It holds for every $N$ below $906\,150\,257$, and it was believed for nearly forty years. In 1958 it was shown to fail somewhere, and decades later the first failure was found: $N = 906\,150\,257$. Nearly a billion cases agreed. Then one did not.
What a proof is
A proof is a chain of steps. It starts from things already accepted: definitions, results proved earlier, and the rules of algebra. Each step follows with certainty from the steps before it. If every step is correct, the conclusion cannot be false, however many cases it covers.
This is deductive reasoning: from a general rule to a particular case. For example, every multiple of 4 is even, and 132 is a multiple of 4, so 132 is even. You do not need to divide 132 by 2 to know this.
The circle problem went in the opposite direction, from a few cases to a general rule. In everyday English that is also called induction, and it can give a false conclusion. Deduction cannot.
A short proof shows how algebra covers every case at once. To prove that the sum of any two odd numbers is even, write the two numbers as $2a + 1$ and $2b + 1$, where $a$ and $b$ are integers. Use two different letters, so that the two numbers can be different. Their sum is
$$(2a + 1) + (2b + 1) = 2(a + b + 1).$$
Since $a + b + 1$ is an integer, the sum is 2 times an integer, so it is even. This holds for every pair of odd numbers, because $a$ and $b$ stand for any integers. The example $3 + 5 = 8$ would have proved nothing.
Statements that depend on n
Some statements are about every positive whole number. For example,
$$1 + 3 + 5 + \cdots + (2n - 1) = n^2.$$
This is a different statement for each value of $n$. Call it $P_n$. Then $P_1$ says $1 = 1^2$, $P_2$ says $1 + 3 = 2^2$, and so on, without end. You can check any one of them, but checking them one at a time never finishes. Mathematical induction proves the whole infinite list using only two facts.
The idea: a line of dominoes
As an analogy, picture a line of dominoes that never ends. You cannot push every domino by hand. But suppose you know two things: the first domino is pushed, and whenever any domino falls, it knocks over the next one. Then every domino falls.
Switch each fact off in turn, and push.
The four steps
Each step keeps its label in the rest of this article.
1 · Base case 2 · Hypothesis 3 · Inductive step 4 · Conclusion
To prove that $P_n$ is true for every integer $n \ge 1$:
- Base case Show that $P_1$ is true.
- Hypothesis Assume that $P_k$ is true for some integer $k \ge 1$.
- Inductive step Show that if $P_k$ is true, then $P_{k+1}$ is true. This is written $P_k \Rightarrow P_{k+1}$.
- Conclusion Since $P_1$ is true, and $P_k$ true implies $P_{k+1}$ true, by the principle of mathematical induction $P_n$ is true for every integer $n \ge 1$.
Here is the sum of odd numbers, proved in full.
Step 1 · Base case. For $n = 1$ the left side is $1$ and the right side is $1^2 = 1$. They agree, so $P_1$ is true.
Step 2 · Hypothesis. Assume $P_k$ is true for some $k \ge 1$:
$$1 + 3 + 5 + \cdots + (2k - 1) = k^2.$$
Step 3 · Inductive step. The next odd number is $2(k + 1) - 1 = 2k + 1$. Add it to both sides, and use the hypothesis to replace the sum by $k^2$:
$$1 + 3 + \cdots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2.$$
This is $P_{k+1}$: the same formula with $k + 1$ in place of $n$. So if $P_k$ is true, then $P_{k+1}$ is true.
Step 4 · Conclusion. Since $P_1$ is true, and $P_k$ true implies $P_{k+1}$ true, by the principle of mathematical induction $P_n$ is true for every integer $n \ge 1$. $\blacksquare$
Exam corner: the words that earn marks
Write these sentences in every induction proof. The algebra between them changes from question to question.
- Step 1 “… so $P_1$ is true.”
- Step 2 “Assume $P_k$ is true for some $k \ge 1$.”
- Step 3 “So if $P_k$ is true, then $P_{k+1}$ is true.”
- Step 4 “Since $P_1$ is true, and $P_k$ true implies $P_{k+1}$ true, by the principle of mathematical induction $P_n$ is true for all integers $n \ge 1$.”
Why the two facts reach every n
Choose any value, say $n = 1000$. The base case makes $P_1$ true. The inductive step turns $P_1$ into $P_2$, then $P_2$ into $P_3$. After 999 uses of the step, $P_{1000}$ is true. The same finite chain reaches any $n$ you choose, so no value is left out.
There is a second way to see this, by contradiction. Suppose both steps are done, but $P_n$ is false for some values of $n$. Among those values there is a smallest one, say $m$. It is not $1$, because the base case showed that $P_1$ is true. So $P_{m-1}$ is true, because $m$ was the smallest failure. But the inductive step says that $P_{m-1}$ makes $P_m$ true. That contradicts the failure of $P_m$, so there are no failures.
Notice that mathematical induction, despite its name, is deduction. It does not guess a rule from examples. It proves the rule from two facts, and the conclusion is certain.
Six beliefs that break a proof
Each card below is a belief that leads to a wrong or incomplete proof. Open the ones you are not sure about.
Belief 1Assuming $P_k$ is cheating.
The inductive step is an if–then statement. It does not claim that $P_k$ is true. It claims only that if $P_k$ is true, then $P_{k+1}$ is true. In the analogy: it does not say that domino $k$ has fallen. It says that if domino $k$ falls, domino $k + 1$ falls with it.
Logic makes this exact. An implication “$A \Rightarrow B$” is false in only one case: when $A$ is true and $B$ is false.
| $A$ | $B$ | $A \Rightarrow B$ |
|---|---|---|
| true | true | true |
| true | false | false |
| false | true | true |
| false | false | true |
In the step, $A$ is $P_k$ and $B$ is $P_{k+1}$. So the step rules out one situation only: $P_k$ true and $P_{k+1}$ false. Whether $P_k$ is true is the job of the base case.
Belief 2The base case is a formality.
Without the base case, the inductive step can prove nothing at all. Take the statement “$n(n + 1)$ is odd”. The inductive step works for it. If $k(k + 1)$ is odd, then
$$(k + 1)(k + 2) = k(k + 1) + 2(k + 1),$$
which is odd plus even, so it is odd. But the base case fails: $1 \times 2 = 2$ is even. In fact every $n(n + 1)$ is even, because one of two consecutive integers is even. The step was true only because its premise is never true: the last two rows of the table. The dominoes were never pushed.
Belief 3Assume it for all $k$.
The hypothesis assumes $P_k$ for some $k$: one particular value that is not named. Writing “assume $P_k$ is true for all $k$” assumes the whole statement you are trying to prove. That is a circular argument, and examiners withhold the reasoning marks for it. The hypothesis is one domino falling, not the whole line.
Belief 4The hypothesis only needs to be written down.
The hypothesis has to be used. In the proof above, the sum up to $(2k - 1)$ was replaced by $k^2$. That substitution is the link in the chain. If you reach $P_{k+1}$ without using $P_k$, you have not shown that one case leads to the next.
The same applies to divisibility. To prove that $8^n - 1$ is divisible by $7$, the hypothesis is $8^k - 1 = 7m$ for some integer $m$, and the step uses it directly:
$$8^{k+1} - 1 = 8(8^k - 1) + 7 = 8(7m) + 7 = 7(8m + 1).$$
Without the hypothesis, the bracket $8^k - 1$ would have no known factor of 7.
Belief 5The first case is always $n = 1$.
A statement can start later. The inequality $2^n > n^2$ is false for $n = 2, 3$ and $4$, but true for every $n \ge 5$. Its base case is $P_5$: $2^5 = 32 > 25 = 5^2$. The hypothesis is then for some $k \ge 5$, and the conclusion is for every $n \ge 5$. Choose the first domino to match the statement.
Belief 6The final sentence is decoration.
The conclusion is where the two facts become a statement about every $n$. Write it out in full, naming both facts and the principle of mathematical induction. Markschemes usually award a mark for it.
Find the flaw
Here is a famous “proof” that all horses are the same colour. Every line looks reasonable. Read it carefully and decide which step fails before you open the answer.
Let $P_n$ be the statement: “in any group of $n$ horses, all the horses are the same colour.”
Base case A group of 1 horse has only one colour, so $P_1$ is true.
Hypothesis Assume $P_k$ is true for some $k \ge 1$.
Inductive step Take any group of $k + 1$ horses. Remove the last horse: the remaining $k$ horses are all one colour, by the hypothesis. Now put it back and remove the first horse instead: these $k$ horses are also all one colour. The two groups share the horses in the middle, so both colours are the same, and all $k + 1$ horses are one colour.
Conclusion By induction, all horses are the same colour.
Show the flaw
The base case is correct, and the step works for $k \ge 2$. It fails at exactly one place: going from $k = 1$ to $k + 1 = 2$.
With 2 horses, removing the last horse leaves the first one, and removing the first horse leaves the second one. The two groups have no horse in common, so nothing connects their colours. The argument “the two groups share the horses in the middle” needs at least one horse in the middle, which only happens when $k \ge 2$.
So $P_1 \Rightarrow P_2$ is never proved. The first domino is pushed but does not knock over the second, and the chain stops at the start. An inductive step has to work for every $k$ from the base case on, including the first one.
Check yourself
1. Forty values of $n$ make a formula prime. Is the formula prime for all $n$?
Not necessarily. Examples cannot prove a claim about every $n$. The formula $n^2 + n + 41$ is prime for $n = 0$ to $39$ and fails at $n = 40$.
2. In step 2, may you write "assume $P_k$ is true for all $k$"?
No. Assume $P_k$ for some $k$. Assuming it for all $k$ assumes the result you are proving.
3. You proved $P_k \Rightarrow P_{k+1}$ but forgot the base case. What have you proved?
Nothing about any particular $n$. The statement “$n(n+1)$ is odd” has a working inductive step and is false for every $n$.
Where this leads
Induction is not only for sums. In the course it also proves divisibility results, inequalities, formulas for sequences defined by a recurrence, formulas for $n$-th derivatives, and De Moivre’s theorem for complex numbers. When a claim is about every integer from some point on, and each case builds on the one before, induction is a natural method to try.
Your turn
Prove by induction that $3 + 7 + 11 + \cdots + (4n - 1) = n(2n + 1)$ for every integer $n \ge 1$. Write the four steps, then check each one against the worked proof above. For a new problem each week, open the question of the week.
Chapter 3 of BetterMath, Proofs, covers deductive proof, disproof by counterexample, proof by contradiction and proof by induction, with worked examples for sums, divisibility, inequalities and recurrences.