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 that neither method finishes: every integer $n \geq 2$ is a product of primes. For an arbitrary $n$ , either $n$ is prime or $n = a b$ with $a$ and $b$ smaller than $n$ , and to finish, the argument needs the claim for $a$ and $b$ first. This lesson gives the method for such chains and proves it valid. It then puts the method to work on sums, inequalities and divisibility, on sequences defined by recursion, on claims that only yield once they are strengthened, and finally on objects that are not numbers at all. Throughout, $ℕ = {1, 2, 3, \dots}$ starts 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 of induction

For each natural number $n$ let $P (n)$ be a statement, such as " $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ ". In the language of the lesson on quantifiers, $P$ is an open sentence with domain $ℕ$ , and the goal is $\forall n \in ℕ P (n)$ .

The principle of induction. Let $P (n)$ be a statement for each natural number $n$ . If $P (1)$ is true, and $P (n) \Rightarrow P (n + 1)$ is true for every natural number $n$ , then $P (n)$ is true for every natural number $n$ .

The two hypotheses have names. Proving $P (1)$ is the base case. Proving $\forall n \in ℕ (P (n) \Rightarrow P (n + 1))$ is the inductive step, and inside it the assumption $P (n)$ is the inductive hypothesis. The step is an ordinary universal conditional, and it is proved the way the lesson on direct proof proved every such statement: let $n$ be an arbitrary natural number, assume $P (n)$ , and derive $P (n + 1)$ .

Why should the two together reach every $n$ ? The base case gives $P (1)$ . The step with $n = 1$ gives $P (1) \Rightarrow P (2)$ , so $P (2)$ . The step with $n = 2$ gives $P (3)$ , and so on. For any one number, say $1000$ , a chain of $999$ applications of the step reaches it, and the chain is finite. What no finite chain can do is reach every $n$ at once, and that is what the principle adds. The usual picture is a line of dominoes: the base case knocks over the first, the step guarantees that each falling domino knocks over the next, and so every domino falls, however long the line.

A first reaction to the step is that it assumes what it is meant to prove. It does not. The goal is the universal statement " $P (n)$ for every $n$ ". The step assumes $P (n)$ for one arbitrary $n$ , as the hypothesis of a conditional, and shows only that $P (n + 1)$ would follow. It never claims that $P (n)$ is true. Someone with no idea whether $P (5)$ holds can still prove "if $P (5)$ then $P (6)$ ". Assuming $P (n)$ for a single arbitrary $n$ is legitimate; assuming $P (n)$ for every $n$ would be circular, and the difference between those two is the difference between an induction and a fraud.

A written proof by induction has a standard shape, and it pays to keep to it until the method is second nature. State $P (n)$ in full. Prove the base case $P (1)$ , usually by computing both sides. For the step, write "let $n$ be a natural number and suppose $P (n)$ ", then write out $P (n + 1)$ explicitly as the target, and derive it, marking the line where the inductive hypothesis is used. Finish with "by induction, $P (n)$ holds for every natural number $n$ ".

Both halves are needed, and a claim can pass one 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 that $2$ is odd, which is false, and in fact $n^{2} + n = n (n + 1)$ is even for every $n$ . The step was a true conditional whose hypothesis never holds. In the other direction, a base case with no step is a single example, and the first lesson showed where examples lead: $n^{2} + n + 41$ is prime for $n = 0, 1, \dots, 39$ and not for $n = 40$ .

Sums

Sums are where induction is first met, and the notation for them is worth fixing. For numbers $a_{1}, a_{2}, \dots, a_{n}$ ,

\sum_{k = 1}^{n} a_{k} = a_{1} + a_{2} + \dots + a_{n}

read "the sum of $a_{k}$ for $k$ from $1$ to $n$ ". The letter $k$ is a dummy: $\sum_{k = 1}^{n} k^{2}$ and $\sum_{j = 1}^{n} j^{2}$ are the same number. The one property of the notation an induction uses is

\sum_{k = 1}^{n + 1} a_{k} = \sum_{k = 1}^{n} a_{k} + a_{n + 1}

which says that the sum up to $n + 1$ is the sum up to $n$ with one more term added. A later section makes this the definition.

A story told of Carl Friedrich Gauss as a schoolboy has him adding $1 + 2 + \dots + 100$ in pairs from the outside in: $1 + 100$ , $2 + 99$ , and so on, fifty pairs of $101$ , so $5050$ . The same pairing suggests a formula for every $n$ , and induction proves it.

Example. Prove that $\sum_{k = 1}^{n} k = \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 of $P (1)$ 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 suppose $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ . The target is $P (n + 1)$ , which reads $1 + 2 + \dots + (n + 1) = \frac{(n + 1) (n + 2)}{2}$ . Adding $n + 1$ to both sides of the inductive hypothesis,

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}

which is the target, so $P (n + 1)$ holds. By induction, the formula holds for every natural number $n$ .

Writing the target before the algebra is what made the last step obvious: once $\frac{(n + 1) (n + 2)}{2}$ was on the page, the factor $n + 1$ was the thing to pull out. Without a target, a step of this kind tends to expand everything and then struggle to recognise the result.

Now you. Prove that $\sum_{k = 1}^{n} k^{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, let $n$ be a natural number and suppose $P (n)$ . The target is $\sum_{k = 1}^{n + 1} k^{2} = \frac{(n + 1) (n + 2) (2 n + 3)}{6}$ , since $2 (n + 1) + 1 = 2 n + 3$ . Adding $(n + 1)^{2}$ to both sides of the inductive hypothesis, the right side becomes

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

which is the target. So $P (n + 1)$ holds, and by induction the formula holds for every $n$ . As a check, $n = 3$ gives $1 + 4 + 9 = 14$ and $\frac{3 \times 4 \times 7}{6} = 14$ .

Induction checks a formula; it does not find one. The usual route is a guess from small cases. The sums $1$ , $1 + 3 = 4$ , $1 + 3 + 5 = 9$ and $1 + 3 + 5 + 7 = 16$ suggest that the first $n$ odd numbers add up to $n^{2}$ , and then the step is one line, $n^{2} + (2 n + 1) = (n + 1)^{2}$ . The guess has to be exact before induction can touch it. "The sum of the first $n$ odd numbers is a perfect square" is true, but as an inductive hypothesis it is useless, since knowing that some sum is some square says nothing about which square, and so nothing about the next sum. The sharper claim, that the square is $n^{2}$ , is the one that carries itself from $n$ to $n + 1$ . That observation returns, in a stronger form, later in the lesson.

How is a formula like the sum of squares found in the first place?

One way is to make the sum collapse. For any numbers $b_{1}, b_{2}, \dots, b_{n + 1}$ ,

\sum_{k = 1}^{n} (b_{k + 1} - b_{k}) = b_{n + 1} - b_{1}

because each $b_{k}$ in the middle is added once and subtracted once. (A careful proof of this "telescoping" is itself a one-line induction.) So a sum can be evaluated whenever its terms can be written as differences. Take $b_{k} = k^{3}$ . Then $(k + 1)^{3} - k^{3} = 3 k^{2} + 3 k + 1$ , and summing from $k = 1$ to $n$ gives

(n + 1)^{3} - 1 = 3 \sum_{k = 1}^{n} k^{2} + 3 \cdot \frac{n (n + 1)}{2} + n

using the formula for $\sum k$ already proved. Solve for the unknown sum:

3 \sum_{k = 1}^{n} k^{2} = (n + 1)^{3} - (n + 1) - \frac{3 n (n + 1)}{2} = (n + 1) (n^{2} + 2 n - \frac{3 n}{2}) = \frac{n (n + 1) (2 n + 1)}{2}

and dividing by $3$ gives the formula of the Now you. This is a derivation, not a guess, so strictly it needs no separate induction; but the telescoping identity it rests on is an induction, so induction is there either way.

A second way uses the shape of the answer. Summing a polynomial of degree $d$ gives a polynomial of degree $d + 1$ (the same telescoping argument, with $b_{k} = k^{d + 1}$ , shows this by induction on $d$ ). So $\sum_{k = 1}^{n} k^{2}$ is $a n^{3} + b n^{2} + c n + e$ for some constants, and the four values $0$ , $1$ , $5$ , $14$ at $n = 0, 1, 2, 3$ determine them. Solving gives $a = \frac{1}{3}$ , $b = \frac{1}{2}$ , $c = \frac{1}{6}$ , $e = 0$ , which is the formula again.

Repeating the first method with $b_{k} = k^{4}$ , $k^{5}$ and so on gives $\sum k^{3}$ , $\sum k^{4}$ , one after another. Jakob Bernoulli found the general pattern, published in his Ars Conjectandi in 1713, and the coefficients that appear in it are still called the Bernoulli numbers.

Why induction works

The lesson on direct proof took one property of $ℕ$ as basic and used it to prove the division algorithm.

The well-ordering principle. Every non-empty set of natural numbers has a least element.

It fails for the integers, which have no least element, and for the positive rationals, since half of any positive rational is a smaller one. It is a fact about how $ℕ$ is built, and induction follows from it.

Theorem. The well-ordering principle implies the principle of induction.

Proof. Suppose $P (1)$ is true and $P (n) \Rightarrow P (n + 1)$ for every natural number $n$ , and suppose, for contradiction, that $P (n)$ is false for some natural number $n$ . Then the set $F$ of natural numbers $n$ for which $P (n)$ is false is non-empty, so by well-ordering it has a least element $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 element of $F$ , the number $m - 1$ is not in $F$ , so $P (m - 1)$ is true. The inductive step with $n = m - 1$ then gives $P (m)$ , contradicting $m \in F$ . So $F$ is empty, and $P (n)$ holds for every $n$ . $□$

The shape of this proof is worth keeping. A first failure would need a predecessor that succeeds, and the step forbids exactly that. The same shape gives another way to write any induction, the smallest counterexample argument: suppose the claim fails somewhere, take the least $n$ where it fails, and derive a contradiction, usually by finding a smaller failure. Here it is on a fact the previous lesson proved in just this way, for Euclid's proof that the primes never run out.

Proposition. Every integer $n \geq 2$ has a prime divisor.

Proof. Suppose not, and let $m$ be the least integer $m \geq 2$ with no prime divisor; it exists by well-ordering. Then $m$ is not prime, since a prime divides itself. So $m = a b$ for integers $a$ and $b$ with $1 < a < m$ . As $2 \leq a < m$ and $m$ is the least counterexample, $a$ has a prime divisor $p$ . Then $p ∣ a$ and $a ∣ m$ , so $p ∣ m$ by transitivity of divisibility, and $m$ has a prime divisor after all. This contradiction proves the proposition. $□$

Well-ordering was stated for sets of natural numbers, and the proof applied it to a set of integers that are at least $2$ . That is harmless: such a set is a set of natural numbers. More generally, a non-empty set of integers that are all at least some fixed integer $n_{0}$ has a least element, by shifting every member by $1 - n_{0}$ , taking the least element of the resulting set of natural numbers, and shifting back.

Is induction a theorem or an axiom?

The theorem above derived induction from well-ordering, and a later section derives well-ordering from induction. Neither derivation starts from nothing: each assumes the other, or something equivalent. So one of them has to be taken as a basic truth about $ℕ$ , and which one is a matter of taste. This course took well-ordering; most axiomatic treatments take induction.

The standard axioms are due to Richard Dedekind, in his 1888 essay Was sind und was sollen die Zahlen? ("What are numbers and what should they be?"), and Giuseppe Peano, whose 1889 Arithmetices principia set them out in the form now called the Peano axioms. In modern dress they say: $1$ is a natural number; every natural number $n$ has a successor $n + 1$ , which is a natural number; $1$ is not the successor of anything; different numbers have different successors; and any set that contains $1$ and contains the successor of each of its members contains every natural number. The last axiom is the principle of induction, stated for sets instead of statements (take the set of $n$ for which $P (n)$ holds).

The first four axioms do not imply the fifth. They are all true of a structure made of $ℕ$ together with a second, separate chain $\dots, c_{- 1}, c_{0}, c_{1}, \dots$ in which the successor of $c_{i}$ is $c_{i + 1}$ : every element has exactly one successor, different elements have different successors, and $1$ is still no one's successor. But the set $ℕ$ itself contains $1$ and is closed under successors, and it leaves out every $c_{i}$ . The induction axiom is precisely what rules such extra chains out. It says that the natural numbers are the things reachable from $1$ by adding $1$ finitely many times, and nothing else.

That is also why induction is not a law of logic. Logic alone, from $P (1)$ and $\forall n (P (n) \Rightarrow P (n + 1))$ , derives $P (2)$ , $P (3)$ and each particular $P (n)$ in finitely many steps, but never $\forall n P (n)$ , because the structure with the extra chain satisfies the premises and not the conclusion. The Logic course makes this point formally in its lesson on proof technique. The name "mathematical induction", for the method as a whole, was given by Augustus De Morgan in 1838.

Other starting points, and inequalities

Nothing forces the base case to be $1$ .

Induction from $n_{0}$ . Let $n_{0}$ be an integer and let $P (n)$ be a statement for each integer $n \geq n_{0}$ . If $P (n_{0})$ is true, and $P (n) \Rightarrow P (n + 1)$ for every integer $n \geq n_{0}$ , then $P (n)$ is true for every integer $n \geq n_{0}$ .

Proof. Apply the ordinary principle to $Q (k) = P (n_{0} + k - 1)$ for $k \in ℕ$ . Then $Q (1)$ is $P (n_{0})$ , and $Q (k) \Rightarrow Q (k + 1)$ is the step for $n = n_{0} + k - 1 \geq n_{0}$ . So $Q (k)$ holds for every natural number $k$ , which says $P (n)$ holds for every integer $n \geq n_{0}$ . $□$

A start at $n_{0} = 0$ is common, for sums that begin at $k = 0$ and for statements about sets with $n$ elements, where the empty set is the natural first case. A later start is what many inequalities need. Compare $2^{n}$ with $n^{2}$ : for $n = 1, 2, 3, 4$ the values are $2 > 1$ , $4 = 4$ , $8 < 9$ and $16 = 16$ . From $n = 5$ , where $32 > 25$ , the power of two pulls ahead and stays there.

Claim. $2^{n} > n^{2}$ for every integer $n \geq 5$ .

Proof. For the base case, $2^{5} = 32 > 25 = 5^{2}$ . For the step, let $n \geq 5$ and suppose $2^{n} > n^{2}$ . The target is $2^{n + 1} > (n + 1)^{2}$ . By the hypothesis, $2^{n + 1} = 2 \times 2^{n} > 2 n^{2}$ , so it is enough 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 used $n \geq 5$ only to get $n^{2} > 2 n + 1$ , which holds for every $n \geq 3$ . So the step is valid from $n = 3$ on, and yet the claim is false at $n = 3$ and $n = 4$ . There is no contradiction: a true conditional says nothing when its hypothesis is false, and $P (3)$ is false, so $P (3) \Rightarrow P (4)$ is true and useless. The chain starts only where a base case has been checked.

Inequality steps have a common pattern, visible above. The hypothesis gives a bound for the new quantity (here $2^{n + 1} > 2 n^{2}$ ), and what remains is to compare that bound with the target (here $2 n^{2} \geq (n + 1)^{2}$ ). That leftover comparison usually involves no induction at all, and it is where the condition on $n$ gets used. Finding it is most of the work.

Example. Prove Bernoulli's inequality: for every real number $x \geq - 1$ and every natural number $n$ , $(1 + x)^{n} \geq 1 + n x$ .

There are two variables, and the induction is on $n$ alone. Fix a real number $x \geq - 1$ , and let $P (n)$ be the statement $(1 + x)^{n} \geq 1 + n x$ .

For the base case, $(1 + x)^{1} = 1 + x = 1 + 1 \cdot x$ , so $P (1)$ holds with equality.

For the step, let $n$ be a natural number and suppose $(1 + x)^{n} \geq 1 + n x$ . The target is $(1 + x)^{n + 1} \geq 1 + (n + 1) x$ . Since $x \geq - 1$ , the number $1 + x$ is non-negative, and multiplying both sides of an inequality by a non-negative number keeps its direction. So

(1 + x)^{n + 1} = (1 + x)^{n} (1 + x) \geq (1 + n x) (1 + x) = 1 + (n + 1) x + n x^{2} \geq 1 + (n + 1) x

where the last step uses $n x^{2} \geq 0$ . So $P (n + 1)$ holds. By induction, $P (n)$ holds for every $n$ , and since $x \geq - 1$ was arbitrary, the inequality holds for all such $x$ .

The hypothesis $x \geq - 1$ was used exactly once, to multiply through by $1 + x$ , and it cannot be dropped: at $x = - 4$ and $n = 3$ , the left side is $(- 3)^{3} = - 27$ and the right side is $1 - 12 = - 11$ . The inequality is crude but strong enough for a striking conclusion. With $x = 0.01$ it gives ${1.01}^{n} \geq 1 + \frac{n}{100}$ , so ${1.01}^{100 000} \geq 1001$ , and in general a growth factor above $1$ , however slightly above, eventually exceeds any bound. That fact returns in the lesson on limits.

Now you. Prove that $n! > 2^{n}$ for every integer $n \geq 4$ , where $n! = 1 \times 2 \times \dots \times n$ . Check that the claim is false for $n = 1, 2, 3$ , and say for which $n$ the step is valid.

Answer

Let $P (n)$ be $n! > 2^{n}$ . For the base case, $4! = 24 > 16 = 2^{4}$ .

For the step, let $n \geq 4$ and suppose $n! > 2^{n}$ . The target is $(n + 1)! > 2^{n + 1}$ . Now $(n + 1)! = (n + 1) \cdot n! > (n + 1) \cdot 2^{n}$ , using the hypothesis and $n + 1 > 0$ . Since $n + 1 \geq 2$ , $(n + 1) \cdot 2^{n} \geq 2 \cdot 2^{n} = 2^{n + 1}$ . So $(n + 1)! > 2^{n + 1}$ , and by induction the claim holds for every $n \geq 4$ .

For small $n$ : $1! = 1 < 2$ , $2! = 2 < 4$ and $3! = 6 < 8$ , so the claim is false at $1$ , $2$ and $3$ . The step used only $n + 1 \geq 2$ , so it is valid for every $n \geq 1$ . As with $2^{n} > n^{2}$ , the base case, not the step, decides where the claim starts.

Divisibility

For a claim of the form $d ∣ f (n)$ , the step has a characteristic move: write $f (n + 1)$ as a multiple of $f (n)$ plus something visibly divisible by $d$ . Then the hypothesis takes care of the first part and algebra takes care of the second.

Claim. $3 ∣ n^{3} - n$ for every natural number $n$ .

Proof. For the base case, $1^{3} - 1 = 0 = 3 \times 0$ . For the step, suppose $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)$ , a product of three consecutive integers, one of which is a multiple of $3$ by the division algorithm, gives a shorter proof, and one that covers negative $n$ as well. The merit of induction is that it needs no such insight, only the algebra of one step. When the expression has a power with $n$ in the exponent, the useful split is usually different: factor out the base of the power.

Example. Prove that $9 ∣ 4^{n} + 6 n - 1$ for every natural number $n$ .

Let $P (n)$ be the statement $9 ∣ 4^{n} + 6 n - 1$ . For the base case, $4 + 6 - 1 = 9$ , which is divisible by $9$ .

For the step, let $n$ be a natural number and suppose $4^{n} + 6 n - 1 = 9 k$ for some integer $k$ . The target is $9 ∣ 4^{n + 1} + 6 (n + 1) - 1$ . The term $4^{n + 1}$ is $4 \times 4^{n}$ , so aim to produce $4$ copies of the old expression:

4^{n + 1} + 6 n + 5 = 4 (4^{n} + 6 n - 1) - 24 n + 4 + 6 n + 5 = 4 (4^{n} + 6 n - 1) - 18 n + 9

The right side is $4 \times 9 k - 9 (2 n - 1) = 9 (4 k - 2 n + 1)$ , and $4 k - 2 n + 1$ is an integer, so $P (n + 1)$ holds. By induction, $9 ∣ 4^{n} + 6 n - 1$ for every natural number $n$ .

The bookkeeping line is the only idea: after writing $4^{n + 1} = 4 \times 4^{n}$ , add and subtract whatever makes $4$ times the old expression appear, and check that what is left over is divisible by $9$ . For $n = 2$ and $n = 3$ the numbers are $16 + 12 - 1 = 27$ and $64 + 18 - 1 = 81$ .

Now you. Prove that $64 ∣ 9^{n} - 8 n - 1$ for every natural number $n$ .

Answer

Let $P (n)$ be the statement. For the base case, $9 - 8 - 1 = 0 = 64 \times 0$ .

For the step, let $n$ be a natural number and suppose $9^{n} - 8 n - 1 = 64 k$ for some integer $k$ . Then

9^{n + 1} - 8 (n + 1) - 1 = 9 (9^{n} - 8 n - 1) + 72 n + 9 - 8 n - 9 = 9 \times 64 k + 64 n = 64 (9 k + n)

and $9 k + n$ is an integer, so $P (n + 1)$ holds. By induction, $64 ∣ 9^{n} - 8 n - 1$ for every natural number $n$ . For $n = 2$ the number is $81 - 17 = 64$ , and for $n = 3$ it is $729 - 25 = 704 = 64 \times 11$ .

Induction also gives a second proof of a fact that the lesson on direct proof derived from the division algorithm: every integer is even or odd. Let $P (n)$ be " $n$ is even or $n$ is odd". The base case holds since $1 = 2 \times 0 + 1$ is odd. For the step, if $n = 2 k$ then $n + 1 = 2 k + 1$ is odd, and if $n = 2 k + 1$ then $n + 1 = 2 (k + 1)$ is even, so $P (n + 1)$ holds in either case. That covers $ℕ$ . For the other integers, $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$ . This proof needs only the definitions and induction, where the division algorithm needed well-ordering, and a later section shows that those two are one principle in different forms.

All horses are one colour

Here is a proof by induction of something false. It is worth taking apart slowly, because the error in it is the most common error in real inductions.

Claim. In any group of $n$ horses, all the horses are the same colour.

Proof. Let $P (n)$ be the claim for groups of $n$ horses. For the base case, a group of one horse is one colour. For the step, suppose $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 the inductive 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, every group of horses is one colour.

The base case is fine, so the step must fail for some $n$ . The step claims to prove $P (n) \Rightarrow P (n + 1)$ for every $n \geq 1$ , so try the smallest, $n = 1$ , going from one horse to two, $A$ and $B$ . Removing the last horse leaves ${A}$ and removing the first leaves ${B}$ , and each is trivially one colour. The horses "in the middle", 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 two groups overlap in $n - 1 \geq 1$ horses, and the step is correct: $P (2) \Rightarrow P (3)$ is a true conditional, and so are all the later links. The chain fails at exactly one link, the first, and that is enough, because $P (2)$ is false and every later domino waits on it. The argument hid an assumption about $n$ , that there is at least one horse in the middle, and the remedy is mechanical: run the step by hand at the smallest value it must cover. A step that is valid only for $n \geq 2$ needs base cases up to $2$ , and here $P (2)$ cannot be proved, because it is false.

Two other failures are worth knowing by sight. The first is a step of the wrong size. From $P (1)$ and $P (n) \Rightarrow P (n + 2)$ follow $P (3)$ , $P (5)$ , $P (7)$ and so on, and nothing at all about even $n$ . A step that jumps by more than $1$ needs as many base cases as the size of the jump, one to start each chain; the section on strong induction does exactly this.

The second is building up instead of cutting down. A step should start from an arbitrary object of size $n + 1$ and reduce it to objects of size $n$ , as the horse argument (correctly, in this respect) did. The tempting alternative starts from an object of size $n$ , for which $P (n)$ holds, and enlarges it by one; but that proves the claim only for those objects of size $n + 1$ that arise by enlarging, and there may be others. In graph theory, where objects are grown one vertex or edge at a time, this "build-up error" produces convincing false proofs, and the cure is always the same: begin the step with an arbitrary object of the larger size.

Strong induction

Some steps need more than the case just before. To show that $60$ is a product of primes, knowing that $59$ is one is no help at all; what helps is that $60 = 6 \times 10$ and that $6$ and $10$ are products of primes. Strong induction lets the step assume every earlier case, not only the last.

The principle of strong induction. Let $P (n)$ be a statement for each natural number $n$ . If $P (1)$ is true, and for every natural number $n$ the truth of all of $P (1), P (2), \dots, P (n)$ implies $P (n + 1)$ , then $P (n)$ is true for every natural number $n$ .

Despite the name, it is no stronger than ordinary induction.

Theorem. The principle of induction implies the principle of strong induction.

Proof. Suppose $P (1)$ holds and the strong step holds. Let $Q (n)$ be the statement " $P (1), P (2), \dots, P (n)$ are all true", and apply ordinary induction to $Q$ . The base case $Q (1)$ is $P (1)$ , which is true. For the step, suppose $Q (n)$ . Then $P (1)$ to $P (n)$ are all true, so the strong step gives $P (n + 1)$ , and together these say $Q (n + 1)$ . By induction, $Q (n)$ holds for every $n$ , and in particular $P (n)$ holds for every $n$ . $□$

As with ordinary induction, the start can be any integer $n_{0}$ : the step for $n + 1$ may then assume $P (k)$ for every $k$ with $n_{0} \leq k \leq n$ .

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$ . Let $P (n)$ be " $n$ is a product of primes".

For the base case, $2$ is prime, so it is a product of one prime.

For the step, let $n \geq 2$ and suppose 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, since $n + 1 \geq 2$ and is not prime, $n + 1 = a b$ for integers $a$ and $b$ with $1 < a < n + 1$ and $1 < b < n + 1$ . So $2 \leq a \leq n$ and $2 \leq b \leq n$ , and by the inductive hypothesis each of $a$ and $b$ is a product of primes. Writing the two products side by side expresses $n + 1 = a b$ as a product of primes. So $P (n + 1)$ holds, and by strong induction every integer $n \geq 2$ is a product of primes.

This is the existence half of the fundamental theorem of arithmetic. The other half, that the factorisation is unique apart from the order of the factors, is a separate and harder theorem: it needs Euclid's lemma from the previous lesson, that a prime dividing a product divides one of the factors, and it is proved in the Discrete Mathematics lesson on primes. That lesson also shows a number system, the even numbers, in which the existence proof above goes through word for word and uniqueness fails, which is the best evidence that uniqueness is not a formality.

Now you. Prove that every integer $n \geq 8$ can be written as $3 a + 5 b$ with $a$ and $b$ non-negative integers. (Think of paying $n$ pence exactly with 3p and 5p stamps.) Show that $7$ cannot be written this way.

Answer

Let $P (n)$ be " $n = 3 a + 5 b$ for some non-negative integers $a$ and $b$ ". We use strong induction starting at $8$ , with three base cases, because the step reaches back three places.

Base cases: $8 = 3 + 5$ , $9 = 3 + 3 + 3$ and $10 = 5 + 5$ , so $P (8)$ , $P (9)$ and $P (10)$ hold.

Step: let $n \geq 10$ and suppose $P (k)$ for every $k$ with $8 \leq k \leq n$ . Then $n + 1 \geq 11$ , so $k = n - 2$ satisfies $8 \leq k \leq n$ , and by the hypothesis $n - 2 = 3 a + 5 b$ with $a, b \geq 0$ . So $n + 1 = 3 (a + 1) + 5 b$ , with $a + 1$ and $b$ non-negative, and $P (n + 1)$ holds. By strong induction, $P (n)$ holds for every $n \geq 8$ .

The step starts at $n = 10$ , not $8$ , because for $n + 1 = 9$ or $10$ the number $n - 2$ would be $7$ or $8$ , and $7$ is below the start. That is why $9$ and $10$ had to be base cases.

For $7$ : if $7 = 3 a + 5 b$ with $a, b \geq 0$ , then $b \leq 1$ . If $b = 0$ then $3 a = 7$ , and if $b = 1$ then $3 a = 2$ , and neither has an integer solution. So $7$ cannot be written, and the start at $8$ cannot be lowered.

The number of base cases is set by the step, not by taste. Count how far back the step reaches (here $3$ places), and check by hand every case the step cannot produce from an earlier one. In the Now you, those were $8$ , $9$ and $10$ . The answer's $7$ is not an accident: for stamps of $a$ and $b$ pence with no common factor greater than $1$ , the largest amount that cannot be paid exactly is $a b - a - b$ , here $15 - 3 - 5 = 7$ , a result usually credited to James Joseph Sylvester.

Ordinary induction could have done the stamps, with a less natural step: go from $n$ to $n + 1$ by trading a 5p stamp for two 3p stamps when there is one, and three 3p stamps for two 5p stamps otherwise (possible since $n \geq 8$ forces at least three 3p stamps when there is no 5p stamp). Strong induction is not more powerful, as the theorem showed, but it lets the step reach for whichever earlier case is useful, and that is often the difference between an easy proof and a clever one.

Recursive definitions and the Fibonacci numbers

Induction proves statements about every natural number. Its partner, recursion, defines objects for every natural number, in the same two parts: a starting value, and a rule that gives each next value from the earlier ones. Many familiar objects are defined this way, even when school presented them otherwise.

For a real number $a$ , the powers are defined by $a^{0} = 1$ and $a^{n + 1} = a^{n} \cdot a$ for every integer $n \geq 0$ . Factorials are defined by $0! = 1$ and $(n + 1)! = (n + 1) \cdot n!$ , which gives $1! = 1$ , $2! = 2$ , $3! = 6$ , $4! = 24$ . Sums are defined by $\sum_{k = 1}^{1} a_{k} = a_{1}$ and $\sum_{k = 1}^{n + 1} a_{k} = \sum_{k = 1}^{n} a_{k} + a_{n + 1}$ , which is why "add the next term to both sides" was the natural move in every sum above. The dots in $a_{1} + a_{2} + \dots + a_{n}$ are an informal abbreviation of this definition.

A property of a recursively defined object is proved by induction, and the proof's step follows the definition's step. Here is a law of exponents, the kind of rule school takes for granted.

Proposition. For every real number $a$ and all integers $m, n \geq 0$ , $a^{m + n} = a^{m} a^{n}$ .

Proof. Fix $a$ and $m$ , and induct on $n$ from $n_{0} = 0$ . For $n = 0$ , $a^{m + 0} = a^{m} = a^{m} \cdot 1 = a^{m} a^{0}$ . For the step, suppose $a^{m + n} = a^{m} a^{n}$ . Then, using the definition twice and the hypothesis once,

a^{m + (n + 1)} = a^{(m + n) + 1} = a^{m + n} \cdot a = a^{m} a^{n} \cdot a = a^{m} a^{n + 1}

So the law holds for $n + 1$ , and by induction for every $n \geq 0$ . $□$

Why does a recursive definition define anything?

The definition of $n!$ says what $0!$ is and how to get $(n + 1)!$ from $n!$ . It is tempting to say "so $n!$ is defined for every $n$ , by induction", but induction proves statements about objects that already exist, and here the object is what is in question. The precise result is the recursion theorem, proved by Dedekind in his 1888 essay: given a set $X$ , an element $c$ of $X$ , and a rule $g$ that gives an element $g (n, x)$ of $X$ for each natural number $n$ and each $x$ in $X$ , there is exactly one sequence $a_{1}, a_{2}, a_{3}, \dots$ of elements of $X$ with $a_{1} = c$ and $a_{n + 1} = g (n, a_{n})$ for every $n$ .

Uniqueness is an ordinary induction. If $a$ and $b$ are two such sequences, then $a_{1} = c = b_{1}$ , and if $a_{n} = b_{n}$ then $a_{n + 1} = g (n, a_{n}) = g (n, b_{n}) = b_{n + 1}$ . So $a_{n} = b_{n}$ for every $n$ . Existence takes more care: one proves by induction that for each $n$ there is exactly one finite list $a_{1}, \dots, a_{n}$ obeying the rules up to $n$ , checks that these lists agree wherever they overlap, and glues them into one infinite sequence. Doing that rigorously needs a sequence to be an object, a function from $ℕ$ to $X$ in the sense of the lesson on functions.

The theorem needs the rule to run from earlier values to later ones, and a "definition" that does not can fail in both possible ways. The condition $f (n) = f (n + 1)$ for every $n$ is satisfied by every constant sequence, so it defines nothing in particular. The condition $f (n) = f (n + 1) + 1$ for every $n$ , with values in $ℕ$ , is satisfied by nothing: it would make $f (1) > f (2) > f (3) > \dots$ , and the set of these values would have no least element, against well-ordering.

And sometimes nobody knows. Let $T (1) = 0$ , and for $n > 1$ let $T (n) = 1 + T (\frac{n}{2})$ when $n$ is even and $T (n) = 1 + T (3 n + 1)$ when $n$ is odd. Then $T (n)$ counts the steps the process "halve if even, otherwise triple and add one" takes to reach $1$ . From $3$ the process runs $3, 10, 5, 16, 8, 4, 2, 1$ , so $T (3) = 7$ , and from $27$ it takes $111$ steps, climbing as high as $9232$ on the way. Whether $T (n)$ is defined for every $n$ , that is, whether every starting number eventually reaches $1$ , is the Collatz conjecture, posed by Lothar Collatz in 1937 and still open. The rule for odd $n$ calls on the larger number $3 n + 1$ , so the recursion theorem does not apply, and no substitute for it has been found.

The most famous recursive sequence has a two-step rule. The Fibonacci numbers are defined by

F_{1} = 1, F_{2} = 1, F_{n + 2} = F_{n + 1} + F_{n} for every n \geq 1

so the sequence runs $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dots$ , each term the sum of the two before. They are named after Leonardo of Pisa, called Fibonacci, whose Liber Abaci of 1202 counted pairs of breeding rabbits with them. Because the rule reaches back two places, proofs about them are typically strong inductions with two base cases.

For instance, $F_{n} < 2^{n}$ for every $n$ . The base cases are $F_{1} = 1 < 2$ and $F_{2} = 1 < 4$ . For the step, let $n \geq 2$ and suppose $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}$ . The step starts at $n = 2$ because at $n = 1$ it would call on $F_{0}$ , which the definition does not provide, so $F_{2}$ has to be checked by hand.

The bound is generous: $F_{30} = 832 040$ against $2^{30} = 1 073 741 824$ . The true growth rate comes from the number $φ = \frac{1 + \sqrt{5}}{2} \approx 1.618$ , which satisfies $φ^{2} = φ + 1$ . The same two-base induction shows $φ^{n - 2} \leq F_{n} \leq φ^{n - 1}$ for every $n$ : the bases are $φ^{- 1} \leq 1 \leq 1$ and $1 \leq 1 \leq φ$ , and for the step, $φ^{n - 2} + φ^{n - 3} = φ^{n - 3} (φ + 1) = φ^{n - 1}$ , and in the same way $φ^{n - 1} + φ^{n - 2} = φ^{n}$ . So the Fibonacci numbers grow like powers of $φ$ , and the Discrete Mathematics lesson on linear recurrences derives the exact formula, $F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}$ with $ψ = \frac{1 - \sqrt{5}}{2}$ .

Identities between Fibonacci numbers are a good training ground, because the recursion is the only tool and the step has to be found in it.

Example. Prove that $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1$ for every natural number $n$ .

Let $P (n)$ be the statement $\sum_{k = 1}^{n} F_{k} = F_{n + 2} - 1$ . For the base case, the left side is $F_{1} = 1$ and the right side is $F_{3} - 1 = 2 - 1 = 1$ .

For the step, let $n$ be a natural number and suppose $\sum_{k = 1}^{n} F_{k} = F_{n + 2} - 1$ . The target is $\sum_{k = 1}^{n + 1} F_{k} = F_{n + 3} - 1$ . By the definition of the sum, the hypothesis, and then the Fibonacci rule,

\sum_{k = 1}^{n + 1} F_{k} = \sum_{k = 1}^{n} F_{k} + F_{n + 1} = F_{n + 2} - 1 + F_{n + 1} = F_{n + 3} - 1

So $P (n + 1)$ holds, and by induction the identity holds for every $n$ . As a check, $1 + 1 + 2 + 3 + 5 = 12 = F_{7} - 1 = 13 - 1$ .

Only one earlier case was needed, so this was an ordinary induction; the two-place reach of the Fibonacci rule was absorbed by the two Fibonacci numbers already present in the hypothesis.

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

Answer

Let $P (n)$ be the statement $\sum_{k = 1}^{n} F_{k}^{2} = F_{n} F_{n + 1}$ . For the base case, $F_{1}^{2} = 1 = F_{1} F_{2}$ .

For the step, let $n$ be a natural number and suppose $\sum_{k = 1}^{n} F_{k}^{2} = F_{n} F_{n + 1}$ . The target is $\sum_{k = 1}^{n + 1} F_{k}^{2} = F_{n + 1} F_{n + 2}$ . Now

\sum_{k = 1}^{n + 1} F_{k}^{2} = F_{n} F_{n + 1} + F_{n + 1}^{2} = F_{n + 1} (F_{n} + F_{n + 1}) = F_{n + 1} F_{n + 2}

using the hypothesis, then factoring out $F_{n + 1}$ , then the Fibonacci rule. So $P (n + 1)$ holds, and by induction the identity holds for every $n$ .

The identity has a picture. Squares of sides $1, 1, 2, 3, 5, \dots, F_{n}$ , each placed against the long side of the rectangle formed by the ones before, fill an $F_{n}$ by $F_{n + 1}$ rectangle exactly; for $n = 5$ , the areas $1 + 1 + 4 + 9 + 25 = 40 = 5 \times 8$ .

Loading the induction

Sometimes a true statement cannot be proved by induction as it stands, and a stronger statement can. This sounds backwards, since a stronger statement says more and should be harder to prove. But in an induction the statement plays two parts: it is the conclusion of the step, and it is also the hypothesis. Strengthening it makes the target harder, and it also makes the hypothesis more useful, and the second effect often wins. George Pólya, in How to Solve It (1945), called this the inventor's paradox: the more ambitious plan may have the better chance of success. Strengthening the statement to be proved is also called loading the induction.

Example. Prove that $\sum_{k = 1}^{n} \frac{1}{k^{2}} < 2$ for every natural number $n$ .

First try the claim as it stands. The base case is $1 < 2$ . For the step, suppose $\sum_{k = 1}^{n} \frac{1}{k^{2}} < 2$ ; then

\sum_{k = 1}^{n + 1} \frac{1}{k^{2}} = \sum_{k = 1}^{n} \frac{1}{k^{2}} + \frac{1}{(n + 1)^{2}} < 2 + \frac{1}{(n + 1)^{2}}

and that is not less than $2$ . The step fails, and it has to: the hypothesis "less than $2$ " allows the sum to be $1.9999$ , and then adding a term of $\frac{1}{4}$ would break the bound. The hypothesis does not say how much room is left below $2$ , and the step needs exactly that information.

So put the room into the statement. Let $P (n)$ be the statement

\sum_{k = 1}^{n} \frac{1}{k^{2}} \leq 2 - \frac{1}{n}

This implies the original claim, since $2 - \frac{1}{n} < 2$ . For the base case, both sides are $1$ . For the step, let $n$ be a natural number and suppose $P (n)$ . The target is $\sum_{k = 1}^{n + 1} \frac{1}{k^{2}} \leq 2 - \frac{1}{n + 1}$ . By the hypothesis,

\sum_{k = 1}^{n + 1} \frac{1}{k^{2}} \leq 2 - \frac{1}{n} + \frac{1}{(n + 1)^{2}}

so it is enough to show $- \frac{1}{n} + \frac{1}{(n + 1)^{2}} \leq - \frac{1}{n + 1}$ , that is, $\frac{1}{(n + 1)^{2}} \leq \frac{1}{n} - \frac{1}{n + 1}$ . The right side is $\frac{(n + 1) - n}{n (n + 1)} = \frac{1}{n (n + 1)}$ , and $n (n + 1) < (n + 1)^{2}$ , so $\frac{1}{(n + 1)^{2}} < \frac{1}{n (n + 1)}$ . Hence $P (n + 1)$ holds, and by induction $P (n)$ holds for every $n$ . In particular every sum $\sum_{k = 1}^{n} \frac{1}{k^{2}}$ is less than $2$ .

Where did $2 - \frac{1}{n}$ come from? From asking what the step needs. A bound of the form $2 - g (n)$ carries itself forward when $g (n) - g (n + 1) \geq \frac{1}{(n + 1)^{2}}$ : the room lost in one step must cover the new term. The choice $g (n) = \frac{1}{n}$ loses $\frac{1}{n (n + 1)}$ per step, which is just enough, and $g (1) = 1$ makes the base case work. That calculation, done on scrap paper, is how loaded statements are found. The sums themselves approach $\frac{π^{2}}{6} \approx 1.645$ , a value found by Leonhard Euler in the 1730s, but no bound of that precision is needed to prove that they stay below $2$ .

Now you. Prove that $\sum_{k = 1}^{n} \frac{1}{k^{3}} < \frac{3}{2}$ for every natural number $n$ , by proving the stronger statement $\sum_{k = 1}^{n} \frac{1}{k^{3}} \leq \frac{3}{2} - \frac{1}{2 n^{2}}$ .

Answer

Let $P (n)$ be $\sum_{k = 1}^{n} \frac{1}{k^{3}} \leq \frac{3}{2} - \frac{1}{2 n^{2}}$ . Since $\frac{1}{2 n^{2}} > 0$ , $P (n)$ implies the claim.

For the base case, the left side is $1$ and the right side is $\frac{3}{2} - \frac{1}{2} = 1$ .

For the step, let $n$ be a natural number and suppose $P (n)$ . By the hypothesis,

\sum_{k = 1}^{n + 1} \frac{1}{k^{3}} \leq \frac{3}{2} - \frac{1}{2 n^{2}} + \frac{1}{(n + 1)^{3}}

and the target is $\frac{3}{2} - \frac{1}{2 (n + 1)^{2}}$ . So it is enough to show

\frac{1}{(n + 1)^{3}} + \frac{1}{2 (n + 1)^{2}} \leq \frac{1}{2 n^{2}}

Multiplying both sides by the positive number $2 n^{2} (n + 1)^{3}$ , a reversible step, this is $2 n^{2} + n^{2} (n + 1) \leq (n + 1)^{3}$ , that is, $n^{3} + 3 n^{2} \leq n^{3} + 3 n^{2} + 3 n + 1$ , which is true because $3 n + 1 > 0$ . So $P (n + 1)$ holds, and by induction $P (n)$ holds for every $n$ .

The unloaded claim fails in the step for the same reason as in the Example: "less than $\frac{3}{2}$ " says nothing about how much room is left. The sums approach about $1.202$ .

Loading is not only for inequalities. The sum of the first $n$ odd numbers, earlier in the lesson, was a loaded statement: "is a perfect square" could not carry itself forward, and "is $n^{2}$ " could. The Fibonacci bounds were another: to show only that $F_{n}$ is positive would be easy, but to learn how fast it grows, the statement had to carry a precise bound. A useful rule of thumb follows. When an inductive step fails because the hypothesis is too vague, do not give up on induction; ask what extra information the step would need, and put it into the statement.

Three forms of one principle

The lesson has now met three principles about $ℕ$ : well-ordering, ordinary induction and strong induction. They are not three facts but one fact in three forms.

Theorem. The well-ordering principle, the principle of induction and the principle of strong induction are equivalent: each implies the other two.

Proof. It is enough to prove three implications in a cycle, as the lesson on direct proof explained for lists of equivalent statements. Well-ordering implies induction by the theorem in the section on why induction works, and induction implies strong induction by the theorem in the section on strong induction. It remains to show that strong induction implies well-ordering.

Assume the principle of strong induction, and let $A$ be a set of natural numbers with no least element. We show that $A$ is empty; this is the contrapositive of well-ordering. Let $P (n)$ be the statement " $n \notin A$ ".

Base case: if $1$ were in $A$ , it would be the least element of $A$ , since $1 \leq m$ for every natural number $m$ . As $A$ has no least element, $1 \notin A$ , so $P (1)$ holds.

Step: let $n$ be a natural number and suppose $P (1), \dots, P (n)$ , that is, none of $1, 2, \dots, n$ is in $A$ . If $n + 1$ were in $A$ , then every element $m$ of $A$ would satisfy $m \geq n + 1$ , since a natural number less than $n + 1$ is one of $1, \dots, n$ . So $n + 1$ would be the least element of $A$ , which does not exist. Hence $n + 1 \notin A$ , and $P (n + 1)$ holds.

By strong induction, $n \notin A$ for every natural number $n$ , so $A$ is empty. Thus every non-empty set of natural numbers has a least element. $□$

The proofs in the cycle used a few basic facts about $ℕ$ besides the three principles: $1$ is the least natural number, every natural number other than $1$ is $m + 1$ for some natural number $m$ , and no natural number lies strictly between $n$ and $n + 1$ . With those facts taken as known, each principle can stand in for the others, and which to use is a question of convenience.

Use ordinary induction when case $n + 1$ follows from case $n$ , as for sums, most inequalities and most divisibility claims. Use strong induction when case $n + 1$ depends on some earlier case whose position is not fixed, as for factorisations, or on a fixed number of earlier cases, as for the Fibonacci numbers and the stamps. Use the smallest counterexample when the natural argument is "a failure would force a smaller failure". A classic of the last kind is Pierre de Fermat's method of infinite descent, which shows that something cannot exist by showing that any example would produce a smaller one.

Here is descent applied to $\sqrt{2}$ , a proof quite different from the previous lesson's. Suppose $\sqrt{2}$ is rational. Then the set of natural numbers $b$ such that $b \sqrt{2}$ is an integer is non-empty, so it has a least element $b$ ; let $a = b \sqrt{2}$ , a natural number. Since $1 < \sqrt{2} < 2$ , we have $b < a < 2 b$ , so $a - b$ is a natural number less than $b$ . Now

(a - b) \sqrt{2} = a \sqrt{2} - b \sqrt{2} = 2 b - a

since $a \sqrt{2} = b \sqrt{2} \cdot \sqrt{2} = 2 b$ and $b \sqrt{2} = a$ . So $(a - b) \sqrt{2}$ is an integer. Then $a - b$ is a smaller natural number with the same property, contradicting the choice of $b$ . So $\sqrt{2}$ is irrational. The proof never mentions parity; it uses only the ordering of $ℕ$ .

How can three true statements be "equivalent"?

In ordinary logic, any two true statements are equivalent, since $P ⟺ Q$ is true whenever both are true, so "well-ordering is equivalent to induction" cannot mean only that. What it means is: from the basic facts listed after the proof, well-ordering can be derived from induction and induction from well-ordering. So in any structure where the basic facts hold, the three principles stand or fall together.

A structure where they fall together makes this concrete. Take $ℕ$ followed by a copy of the integers: the numbers $1, 2, 3, \dots$ , and after all of them, further elements $\dots, c_{- 1}, c_{0}, c_{1}, \dots$ , with every $c_{i}$ counted larger than every natural number, $c_{i} < c_{j}$ when $i < j$ , and " $x + 1$ " meaning the next element, so $c_{i} + 1 = c_{i + 1}$ . Every basic fact still holds. The first element is $1$ ; every other element has a predecessor, since $c_{i} = c_{i - 1} + 1$ ; and nothing lies strictly between $x$ and $x + 1$ . But all three principles fail. The set ${\dots, c_{- 1}, c_{0}, c_{1}, \dots}$ is non-empty and has no least element, so well-ordering fails. The statement " $x$ is one of $1, 2, 3, \dots$ " holds at $1$ and passes from $x$ to $x + 1$ , but fails at $c_{0}$ , so induction fails. And strong induction fails for the same statement.

Structures like this are not idle inventions. Thoralf Skolem showed in 1934 that the first-order axioms of arithmetic, which can state induction only one formula at a time, cannot rule out such extra elements: there are "non-standard models" of arithmetic whose order begins with a copy of $ℕ$ and continues with blocks like the one above. Inside ordinary mathematics, the second-order induction axiom, about all sets of natural numbers, is what excludes them, and it is the version this course uses.

Structural induction, a first look

Induction is not really about numbers. It is about things built up in stages from starting pieces by fixed rules, and the natural numbers are the simplest such things: one starting piece, $1$ , and one rule, "add $1$ ". Other objects are built the same way, and they have their own induction.

The formulas of propositional logic, from the lesson on statements and connectives, are the standard example. They are defined recursively, by rules for building them. Each variable $p$ , $q$ , $r$ , and so on, is a formula. If $φ$ is a formula, so is $\neg φ$ . If $φ$ and $ψ$ are formulas, so are $(φ \land ψ)$ and $(φ \lor ψ)$ . And nothing is a formula unless it is produced by these rules.

So $((p \land q) \lor \neg r)$ is a formula: $p$ , $q$ and $r$ are formulas, hence $(p \land q)$ and $\neg r$ are, hence the whole. The string $p \land \lor q$ is not, since no rule produces it.

The principle of structural induction. To prove that every formula has a property, prove that every variable has it (the base case), and prove that the rules preserve it: if $φ$ and $ψ$ have the property, then so do $\neg φ$ , $(φ \land ψ)$ and $(φ \lor ψ)$ (the inductive steps, one per rule).

Proposition. Every formula contains as many left brackets as right brackets.

Proof. By structural induction. For a formula $φ$ write $L (φ)$ and $R (φ)$ for its numbers of left and right brackets. A variable has no brackets, so $L = R = 0$ . If $L (φ) = R (φ)$ , then $\neg φ$ has the same brackets as $φ$ , so $L (\neg φ) = R (\neg φ)$ . If $L (φ) = R (φ)$ and $L (ψ) = R (ψ)$ , then

L ((φ \land ψ)) = L (φ) + L (ψ) + 1 = R (φ) + R (ψ) + 1 = R ((φ \land ψ))

and the same holds for $(φ \lor ψ)$ . So every rule preserves the property, and every formula has it. $□$

The same method shows that in every formula the number of occurrences of variables is one more than the number of occurrences of $\land$ and $\lor$ together. A variable has $1$ and $0$ . The rule for $\neg$ changes neither count. And if $φ$ and $ψ$ have $b + 1$ and $b' + 1$ variable occurrences against $b$ and $b'$ binary connectives, then $(φ \land ψ)$ has $b + b' + 2$ variable occurrences against $b + b' + 1$ connectives. So $((p \land q) \lor \neg r)$ , with three variables, has two binary connectives, as it does.

These look like small facts, and they are the first steps of real theorems. The bracket count, sharpened a little, proves that every formula can be read in only one way, which is what allows the truth value of a formula to be defined recursively from the truth values of its parts. Structural induction is also the everyday tool of computer science, where lists, trees, expressions and programs are all built by rules like these, and where a function defined by recursion on such an object is proved correct by induction on the same structure.

Is structural induction a new principle, or ordinary induction in disguise?

For formulas it is strong induction on length. Let $Q$ be a property that holds for every variable and is preserved by the three rules, and let $P (n)$ be the statement "every formula with exactly $n$ symbols has $Q$ ", counting variables, connectives and brackets as symbols. By the last clause of the definition, every formula is a variable or is produced by a rule from shorter formulas. A formula with $n$ symbols is therefore a variable (and then $n = 1$ ), or $\neg φ$ with $φ$ of $n - 1$ symbols, or $(φ \land ψ)$ or $(φ \lor ψ)$ with $φ$ and $ψ$ together of $n - 3$ symbols. In every case the parts have fewer than $n$ symbols. So if $P (k)$ holds for every $k < n$ , the parts have $Q$ , the rule preserves it, and the formula has $Q$ . That is a strong inductive step, and the case $n = 1$ is the base case, so $P (n)$ holds for every $n$ and every formula has $Q$ .

The last clause, "nothing else is a formula", is what makes this work. Without it, some object could count as a formula without being built from shorter ones, and the induction would never reach it. It plays the same part as the Peano axiom that nothing is a natural number except what can be reached from $1$ .

The general form of the idea is well-founded induction. Suppose objects are compared by a relation "is simpler than" under which there is no infinite chain, each object simpler than the one before. Then any property that holds for an object whenever it holds for all simpler objects holds for every object. Ordinary induction is the case of $ℕ$ with its usual order, structural induction is the case of formulas ordered by "is a part of", and the smallest counterexample argument is the same idea viewed from the other side: a counterexample would have to have a simplest counterexample, and the argument shows it cannot. The lesson on order relations returns to orders with no infinite descending chains.

Every proof in this lesson used collections without saying what they are. The proof that induction works took "the set of natural numbers where $P$ fails" and asked for its least element. The horses came in groups, and were removed from them. The formulas were a collection defined by rules. The next lesson makes those words exact: sets, how to build them, and how to prove that two of them are equal.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. Prove that $\sum_{k = 1}^{n} k (k + 1) = \frac{n (n + 1) (n + 2)}{3}$ for every natural number $n$ .

Solution

Let $P (n)$ be the formula. For the base case, the left side is $1 \times 2 = 2$ and the right side is $\frac{1 \times 2 \times 3}{3} = 2$ .

For the step, let $n$ be a natural number and suppose $P (n)$ . The target is $\sum_{k = 1}^{n + 1} k (k + 1) = \frac{(n + 1) (n + 2) (n + 3)}{3}$ . By the hypothesis,

\sum_{k = 1}^{n + 1} k (k + 1) = \frac{n (n + 1) (n + 2)}{3} + (n + 1) (n + 2) = \frac{(n + 1) (n + 2) (n + 3)}{3}

taking out the common factor $\frac{(n + 1) (n + 2)}{3}$ . So $P (n + 1)$ holds, and by induction $P (n)$ holds for every natural number $n$ .

2. Prove that $\sum_{k = 1}^{n} \frac{1}{k (k + 1)} = \frac{n}{n + 1}$ for every natural number $n$ .

Solution

Let $P (n)$ be the formula. For the base case, both sides equal $\frac{1}{2}$ .

For the step, let $n$ be a natural number and suppose $P (n)$ . By the hypothesis,

\sum_{k = 1}^{n + 1} \frac{1}{k (k + 1)} = \frac{n}{n + 1} + \frac{1}{(n + 1) (n + 2)} = \frac{n (n + 2) + 1}{(n + 1) (n + 2)} = \frac{(n + 1)^{2}}{(n + 1) (n + 2)} = \frac{n + 1}{n + 2}

which is $P (n + 1)$ . By induction, $P (n)$ holds for every natural number $n$ . (Since $\frac{1}{k (k + 1)} = \frac{1}{k} - \frac{1}{k + 1}$ , the sum also telescopes to $1 - \frac{1}{n + 1}$ .)

3. Prove that $7 ∣ 3^{2 n + 1} + 2^{n + 2}$ for every natural number $n$ .

Solution

Let $P (n)$ be the statement. For the base case, $3^{3} + 2^{3} = 27 + 8 = 35 = 7 \times 5$ .

For the step, let $n$ be a natural number and suppose $3^{2 n + 1} + 2^{n + 2} = 7 k$ for some integer $k$ . Then

3^{2 n + 3} + 2^{n + 3} = 9 \cdot 3^{2 n + 1} + 2 \cdot 2^{n + 2} = 9 (3^{2 n + 1} + 2^{n + 2}) - 7 \cdot 2^{n + 2} = 7 (9 k - 2^{n + 2})

and $9 k - 2^{n + 2}$ is an integer, so $P (n + 1)$ holds. By induction, $P (n)$ holds for every natural number $n$ .

4. A sequence is defined by $a_{1} = 1$ and $a_{n + 1} = 2 a_{n} + 1$ for $n \geq 1$ . Compute $a_{1}$ to $a_{5}$ , guess a formula for $a_{n}$ , and prove it.

Solution

The first terms are $a_{1} = 1$ , $a_{2} = 3$ , $a_{3} = 7$ , $a_{4} = 15$ , $a_{5} = 31$ , each one less than a power of $2$ . The guess is $a_{n} = 2^{n} - 1$ .

Let $P (n)$ be $a_{n} = 2^{n} - 1$ . For the base case, $a_{1} = 1 = 2^{1} - 1$ . For the step, let $n$ be a natural number and suppose $a_{n} = 2^{n} - 1$ . By the recursive definition and the hypothesis, $a_{n + 1} = 2 a_{n} + 1 = 2 (2^{n} - 1) + 1 = 2^{n + 1} - 1$ , which is $P (n + 1)$ . By induction, $a_{n} = 2^{n} - 1$ for every natural number $n$ .

This is the number of moves needed for the Tower of Hanoi with $n$ discs, which satisfies the same recursion.

Core

5. Prove that $1^{3} + 2^{3} + \dots + n^{3} = \frac{n^{2} (n + 1)^{2}}{4}$ for every natural number $n$ , and deduce that $1^{3} + 2^{3} + \dots + n^{3} = (1 + 2 + \dots + n)^{2}$ .

Hint

In the step, both the old right side and the new term contain the factor $(n + 1)^{2}$ . Take it out before expanding anything.

Solution

Let $P (n)$ be the statement $\sum_{k = 1}^{n} k^{3} = \frac{n^{2} (n + 1)^{2}}{4}$ . For the base case, both sides equal $1$ , since $\frac{1 \times 4}{4} = 1$ .

For the step, let $n$ be a natural number and suppose $P (n)$ . The target is $\sum_{k = 1}^{n + 1} k^{3} = \frac{(n + 1)^{2} (n + 2)^{2}}{4}$ . By the hypothesis,

\sum_{k = 1}^{n + 1} k^{3} = \frac{n^{2} (n + 1)^{2}}{4} + (n + 1)^{3} = \frac{(n + 1)^{2} (n^{2} + 4 n + 4)}{4} = \frac{(n + 1)^{2} (n + 2)^{2}}{4}

which is the target. By induction, $P (n)$ holds for every natural number $n$ .

For the deduction, the Example in the section on sums gives $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ , whose square is $\frac{n^{2} (n + 1)^{2}}{4}$ . So the sum of the first $n$ cubes is the square of the sum of the first $n$ numbers; for $n = 4$ , $1 + 8 + 27 + 64 = 100 = 10^{2}$ .

6. Find the flaw in this proof.

Claim. For every non-zero real number $a$ and every integer $n \geq 0$ , $a^{n} = 1$ .

Proof. By strong induction on $n$ , starting at $0$ . For the base case, $a^{0} = 1$ by definition. For the step, let $n \geq 0$ and suppose $a^{k} = 1$ for every integer $k$ with $0 \leq k \leq n$ . Then

a^{n + 1} = \frac{a^{n} \cdot a^{n}}{a^{n - 1}} = \frac{1 \times 1}{1} = 1

so the claim holds for $n + 1$ . By strong induction, $a^{n} = 1$ for every $n \geq 0$ .

Hint

Run the step by hand at the smallest value of $n$ it has to cover, and ask which cases it calls on.

Solution

The claim is false: $2^{1} = 2$ . The base case is correct, so the step must fail somewhere.

The step for $n$ uses the inductive hypothesis at $k = n$ and at $k = n - 1$ . For $n \geq 1$ both lie in the range $0 \leq k \leq n$ , and the step is valid there: from $a^{n} = 1$ and $a^{n - 1} = 1$ it correctly deduces $a^{n + 1} = 1$ . But the step must also cover $n = 0$ , the passage from $a^{0}$ to $a^{1}$ , and there it uses $a^{- 1} = 1$ . The case $k = - 1$ is not in the range $0 \leq k \leq 0$ , so the hypothesis says nothing about it, and indeed $a^{- 1} = \frac{1}{a}$ is not $1$ unless $a = 1$ . The algebraic identity $a^{n + 1} = \frac{a^{n} a^{n}}{a^{n - 1}}$ is true for $n = 0$ ; the failure is in replacing $a^{- 1}$ by $1$ .

So the chain breaks at its first link, exactly as in the horses: $P (0) \Rightarrow P (1)$ is not established, and every later link waits on $P (1)$ . A step that reaches back two places needs two base cases, here $n = 0$ and $n = 1$ , and $P (1)$ , which says $a = 1$ , cannot be proved.

7. Prove or disprove each claim. (a) $2^{n} \geq n^{3}$ for every integer $n \geq 10$ . (b) $2^{n} \geq n^{3}$ for every integer $n \geq 9$ .

Hint

Check the base cases first. For the step in (a), reduce the target to an inequality between polynomials in $n$ and use $n \geq 10$ to compare their leading terms.

Solution

(b) is false: $2^{9} = 512$ and $9^{3} = 729$ , so $n = 9$ is a counterexample.

(a) is true. Let $P (n)$ be $2^{n} \geq n^{3}$ . For the base case, $2^{10} = 1024 \geq 1000 = 10^{3}$ .

For the step, let $n \geq 10$ and suppose $2^{n} \geq n^{3}$ . Then $2^{n + 1} = 2 \cdot 2^{n} \geq 2 n^{3}$ , so it is enough to show $2 n^{3} \geq (n + 1)^{3} = n^{3} + 3 n^{2} + 3 n + 1$ , that is, $n^{3} \geq 3 n^{2} + 3 n + 1$ . Since $n \geq 10$ ,

n^{3} \geq 10 n^{2} = 3 n^{2} + 7 n^{2} \geq 3 n^{2} + 70 n > 3 n^{2} + 3 n + 1

using $n^{2} \geq 10 n$ and $70 n > 3 n + 1$ . So $2^{n + 1} \geq (n + 1)^{3}$ , and by induction $P (n)$ holds for every $n \geq 10$ .

The two parts together show that the base case, not the step, fixes where the claim starts: $n = 10$ is the least $n$ from which the inequality holds for good. (It also holds at $n = 1$ , where $2 \geq 1$ , and fails for $n = 2$ to $9$ .)

8. Prove that every natural number can be written as a sum of distinct powers of $2$ (the powers $2^{0} = 1$ , $2^{1} = 2$ , $2^{2} = 4$ , and so on, each used at most once), and that this can be done in only one way, apart from the order of the terms.

Hint

For existence, use strong induction: subtract the largest power of $2$ that does not exceed $n$ . For uniqueness, first show that distinct powers of $2$ that are all less than $2^{m}$ add up to less than $2^{m}$ .

Solution

Existence. Let $P (n)$ be " $n$ is a sum of distinct powers of $2$ ". We use strong induction. For the base case, $1 = 2^{0}$ .

For the step, let $n$ be a natural number, suppose $P (k)$ for every $k \leq n$ , and consider $n + 1$ . The powers of $2$ that do not exceed $n + 1$ include $2^{0}$ , and there are finitely many of them, since $2^{j} > j \geq n + 1$ once $j \geq n + 1$ (an easy induction shows $2^{j} > j$ for all $j$ ). Let $2^{m}$ be the largest, so $2^{m} \leq n + 1 < 2^{m + 1}$ . If $n + 1 = 2^{m}$ , we are done. Otherwise let $r = n + 1 - 2^{m}$ . Then $1 \leq r$ , and $r < 2^{m + 1} - 2^{m} = 2^{m}$ , and $r \leq n$ since $2^{m} \geq 1$ . By the hypothesis, $r$ is a sum of distinct powers of $2$ , each at most $r$ and therefore less than $2^{m}$ . Adding $2^{m}$ to that sum gives $n + 1$ as a sum of distinct powers of $2$ , since $2^{m}$ is not among the others. By strong induction, $P (n)$ holds for every $n$ .

A lemma. For every integer $m \geq 0$ , $2^{0} + 2^{1} + \dots + 2^{m - 1} = 2^{m} - 1$ (for $m = 0$ the sum is empty and both sides are $0$ ). This is an induction on $m$ : if the sum up to $2^{m - 1}$ is $2^{m} - 1$ , adding $2^{m}$ gives $2^{m + 1} - 1$ . So any collection of distinct powers of $2$ all less than $2^{m}$ has sum at most $2^{m} - 1$ , which is less than $2^{m}$ .

Uniqueness. Suppose some natural number is the sum of the powers in a set $S$ and also of the powers in a different set $T$ . Remove from both the powers they have in common. The two sums stay equal, the remaining sets $S'$ and $T'$ have no power in common, and they are not both empty, since $S \neq T$ . Let $2^{m}$ be the largest power in $S' \cup T'$ , and without loss of generality say it lies in $S'$ (the situation is symmetric in $S$ and $T$ ). Every power in $T'$ is then different from $2^{m}$ and at most $2^{m}$ , so less than $2^{m}$ , and by the lemma the sum of $T'$ is less than $2^{m}$ , which is at most the sum of $S'$ . That contradicts the equality of the sums. So the representation is unique.

This is the binary representation of $n$ : for example $13 = 8 + 4 + 1$ , written $1101$ in base $2$ .

9. Let $p_{n} = \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{5}{6} \dots \frac{2 n - 1}{2 n}$ . Prove that $p_{n} < \frac{1}{\sqrt{3 n}}$ for every natural number $n$ .

Hint

First try the claim as it stands, and see that the step fails. Then prove the stronger statement $p_{n} \leq \frac{1}{\sqrt{3 n + 1}}$ . Squaring is reversible for positive quantities.

Solution

A direct induction fails. From $p_{n} < \frac{1}{\sqrt{3 n}}$ the step would need $\frac{1}{\sqrt{3 n}} \cdot \frac{2 n + 1}{2 n + 2} \leq \frac{1}{\sqrt{3 n + 3}}$ , which after squaring and clearing denominators is $(2 n + 1)^{2} (3 n + 3) \leq 3 n (2 n + 2)^{2}$ , that is, $12 n^{3} + 24 n^{2} + 15 n + 3 \leq 12 n^{3} + 24 n^{2} + 12 n$ , which is false for every $n$ . So load the induction.

Let $P (n)$ be $p_{n} \leq \frac{1}{\sqrt{3 n + 1}}$ . For the base case, $p_{1} = \frac{1}{2} = \frac{1}{\sqrt{4}}$ .

For the step, let $n$ be a natural number and suppose $P (n)$ . Since $p_{n + 1} = p_{n} \cdot \frac{2 n + 1}{2 n + 2}$ and the factor is positive,

p_{n + 1} \leq \frac{1}{\sqrt{3 n + 1}} \cdot \frac{2 n + 1}{2 n + 2}

and it is enough to show that the right side is at most $\frac{1}{\sqrt{3 n + 4}}$ . Both are positive, so this is equivalent to the inequality between their squares, and clearing the positive denominators, to

(2 n + 1)^{2} (3 n + 4) \leq (2 n + 2)^{2} (3 n + 1)

The left side expands to $12 n^{3} + 28 n^{2} + 19 n + 4$ and the right side to $12 n^{3} + 28 n^{2} + 20 n + 4$ , so the inequality says $19 n \leq 20 n$ , which is true. Hence $P (n + 1)$ holds, and by induction $P (n)$ holds for every natural number $n$ .

Finally, $3 n + 1 > 3 n$ gives $\frac{1}{\sqrt{3 n + 1}} < \frac{1}{\sqrt{3 n}}$ , so $p_{n} < \frac{1}{\sqrt{3 n}}$ for every $n$ .

The margin in the step, $n$ out of about $12 n^{3}$ , is tiny, which is why the unloaded version failed. The true size of $p_{n}$ is close to $\frac{1}{\sqrt{π n}}$ , and since $π > 3$ , that is consistent with the bound.

10. Prove Cassini's identity: $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ for every integer $n \geq 2$ , where $F_{n}$ are the Fibonacci numbers.

Hint

In the step, use the Fibonacci rule to replace $F_{n + 2}$ by $F_{n + 1} + F_{n}$ , and later to replace $F_{n + 1} - F_{n}$ by $F_{n - 1}$ .

Solution

Let $P (n)$ be $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ . For the base case $n = 2$ , $F_{3} F_{1} - F_{2}^{2} = 2 \times 1 - 1 = 1 = (- 1)^{2}$ .

For the step, let $n \geq 2$ and suppose $P (n)$ . The target is $F_{n + 2} F_{n} - F_{n + 1}^{2} = (- 1)^{n + 1}$ . Using $F_{n + 2} = F_{n + 1} + F_{n}$ , and then $F_{n + 1} - F_{n} = F_{n - 1}$ (the Fibonacci rule again, valid since $n \geq 2$ ),

F_{n + 2} F_{n} - F_{n + 1}^{2} = F_{n + 1} F_{n} + F_{n}^{2} - F_{n + 1}^{2} = F_{n}^{2} - F_{n + 1} (F_{n + 1} - F_{n}) = F_{n}^{2} - F_{n + 1} F_{n - 1}

By the hypothesis this is $- (- 1)^{n} = (- 1)^{n + 1}$ . So $P (n + 1)$ holds, and by induction $P (n)$ holds for every $n \geq 2$ .

At $n = 6$ the identity reads $13 \times 5 - 8^{2} = 1$ , and it is behind a well-known puzzle: an $8$ by $8$ square, cut into four pieces along lines through Fibonacci lengths, seems to reassemble into a $5$ by $13$ rectangle of area $65$ . The missing unit of area hides in a thin gap along the diagonal.

11. Call a formula positive if it is built from variables using only $\land$ and $\lor$ , with the formation rules from the section on structural induction but without the rule for $\neg$ . Prove that every positive formula is true when all of its variables are true. Deduce that $\neg p$ is not logically equivalent to any positive formula, so $\land$ and $\lor$ alone are not enough to express every truth table (this makes precise the argument by which the lesson on statements and connectives proved the same result).

Hint

Use structural induction over the rules for positive formulas. For the deduction, compare a positive formula with $\neg p$ under the assignment that makes every variable true.

Solution

Fix the truth assignment $v$ that makes every variable true. We prove by structural induction that every positive formula is true under $v$ . The positive formulas are the variables, together with $(φ \land ψ)$ and $(φ \lor ψ)$ for positive $φ$ and $ψ$ , and nothing else.

Base case: a variable is true under $v$ by the choice of $v$ .

Steps: suppose $φ$ and $ψ$ are positive formulas that are both true under $v$ . Then $(φ \land ψ)$ is true under $v$ , since both its parts are, and $(φ \lor ψ)$ is true under $v$ , since at least one of its parts is.

So every positive formula is true under $v$ .

Now suppose some positive formula $χ$ were logically equivalent to $\neg p$ , that is, had the same truth value as $\neg p$ under every assignment of truth values to the variables occurring in either. Take the assignment making every variable true, $p$ included. Then $\neg p$ is false, while $χ$ is true by what was just proved, so they differ there, and they are not equivalent. Hence no positive formula is equivalent to $\neg p$ , and some truth table, the one for "not", cannot be built from $\land$ and $\lor$ alone. With $\neg$ added, every truth table can be built.

Challenge

12. An L-tromino is the shape formed by three unit squares of a $2$ by $2$ square, the fourth removed. Prove that for every natural number $n$ , a $2^{n}$ by $2^{n}$ board of unit squares with any one square removed can be covered exactly by L-trominoes, without overlaps.

Hint

Split the board of side $2^{n + 1}$ into four quarters of side $2^{n}$ . One quarter contains the removed square. Place a single tromino at the centre of the board so that each of the other three quarters also has exactly one square that is unavailable.

Solution

Let $P (n)$ be the statement that every $2^{n}$ by $2^{n}$ board with one square removed can be tiled by L-trominoes.

For the base case, a $2$ by $2$ board with one square removed is itself an L-tromino.

For the step, let $n$ be a natural number and suppose $P (n)$ . Take a $2^{n + 1}$ by $2^{n + 1}$ board with one square removed. The two lines through the centre of the board, parallel to its sides, divide it into four quarters, each a $2^{n}$ by $2^{n}$ board, and the removed square lies in exactly one of them. Each quarter has one corner square at the centre of the big board, and the three such squares belonging to the other three quarters form an L-tromino; place a tromino on them.

Now each quarter is a $2^{n}$ by $2^{n}$ board with exactly one square unavailable: the removed square in its quarter, and the square covered by the central tromino in each of the other three. By the inductive hypothesis each quarter, with its one unavailable square, can be tiled by L-trominoes. These four tilings together with the central tromino cover the whole board except the removed square, with no overlaps, since the quarters are disjoint and the central tromino lies on squares excluded from the quarters' tilings. So $P (n + 1)$ holds, and by induction $P (n)$ holds for every $n$ .

A count is consistent with this: the board has $4^{n} - 1$ squares left, and $3 ∣ 4^{n} - 1$ because $4^{n} - 1 = (4 - 1) (4^{n - 1} + \dots + 1)$ . The result appears in Solomon Golomb's 1954 paper on polyominoes.

13. The inequality between the arithmetic and geometric means says that for every natural number $n$ and all non-negative real numbers $x_{1}, \dots, x_{n}$ ,

x_{1} x_{2} \dots x_{n} \leq (\frac{x_{1} + x_{2} + \dots + x_{n}}{n})^{n}

Call this statement $A (n)$ . The lesson on direct proof proved $A (2)$ (in the form $\sqrt{x y} \leq \frac{x + y}{2}$ ). Prove $A (n)$ for every $n$ by the following route. (a) Prove $A (2^{k})$ for every natural number $k$ , by induction on $k$ . (b) Prove that $A (n)$ implies $A (n - 1)$ for every $n \geq 2$ . (c) Conclude that $A (n)$ holds for every $n$ .

Hint

For (a), split $2^{k + 1}$ numbers into two halves of $2^{k}$ , apply $A (2^{k})$ to each half and then $A (2)$ to the two averages. For (b), given $n - 1$ numbers with average $a$ , add $a$ itself as an $n$ th number.

Solution

Two facts about non-negative reals are used throughout: if $0 \leq u \leq u'$ and $0 \leq w \leq w'$ then $u w \leq u' w'$ (since $u w \leq u' w \leq u' w'$ ), and consequently, if $0 \leq u \leq u'$ then $u^{m} \leq u^{m}'$ for every natural number $m$ (by induction on $m$ ). Also $A (1)$ says $x_{1} \leq x_{1}$ , which is true.

(a) Induction on $k$ . The base case $A (2)$ says $x y \leq (\frac{x + y}{2})^{2}$ for non-negative $x$ and $y$ ; it holds because $(\frac{x + y}{2})^{2} - x y = \frac{(x - y)^{2}}{4} \geq 0$ .

For the step, suppose $A (m)$ where $m = 2^{k}$ , and let $x_{1}, \dots, x_{2 m}$ be non-negative reals. Let $a$ be the average of $x_{1}, \dots, x_{m}$ and $b$ the average of $x_{m + 1}, \dots, x_{2 m}$ ; both are non-negative, and the average of all $2 m$ numbers is $\frac{a + b}{2}$ . By $A (m)$ applied to each half, $0 \leq x_{1} \dots x_{m} \leq a^{m}$ and $0 \leq x_{m + 1} \dots x_{2 m} \leq b^{m}$ , so multiplying, $x_{1} \dots x_{2 m} \leq a^{m} b^{m} = (a b)^{m}$ . By $A (2)$ , $0 \leq a b \leq (\frac{a + b}{2})^{2}$ , so $(a b)^{m} \leq (\frac{a + b}{2})^{2 m}$ . Hence $x_{1} \dots x_{2 m} \leq (\frac{a + b}{2})^{2 m}$ , which is $A (2 m) = A (2^{k + 1})$ . By induction, $A (2^{k})$ holds for every $k$ .

(b) Let $n \geq 2$ and suppose $A (n)$ . Let $x_{1}, \dots, x_{n - 1}$ be non-negative reals with average $a = \frac{x_{1} + \dots + x_{n - 1}}{n - 1} \geq 0$ , and put $x_{n} = a$ . The average of $x_{1}, \dots, x_{n}$ is $\frac{(n - 1) a + a}{n} = a$ , so $A (n)$ gives $x_{1} \dots x_{n - 1} \cdot a \leq a^{n}$ . If $a > 0$ , dividing by $a$ gives $x_{1} \dots x_{n - 1} \leq a^{n - 1}$ , which is $A (n - 1)$ for these numbers. If $a = 0$ , then all the $x_{i}$ are $0$ , since they are non-negative with sum $0$ , and $A (n - 1)$ reads $0 \leq 0$ . So $A (n - 1)$ holds.

(c) Let $n$ be a natural number. Since $2^{n} > n$ , there is a power of $2$ at least $n$ ; let $N = 2^{n}$ . For $0 \leq j \leq N - n$ let $Q (j)$ be the statement $A (N - j)$ . Then $Q (0)$ is $A (2^{n})$ , true by (a). If $Q (j)$ holds and $j < N - n$ , then $N - j \geq n + 1 \geq 2$ , so (b) turns $A (N - j)$ into $A (N - j - 1)$ , which is $Q (j + 1)$ . By induction on $j$ (a finite run of steps), $Q (N - n)$ holds, and that is $A (n)$ .

This "forward and backward" induction is due to Augustin-Louis Cauchy, in his Cours d'analyse of 1821. The ordinary step from $A (n)$ to $A (n + 1)$ is awkward, and the detour through powers of $2$ avoids it: jumping up far and then stepping down one at a time still reaches every $n$ .

14. Prove Zeckendorf's theorem (existence part): every natural number is a sum of distinct Fibonacci numbers, taken from $F_{2}, F_{3}, F_{4}, \dots$ , no two of which are consecutive in the sequence. For example, $100 = 89 + 8 + 3 = F_{11} + F_{6} + F_{4}$ .

Hint

Use strong induction. Subtract the largest Fibonacci number $F_{k} \leq n$ and show that what is left is less than $F_{k - 1}$ , so the representation of the remainder cannot use $F_{k - 1}$ .

Solution

Call a representation of $n$ as $F_{i_{1}} + F_{i_{2}} + \dots + F_{i_{r}}$ admissible when $i_{1} > i_{2} > \dots > i_{r} \geq 2$ and $i_{j} - i_{j + 1} \geq 2$ for each $j$ . Since $F_{2} = 1 < F_{3} = 2$ and $F_{j + 1} = F_{j} + F_{j - 1} > F_{j}$ for $j \geq 3$ , the numbers $F_{2}, F_{3}, F_{4}, \dots$ are strictly increasing, so $F_{j} \geq j - 1$ for $j \geq 2$ (induction on $j$ ).

Let $P (n)$ be " $n$ has an admissible representation". We use strong induction. For the base case, $1 = F_{2}$ .

For the step, let $n$ be a natural number, suppose $P (k)$ for every $k \leq n$ , and consider $n + 1 \geq 2$ . The indices $j \geq 2$ with $F_{j} \leq n + 1$ include $2$ and are all less than $n + 3$ , since $F_{n + 3} \geq n + 2$ . Let $k$ be the largest. Then $F_{k} \leq n + 1 < F_{k + 1}$ , and $k \geq 3$ because $F_{3} = 2 \leq n + 1$ .

If $n + 1 = F_{k}$ , that is an admissible representation. Otherwise let $r = n + 1 - F_{k}$ . Then $1 \leq r \leq n$ , and

r < F_{k + 1} - F_{k} = F_{k - 1}

By the hypothesis, $r$ has an admissible representation $F_{i_{1}} + \dots + F_{i_{s}}$ . Its largest term satisfies $F_{i_{1}} \leq r < F_{k - 1}$ , and since the $F_{j}$ with $j \geq 2$ are increasing and $k - 1 \geq 2$ , this forces $i_{1} < k - 1$ , that is, $i_{1} \leq k - 2$ . So $n + 1 = F_{k} + F_{i_{1}} + \dots + F_{i_{s}}$ with $k - i_{1} \geq 2$ , which is admissible. By strong induction, every natural number has an admissible representation.

For $100$ , the largest Fibonacci number not exceeding it is $89$ , leaving $11$ ; the largest not exceeding $11$ is $8$ , leaving $3 = F_{4}$ . The representation is also unique, a fact proved by a similar induction and named after Édouard Zeckendorf.