Induction

A claim about every natural number is infinitely many claims, and checking them one at a time never finishes.

The previous lesson, on proof by contrapositive and contradiction, ended on a claim neither method finishes: every integer $n \geq 2$ is a product of primes, where the argument for $n$ needs the claim for smaller numbers first. This lesson gives the method for such chains and proves it valid. Throughout, the natural numbers are $ℕ = {1, 2, 3, \dots}$ , starting at $1$ , and the definitions are the usual ones: $n$ is even when $n = 2 k$ for some integer $k$ , odd when $n = 2 k + 1$ , and $a ∣ b$ when $b = a k$ for some integer $k$ .

The principle

For each natural number $n$ let $P (n)$ be a statement, such as " $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ ". The principle of induction says: if $P (1)$ is true, and if for every natural number $n$ the conditional $P (n) \Rightarrow P (n + 1)$ is true, then $P (n)$ is true for every natural number $n$ .

The two hypotheses have names. Proving $P (1)$ is the base case. Proving $P (n) \Rightarrow P (n + 1)$ for every $n$ is the inductive step, and inside it the assumption $P (n)$ is the inductive hypothesis. The step is an ordinary conditional, proved directly: take an arbitrary $n$ , assume $P (n)$ , derive $P (n + 1)$ . This is not assuming what is to be proved, since the step never claims $P (n)$ is true, only that if it is, so is the next. The picture is a line of dominoes: the base case knocks over the first, and the step makes each falling domino knock over the next.

A claim can pass one check and fail the other. Let $P (n)$ be " $n^{2} + n$ is odd". The step holds: if $n^{2} + n$ is odd, then $(n + 1)^{2} + (n + 1) = (n^{2} + n) + 2 (n + 1)$ is an odd number plus an even one, hence odd. But $P (1)$ says $2$ is odd, which is false, and in fact $n^{2} + n = n (n + 1)$ is even for every $n$ . A proof by induction that skips the base case can prove something false.

A debt from the first lesson

The first lesson of this course defined even and odd, noted that nothing in the definitions says every integer is one or the other, and left that claim open, although every proof since has leaned on it. Induction pays the debt.

Example. Prove that every natural number is even or odd.

Let $P (n)$ be the statement " $n$ is even or $n$ is odd". For the base case, $1 = 2 \times 0 + 1$ , so $1$ is odd and $P (1)$ holds. For the inductive step, let $n$ be a natural number and assume $P (n)$ . If $n$ is even, then $n = 2 k$ for some integer $k$ , so $n + 1 = 2 k + 1$ is odd. If $n$ is odd, then $n = 2 k + 1$ for some integer $k$ , so $n + 1 = 2 k + 2 = 2 (k + 1)$ is even. In either case $n + 1$ is even or odd, so $P (n + 1)$ holds. By induction, $P (n)$ holds for every natural number $n$ .

The claim for all integers follows in a sentence: $0 = 2 \times 0$ is even, and for a natural number $n$ , if $n = 2 k$ then $- n = 2 (- k)$ , while if $n = 2 k + 1$ then $- n = 2 (- k - 1) + 1$ . The companion fact, that no integer is both, is a short contradiction: $2 k = 2 m + 1$ would give $k - m = \frac{1}{2}$ , and a difference of integers is an integer.

Now you. Prove by induction that $n^{2} + n$ is even for every natural number $n$ .

Answer

Let $P (n)$ be " $n^{2} + n$ is even". For the base case, $1^{2} + 1 = 2 = 2 \times 1$ , so $P (1)$ holds. For the step, let $n$ be a natural number with $n^{2} + n = 2 k$ for some integer $k$ . Then $(n + 1)^{2} + (n + 1) = n^{2} + 3 n + 2 = (n^{2} + n) + 2 (n + 1) = 2 k + 2 (n + 1) = 2 (k + n + 1)$ , and $k + n + 1$ is an integer, so $(n + 1)^{2} + (n + 1)$ is even and $P (n + 1)$ holds. By induction, $n^{2} + n$ is even for every natural number $n$ .

Why the principle holds

The principle rests on a property of $ℕ$ called the well-ordering principle: every nonempty collection of natural numbers has a least element. It fails for the integers, which have no least element. Well-ordering is taken as a basic property of $ℕ$ .

Theorem. The principle of induction holds.

Suppose, for contradiction, that $P (1)$ and the step both hold but $P (n)$ is false for some natural number $n$ . Then the collection of natural numbers $n$ for which $P (n)$ is false is nonempty, so by well-ordering it has a least element; call it $m$ . Since $P (1)$ is true, $m \neq 1$ , so $m \geq 2$ and $m - 1$ is a natural number. Since $m - 1 < m$ and $m$ is the least failure, $P (m - 1)$ is true. The inductive step with $n = m - 1$ then gives $P (m)$ , contradicting the choice of $m$ . So $P (n)$ holds for every $n$ .

A first failure would need a predecessor that succeeds, and the step forbids that. The same shape gives another way to write any induction, the smallest counterexample argument: take the least $n$ where the claim fails and find a smaller failure.

Sums

Adding $1 + 2 + \dots + 100$ in pairs from the outside in, $1 + 100$ , $2 + 99$ and so on, gives fifty pairs of $101$ , so $5050$ . The same pairing suggests $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ in general, and induction proves it.

Example. Prove that $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for every natural number $n$ .

Let $P (n)$ be the statement $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ . For the base case, the left side is $1$ and the right side is $\frac{1 \times 2}{2} = 1$ , so $P (1)$ holds. For the step, let $n$ be a natural number and assume $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ . Adding $n + 1$ to both sides,

1 + 2 + \dots + n + (n + 1) = \frac{n (n + 1)}{2} + (n + 1) = \frac{n (n + 1) + 2 (n + 1)}{2} = \frac{(n + 1) (n + 2)}{2} .

The right side is the formula with $n + 1$ in place of $n$ , a target worth writing down before the algebra starts, so $P (n + 1)$ holds. By induction, the formula is true for every natural number $n$ .

Induction checks a formula; it does not find one. The usual route is a guess from small cases: $1$ , $1 + 3 = 4$ , $1 + 3 + 5 = 9$ and $1 + 3 + 5 + 7 = 16$ suggest $1 + 3 + \dots + (2 n - 1) = n^{2}$ , and the step is one line, $n^{2} + (2 n + 1) = (n + 1)^{2}$ .

Now you. Prove that $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ for every natural number $n$ .

Answer

Let $P (n)$ be the formula. For the base case, both sides equal $1$ , since $\frac{1 \times 2 \times 3}{6} = 1$ . For the step, assume $P (n)$ for a natural number $n$ and add $(n + 1)^{2}$ to both sides. The right side becomes

\frac{n (n + 1) (2 n + 1) + 6 (n + 1)^{2}}{6} = \frac{(n + 1) (2 n^{2} + 7 n + 6)}{6} = \frac{(n + 1) (n + 2) (2 n + 3)}{6},

which is the formula with $n + 1$ in place of $n$ , since $2 (n + 1) + 1 = 2 n + 3$ . So $P (n + 1)$ holds, and by induction the formula holds for every $n$ .

Other starting points, and divisibility

Nothing forces the base case to be $1$ . If $P (n_{0})$ holds and $P (n) \Rightarrow P (n + 1)$ for every $n \geq n_{0}$ , then $P (n)$ holds for every $n \geq n_{0}$ ; this is the ordinary principle applied to $Q (k) = P (n_{0} + k - 1)$ . A later start is what inequalities often need. Compare $2^{n}$ with $n^{2}$ for $n = 1, 2, 3, 4$ : $2 > 1$ , then $4 = 4$ , $8 < 9$ and $16 = 16$ . From $n = 5$ , where $32 > 25$ , the power of two stays ahead.

Claim. $2^{n} > n^{2}$ for every integer $n \geq 5$ . For the base case, $2^{5} = 32 > 25 = 5^{2}$ . For the step, let $n \geq 5$ and assume $2^{n} > n^{2}$ . Then $2^{n + 1} = 2 \times 2^{n} > 2 n^{2}$ , and it remains to show $2 n^{2} \geq (n + 1)^{2}$ , that is, $n^{2} \geq 2 n + 1$ . Since $n \geq 5$ , $n^{2} \geq 5 n = 2 n + 3 n > 2 n + 1$ . So $2^{n + 1} > (n + 1)^{2}$ , and by induction the claim holds for every $n \geq 5$ .

The step in fact works for every $n \geq 3$ , yet the claim is false at $3$ and $4$ : a true conditional says nothing when its hypothesis is false, so the chain starts only where a base case is verified. For divisibility, the step shows that the new expression is the old one plus a multiple of the divisor.

Claim. $3 ∣ n^{3} - n$ for every natural number $n$ . For the base case, $1^{3} - 1 = 0 = 3 \times 0$ . For the step, assume $n^{3} - n = 3 k$ for some integer $k$ . Expanding, $(n + 1)^{3} - (n + 1) = n^{3} + 3 n^{2} + 3 n + 1 - n - 1 = (n^{3} - n) + 3 (n^{2} + n) = 3 (k + n^{2} + n)$ , which is a multiple of $3$ . By induction, the claim holds for every $n$ .

Writing $n^{3} - n = (n - 1) n (n + 1)$ , three consecutive integers, gives a shorter proof. Induction's merit is that it needs no such insight, only the algebra of one step.

Strong induction

Some steps need more than the case just before. Strong induction lets the step assume every earlier case: if $P (1)$ is true, and for every natural number $n$ the truth of $P (1), P (2), \dots, P (n)$ together implies $P (n + 1)$ , then $P (n)$ holds for every $n$ . It is no stronger than ordinary induction. Apply the ordinary principle to $Q (n)$ , " $P (1)$ through $P (n)$ are all true": $Q (1)$ is $P (1)$ , and the strong step turns $Q (n)$ into $P (n + 1)$ and hence $Q (n + 1)$ . As before, the base can start at any $n_{0}$ .

Example. Prove that every integer $n \geq 2$ is a product of primes, where a single prime counts as a product of one prime.

We use strong induction starting at $2$ . For the base case, $2$ is prime, so it is a product of one prime. For the step, let $n \geq 2$ and assume that every integer $k$ with $2 \leq k \leq n$ is a product of primes. Consider $n + 1$ . If $n + 1$ is prime, it is a product of one prime. Otherwise $n + 1 = a b$ for integers $a$ and $b$ that are both greater than $1$ and less than $n + 1$ , so both lie between $2$ and $n$ . By the inductive hypothesis each is a product of primes, and writing those two products side by side expresses $n + 1 = a b$ as a product of primes. By strong induction, every integer $n \geq 2$ is a product of primes.

Ordinary induction could not do this: that $59$ factorises says nothing about $60$ , whose proof uses $6$ and $10$ instead, giving $60 = (2 \times 3) (2 \times 5)$ . Uniqueness of the factorisation, apart from order, is a separate and harder theorem.

Now you. The Fibonacci numbers are $F_{1} = F_{2} = 1$ and $F_{n + 1} = F_{n} + F_{n - 1}$ for $n \geq 2$ , giving $1, 1, 2, 3, 5, 8, 13, \dots$ . Prove that $F_{n} < 2^{n}$ for every natural number $n$ .

Answer

We use strong induction with two base cases, because the step reaches back two places. $F_{1} = 1 < 2$ and $F_{2} = 1 < 4$ . For the step, let $n \geq 2$ and assume $F_{k} < 2^{k}$ for every $k \leq n$ . Then $F_{n + 1} = F_{n} + F_{n - 1} < 2^{n} + 2^{n - 1} < 2^{n} + 2^{n} = 2^{n + 1}$ . So the bound holds for $n + 1$ , and by strong induction for every $n$ . The step starts at $n = 2$ because $n = 1$ would call on the undefined $F_{0}$ , so $F_{2}$ must be checked by hand. The bound is generous, since $F_{30} = 832 040$ against $2^{30} = 1 073 741 824$ .

All horses are one colour

Here is a proof by induction of something false. Let $P (n)$ be "in any group of $n$ horses, all the horses are the same colour". For the base case, a group of one horse is one colour. For the step, assume $P (n)$ and take a group of $n + 1$ horses, lined up. Remove the last horse: the first $n$ form a group of $n$ , so by hypothesis they share a colour. Remove the first horse instead: the last $n$ share a colour too. The horses in the middle belong to both groups, so the two colours are the same, and all $n + 1$ horses are one colour. By induction, all horses everywhere are the same colour.

The base case is fine, so the step must fail for some $n$ . Try $n = 1$ , going from one horse to two, $A$ and $B$ . Removing the last leaves ${A}$ , removing the first leaves ${B}$ , and each is trivially one colour. The middle horses, in both groups, number $n - 1$ , which here is none. Nothing links $A$ 's colour to $B$ 's, and the step from $P (1)$ to $P (2)$ is invalid.

For every $n \geq 2$ the groups overlap in $n - 1 \geq 1$ horses and the step is correct. It fails at exactly one link, the first, and that is enough: $P (2)$ is false, so the chain never gets going. A written step often assumes something silent about $n$ , and the remedy is to run it by hand at the smallest value it must cover.

What the proofs are about

Induction completes the toolkit: direct proof, cases, contrapositive, contradiction, and, for claims indexed by the natural numbers, two finite checks. The objects those proofs talk about, though, have stayed informal. The proof of the principle took "the collection of natural numbers where $P$ fails" and asked for its least element, without saying what a collection is or when two collections are the same. The horses came in "groups" and were removed from them. Mathematics needs those words to mean something exact, and the next lesson makes them precise: sets, and how to prove that two of them are equal.