Remove one square from an \(8\times 8\) chessboard. Sixty-three squares remain, and \(63=3\cdot 21\) , so it is at least conceivable that the remaining board can be covered exactly by \(21\) L-shaped pieces, each made of three squares meeting at a corner. Can it? Does the answer depend on which square was removed? And what about a \(16\times 16\) board, or a \(1024\times 1024\) one?
The answers are yes, no, and yes for every board whose side is a power of two. No amount of experiment could establish that, because there are infinitely many boards. What settles all of them at once is a way of arguing that passes from each case to the next: a \(16\times 16\) board is four \(8\times 8\) boards, and a solution for the smaller size can be assembled into a solution for the larger. This is proof by induction. It is the characteristic method of discrete mathematics, and this chapter develops it in three forms, shows the ways it is commonly misused, and then applies it to processes that evolve step by step, where it appears as the method of invariants.
3.1 Well-ordering and the principle of induction
Everything in this chapter rests on a single property of the natural numbers, which we take as an axiom.
Definition 3.1 (well-ordering principle). The well-ordering principle is the statement that every nonempty subset of \(\mathbb N\) has a least element. We accept it as a basic property of the natural numbers.
The principle looks innocent, but it distinguishes \(\mathbb N\) from other familiar number systems. The set of all integers has no least element, and neither does the set of positive rational numbers: for any positive rational \(q\) , the number \(q/2\) is a smaller one. Theorem 1.12 used the principle when it chose a solution with the smallest possible \(b\) .
Theorem 3.2 (principle of mathematical induction). Let \(n_0\) be an integer and let \(P(n)\) be a predicate defined for all integers \(n\ge n_0\) . Suppose that
(i) \(P(n_0)\) is true, and
(ii) for every integer \(k\ge n_0\) , if \(P(k)\) is true then \(P(k+1)\) is true.
Then \(P(n)\) is true for every integer \(n\ge n_0\) .
Proof. Suppose, for contradiction, that \(P(n)\) is false for some \(n\ge n_0\) . Then the set \(C=\{n-n_0 : n\ge n_0\text{ and }P(n)\text{ is false}\}\) is a nonempty subset of \(\mathbb N\) , so by the well-ordering principle it has a least element. Let \(m\) be the corresponding integer, so that \(m\ge n_0\) , \(P(m)\) is false, and \(P(n)\) is true for every \(n\) with \(n_0\le n<m\) .
By (i), \(m\ne n_0\) , so \(m-1\ge n_0\) . Since \(m-1<m\) , the statement \(P(m-1)\) is true. By (ii) with \(k=m-1\) , \(P(m)\) is true. This contradicts the choice of \(m\) . Hence \(P(n)\) is true for all \(n\ge n_0\) .
Condition (i) is the base case, condition (ii) is the inductive step, and the assumption \(P(k)\) made inside the inductive step is the induction hypothesis. The picture is a row of dominoes: (i) says that the first one falls, and (ii) says that each one knocks over the next.
It is essential to see what the inductive step does and does not assert. It is a universal conditional, \(\forall k\ge n_0\,(P(k)\to P(k+1))\) , and it is proved as any such statement is: take an arbitrary \(k\) , assume \(P(k)\) , derive \(P(k+1)\) . Assuming \(P(k)\) for one arbitrary \(k\) is not assuming what is to be proved, which is \(P(n)\) for all \(n\) .
A proof by induction should display its parts. State the predicate \(P(n)\) explicitly, as a statement about \(n\) with a truth value. Prove the base case. For the step, announce the induction hypothesis, write down what \(P(k+1)\) says, and derive it, marking the point where the hypothesis is used. A proof of the step that never uses the hypothesis is either not an induction or not correct.
Example 3.1: The sum of the first odd numbers
Adding the odd numbers in order gives \(1\) , \(1+3=4\) , \(1+3+5=9\) , \(1+3+5+7=16\) . The sums appear to be the squares.
Claim. For every integer \(n\ge 1\) , \(1+3+5+\dots+(2n-1)=n^{2}\) .
Proof. Let \(P(n)\) be the statement \(\sum_{i=1}^{n}(2i-1)=n^{2}\) .
Base case: \(P(1)\) says \(1=1^{2}\) , which is true.
Inductive step: let \(k\ge 1\) and assume \(P(k)\) , that is, \(\sum_{i=1}^{k}(2i-1)=k^{2}\) . The statement \(P(k+1)\) concerns the sum with one more term, and that term is \(2(k+1)-1=2k+1\) . So
where the second equality is the induction hypothesis. This is \(P(k+1)\) .
By induction, \(P(n)\) holds for all \(n\ge 1\) .
The computation started from the left side of \(P(k+1)\) and transformed it into the right side. It did not start from the equation \(P(k+1)\) and manipulate both sides, which would risk assuming the conclusion, as in the third specimen of Example 1.8. As a check on the formula, the first ten odd numbers \(1,3,\dots,19\) sum to \(100\) .
Example 3.2: A base case that is not the first number
Claim. For every integer \(n\ge 4\) , \(2^{n}<n!\) .
The restriction to \(n\ge 4\) is necessary: for \(n=1,2,3\) the two sides are \(2\) and \(1\) , \(4\) and \(2\) , \(8\) and \(6\) , and the inequality fails each time.
Proof. Let \(P(n)\) be the statement \(2^{n}<n!\) . Base case: \(P(4)\) says \(16<24\) , which is true. Inductive step: let \(k\ge 4\) and assume \(2^{k}<k!\) . Then
where the first inequality is the induction hypothesis and the second uses \(2<k+1\) . This is \(P(k+1)\) . By induction, \(P(n)\) holds for all \(n\ge 4\) .
Look again at the inductive step. The only fact about \(k\) that it used was \(2<k+1\) , which is true for every \(k\ge 2\) . So the implication \(P(k)\to P(k+1)\) is valid for \(k=2\) and \(k=3\) as well, even though \(P(2)\) and \(P(3)\) are false. There is no contradiction: a conditional with a false hypothesis is true. A valid inductive step transmits truth from one case to the next and creates none. Without a true base case there is nothing to transmit.
Induction proves inequalities with parameters as readily as identities. The next result is used in Chapter 7 to compare rates of growth.
Proposition 3.3 (Bernoulli’s inequality). For every real number \(x\ge -1\) and every \(n\in\mathbb N\) , \((1+x)^{n}\ge 1+nx\) .
Proof. Fix a real number \(x\ge -1\) and let \(P(n)\) be the statement \((1+x)^{n}\ge 1+nx\) . Base case: \(P(0)\) says \(1\ge 1\) . Inductive step: let \(k\ge 0\) and assume \((1+x)^{k}\ge 1+kx\) . Since \(x\ge -1\) , the number \(1+x\) is nonnegative, and multiplying an inequality by a nonnegative number preserves it. Hence
the last step because \(kx^{2}\ge 0\) . This is \(P(k+1)\) .
The hypothesis \(x\ge -1\) was used at exactly one point, and the proof says where. The induction is on \(n\) with \(x\) held fixed; the statement proved is “for all \(x\ge -1\) , for all \(n\) ”, and the variable carrying the induction should always be identified.
3.2 Induction on the size of an object
The predicate \(P(n)\) need not be a formula. It can be a statement about all objects of size \(n\) , and then the inductive step must show how an object of the next size is built from, or reduced to, objects of the previous size.
Theorem 3.4 (tiling a deficient board). For every integer \(n\ge 1\) , a \(2^{n}\times 2^{n}\) board from which any one square has been removed can be covered exactly, without overlap, by L-shaped pieces of three squares.
Proof. Let \(P(n)\) be the statement: for every choice of one square of the \(2^{n}\times 2^{n}\) board, the board with that square removed can be tiled by L-shaped pieces.
Base case. A \(2\times 2\) board with one square removed consists of three squares meeting at a corner; it is a single L-shaped piece. So \(P(1)\) holds.
Inductive step. Let \(k\ge 1\) and assume \(P(k)\) . Consider a \(2^{k+1}\times 2^{k+1}\) board with one square removed. Cut the board through the middle in both directions into four quadrants, each a \(2^{k}\times 2^{k}\) board. The removed square lies in exactly one quadrant. The four squares at the centre of the big board lie one in each quadrant; place a single L-shaped piece on the three central squares that belong to the quadrants not containing the removed square.
Now each of the four quadrants is a \(2^{k}\times 2^{k}\) board with exactly one square unavailable: in one quadrant the originally removed square, and in each of the other three the central square covered by the piece just placed. By the induction hypothesis, applied four times, each quadrant with its unavailable square removed can be tiled. The four tilings together with the central piece tile the big board with its square removed. So \(P(k+1)\) holds.
Two features of this proof recur in every induction on structures. First, \(P(n)\) contains a universal quantifier of its own: it speaks of every choice of removed square. The induction hypothesis was applied to quadrants whose missing squares lie in different places, so a hypothesis about only one position, chosen in advance, would not have been enough. Stating the predicate with care, including its internal quantifiers, is the main design decision in such a proof. Second, the step began with an arbitrary board of the larger size and reduced it to smaller ones. It did not start from a smaller board and enlarge it. Chapter 6 shows how the enlarging direction can go wrong.
Example 3.3: The construction carried out on a chessboard
The proof of Theorem 3.4 is a recipe. For the \(8\times 8\) board, \(n=3\) . Suppose the removed square is in the third row from the top and the sixth column from the left. Quartering the board puts that square in the upper right quadrant, so the first piece covers the central squares of the other three quadrants. Each quadrant is then a \(4\times 4\) board with one square unavailable, and the recipe is applied to each: quarter it, place a piece at its centre, and continue. At the last level each \(2\times 2\) block with one square unavailable is itself one piece.
The recipe places \(1\) piece at the top level, \(4\) at the second level, and \(16\) at the third, a total of \(1+4+16=21\) pieces, and \(21\cdot 3=63\) is the number of squares to be covered. In general the board has \(4^{n}-1\) squares after one is removed, so the tiling uses \((4^{n}-1)/3\) pieces. As a by-product, \(4^{n}-1\) is divisible by \(3\) for every \(n\ge 1\) : a fact about numbers has been proved by a fact about tilings.
3.3 Strong induction
In the inductive step of Theorem 3.2 only the immediately preceding case is assumed. Sometimes the case \(k+1\) depends on a case further back, or on several earlier cases, and it is not known in advance which.
Theorem 3.5 (strong induction). Let \(n_0\le n_1\) be integers and let \(P(n)\) be a predicate defined for all integers \(n\ge n_0\) . Suppose that
(i) \(P(n_0),P(n_0+1),\dots,P(n_1)\) are all true, and
(ii) for every integer \(k\ge n_1\) , if \(P(j)\) is true for all \(j\) with \(n_0\le j\le k\) , then \(P(k+1)\) is true.
Then \(P(n)\) is true for every integer \(n\ge n_0\) .
Proof. Let \(Q(n)\) be the statement “\(P(j)\) is true for all \(j\) with \(n_0\le j\le n\) ”. We prove \(Q(n)\) for all \(n\ge n_1\) by ordinary induction. The base case \(Q(n_1)\) is hypothesis (i). For the step, let \(k\ge n_1\) and assume \(Q(k)\) . By (ii), \(P(k+1)\) is true, and together with \(Q(k)\) this gives \(Q(k+1)\) . By Theorem 3.2, \(Q(n)\) holds for all \(n\ge n_1\) , and \(Q(n)\) includes \(P(n)\) . The cases \(n_0\le n<n_1\) are covered by (i).
Strong induction is not a stronger principle, in spite of its name; the proof shows that it follows from ordinary induction applied to a cleverer predicate. What is stronger is the hypothesis available in the inductive step. The classical application concerns primes.
Definition 3.6 (prime, composite). An integer \(p\ge 2\) is prime if its only positive divisors are \(1\) and \(p\) . An integer \(n\ge 2\) that is not prime is composite; equivalently, \(n=ab\) for some integers \(a\) and \(b\) with \(1<a<n\) and \(1<b<n\) .
Theorem 3.7 (existence of prime factorizations). Every integer \(n\ge 2\) is a prime or a product of primes.
Proof. Let \(P(n)\) be the statement “\(n\) is a prime or a product of primes”. We use strong induction with \(n_0=n_1=2\) . Base case: \(2\) is prime, so \(P(2)\) holds. Inductive step: let \(k\ge 2\) and assume \(P(j)\) for all \(2\le j\le k\) . If \(k+1\) is prime, \(P(k+1)\) holds. Otherwise \(k+1=ab\) with \(1<a<k+1\) and \(1<b<k+1\) , so \(2\le a\le k\) and \(2\le b\le k\) . By the induction hypothesis each of \(a\) and \(b\) is a prime or a product of primes, and therefore so is their product \(k+1\) .
Ordinary induction would be useless here: knowing that \(k\) factors into primes says nothing about \(k+1\) . The factors \(a\) and \(b\) of \(k+1\) could be anywhere between \(2\) and \(k\) , so the hypothesis must cover that whole range. Chapter 4 proves that the factorization is unique.
Example 3.4: Stamps of two values
Claim. Every integer \(n\ge 12\) can be written as \(n=4a+5b\) with \(a,b\in\mathbb N\) ; that is, every postage of \(12\) units or more can be made with \(4\) -unit and \(5\) -unit stamps.
Proof. Let \(P(n)\) be the statement that such \(a\) and \(b\) exist. We use strong induction with \(n_0=12\) and \(n_1=15\) .
Base cases: \(12=4\cdot 3\) , \(13=4\cdot 2+5\) , \(14=4+5\cdot 2\) , \(15=5\cdot 3\) .
Inductive step: let \(k\ge 15\) and assume \(P(j)\) for all \(12\le j\le k\) . Since \(k\ge 15\) , the integer \(k-3\) satisfies \(12\le k-3\le k\) , so \(P(k-3)\) holds: \(k-3=4a+5b\) for some \(a,b\in\mathbb N\) . Then \(k+1=4(a+1)+5b\) , which is \(P(k+1)\) .
The step reaches back four places, from \(k+1\) to \(k-3\) , and that is why four consecutive base cases are needed: with fewer, the step for some small \(k\) would refer to a case below \(12\) . The bound \(12\) cannot be lowered. The postage \(11\) cannot be made, since \(11\) , \(11-5=6\) , and \(11-10=1\) are not multiples of \(4\) . Listing all cases below \(12\) shows that the amounts that cannot be made are exactly \(1,2,3,6,7,11\) .
Example 3.5: Two base cases for a two-term recurrence
The Fibonacci numbers are defined by \(F_0=0\) , \(F_1=1\) , and \(F_n=F_{n-1}+F_{n-2}\) for \(n\ge 2\) . The sequence begins \(0,1,1,2,3,5,8,13,21,34\) .
Claim. \(F_n<2^{n}\) for every \(n\in\mathbb N\) .
Proof. Strong induction with base cases \(n=0\) and \(n=1\) : \(F_0=0<1\) and \(F_1=1<2\) . For the step, let \(k\ge 1\) and assume \(F_j<2^{j}\) for all \(0\le j\le k\) . Since \(k+1\ge 2\) , the recurrence applies:
The step used the hypothesis at \(k\) and at \(k-1\) , and \(k-1\ge 0\) because \(k\ge 1\) .
Now watch the same step misused. False claim: \(F_n=0\) for every \(n\in\mathbb N\) . Argument: “Base case: \(F_0=0\) . Step: assume \(F_j=0\) for all \(j\le k\) ; then \(F_{k+1}=F_k+F_{k-1}=0+0=0\) .” The step is sound only when the recurrence applies and both earlier terms exist, that is, for \(k\ge 1\) . It therefore needs the two base cases \(n=0\) and \(n=1\) , and the second is false, since \(F_1=1\) . The single base case that was checked does not support the first use of the step. Count how far back the step reaches, and supply that many consecutive base cases.
3.4 Three principles that are one
Induction was deduced from well-ordering, and strong induction from induction. The circle closes.
Theorem 3.8 (equivalence of the three principles). The well-ordering principle, the principle of mathematical induction, and the principle of strong induction are logically equivalent: each can be deduced from any of the others.
Proof. Theorem 3.2 deduced induction from well-ordering, and Theorem 3.5 deduced strong induction from induction. It remains to deduce well-ordering from strong induction.
Let \(S\) be a subset of \(\mathbb N\) with no least element; we show that \(S\) is empty. Let \(P(n)\) be the statement \(n\notin S\) . Base case: if \(0\) were in \(S\) it would be the least element of \(S\) , since no natural number is smaller; so \(0\notin S\) and \(P(0)\) holds. Inductive step: let \(k\ge 0\) and assume \(P(j)\) for all \(0\le j\le k\) , so that none of \(0,1,\dots,k\) is in \(S\) . If \(k+1\) were in \(S\) , it would be the least element of \(S\) . Hence \(k+1\notin S\) , which is \(P(k+1)\) . By strong induction, \(P(n)\) holds for every \(n\) , so \(S\) is empty. Therefore every nonempty subset of \(\mathbb N\) has a least element.
Because the three are equivalent, the choice among them is a matter of convenience. Use ordinary induction when case \(k+1\) visibly depends on case \(k\) . Use strong induction when it depends on earlier cases. Use well-ordering directly, in the form of a smallest counterexample, when the natural move is to take a supposed failure and produce a smaller one. The proof of Theorem 1.12 was of this last kind.
Here is the resolution of a question left open in Chapter 2.
Proposition 3.9 (finite posets have minimal elements). Every partial order on a finite nonempty set has a minimal element.
Proof. By induction on the number \(n\) of elements. If \(n=1\) , the single element is minimal. Let \(k\ge 1\) , assume the claim for sets with \(k\) elements, and let \(A\) be a set with \(k+1\) elements carrying a partial order \(\preceq\) . Choose any \(x\in A\) and let \(A'=A\setminus\{x\}\) . The restriction of \(\preceq\) to \(A'\) is a partial order on a set with \(k\) elements, so by the induction hypothesis it has a minimal element \(m\) .
If \(x\prec m\) is false, then no element of \(A\) lies strictly below \(m\) , and \(m\) is minimal in \(A\) . If \(x\prec m\) , we claim that \(x\) is minimal in \(A\) . Suppose \(y\prec x\) for some \(y\in A\) . Then \(y\ne x\) , so \(y\in A'\) , and by transitivity \(y\preceq m\) ; also \(y\ne m\) , since \(y=m\) would give \(m\prec x\prec m\) , contradicting antisymmetry. So \(y\prec m\) with \(y\in A'\) , contradicting the minimality of \(m\) in \(A'\) . Hence \(x\) is minimal in \(A\) .
Example 3.6: A shortest cycle, by smallest counterexample
In a round-robin tournament every two players meet once and one of them wins; there are no draws. A cycle of length \(r\) is a list of \(r\) different players \(p_1,p_2,\dots,p_r\) in which \(p_1\) beat \(p_2\) , \(p_2\) beat \(p_3\) , and so on, and \(p_r\) beat \(p_1\) . A cycle has length at least \(3\) , because two players meet only once.
Claim. If a round-robin tournament contains a cycle of any length, then it contains a cycle of length \(3\) .
Proof. Suppose the tournament contains a cycle. The set of lengths of its cycles is then a nonempty set of natural numbers, so it has a least element \(r\) ; let \(p_1,\dots,p_r\) be a cycle of that least length. We show \(r=3\) . Suppose instead that \(r>3\) , and consider the game between \(p_1\) and \(p_3\) . If \(p_3\) beat \(p_1\) , then \(p_1,p_2,p_3\) is a cycle of length \(3\) , which is shorter than \(r\) . If \(p_1\) beat \(p_3\) , then \(p_1,p_3,p_4,\dots,p_r\) is a cycle of length \(r-1\) . Either way there is a cycle shorter than the shortest one, a contradiction. So \(r=3\) .
The argument never constructs anything step by step. It takes an extreme object, a cycle of least length, and shows that the extreme forces the conclusion. The claim can be confirmed by brute force for small tournaments: there are \(2^{6}=64\) tournaments on four players and \(2^{10}=1024\) on five, and in every one that has a cycle there is a cycle of length \(3\) .
3.5 Inductions that go wrong
A flawed induction can be very persuasive, because its format looks rigorous. The errors fall into a few types, and the first is the most famous false proof in the subject.
Example 3.7: All horses are the same colour
False claim. In every set of \(n\ge 1\) horses, all the horses have the same colour.
Argument. “Base case: in a set of one horse, all horses have the same colour. Inductive step: assume the claim for sets of \(k\) horses, and let \(h_1,\dots,h_{k+1}\) be a set of \(k+1\) horses. By the hypothesis, the \(k\) horses \(h_1,\dots,h_k\) have one colour, and the \(k\) horses \(h_2,\dots,h_{k+1}\) have one colour. The two groups share the horses \(h_2,\dots,h_k\) , so both groups have the colour of those shared horses, and all \(k+1\) horses have the same colour.”
Diagnosis. The base case is correct. The inductive step is supposed to hold for every \(k\ge 1\) ; test it at the smallest value. For \(k=1\) there are two horses, the first group is \(\{h_1\}\) , the second group is \(\{h_2\}\) , and the list of shared horses \(h_2,\dots,h_k\) is empty. The sentence “both groups have the colour of those shared horses” has nothing to refer to. The two groups \(\{h_1,\dots,h_k\}\) and \(\{h_2,\dots,h_{k+1}\}\) overlap exactly when \(k\ge 2\) , so the step proves \(P(k)\to P(k+1)\) for \(k\ge 2\) only. The implication \(P(1)\to P(2)\) is not proved, and it is false. One broken link is enough: every domino after the first stays standing.
The repair of the argument would need \(P(2)\) as a base case, and \(P(2)\) is false. The method for finding such errors is general: when an inductive step is claimed for all \(k\ge n_0\) , run it by hand at \(k=n_0\) .
Common mistake. Omitting the base case because the step “does all the work”. Consider the claim that \(n(n+1)\) is odd for every \(n\ge 1\) . The step is flawless: \((k+1)(k+2)=k(k+1)+2(k+1)\) , and an odd number plus an even number is odd, so if \(k(k+1)\) is odd then so is \((k+1)(k+2)\) . But \(1\cdot 2=2\) is even, the base case fails, and in fact \(n(n+1)\) is even for every \(n\) . A correct step attached to a false base proves nothing.
Common mistake. Deriving a truth from \(P(k+1)\) and calling it a proof of \(P(k+1)\) . An inductive step that begins by writing down the equation to be proved and then simplifies both sides until they agree has shown only that \(P(k+1)\) implies something true. Start from one side of \(P(k+1)\) , or from the hypothesis \(P(k)\) , and arrive at \(P(k+1)\) at the end, as in Example 3.1.
3.6 Invariants and monovariants
Many discrete problems concern a process: a position that changes by permitted moves. A game, an algorithm, a sequence of rearrangements. Questions about such a process are of two kinds. Can a certain position ever be reached? Must the process eventually stop? Induction answers both, in a form adapted to processes.
Definition 3.10 (invariant). Consider a process with a set of states and a set of permitted moves, each taking one state to another. A property \(I\) of states is an invariant of the process if, whenever a state \(s\) has property \(I\) and a move takes \(s\) to \(s'\) , the state \(s'\) has property \(I\) as well.
Theorem 3.11 (invariant principle). If \(I\) is an invariant of a process and the starting state has property \(I\) , then every state reachable from the starting state by a finite sequence of moves has property \(I\) .
Proof. Let \(P(n)\) be the statement “every state reachable in exactly \(n\) moves has property \(I\) ”. \(P(0)\) holds because the only state reachable in zero moves is the starting state. If \(P(k)\) holds and a state \(s'\) is reachable in \(k+1\) moves, then \(s'\) is obtained by one move from a state \(s\) reachable in \(k\) moves; \(s\) has property \(I\) by \(P(k)\) , and so \(s'\) has it by Definition 3.10. Thus \(P(k+1)\) holds, and by induction every reachable state has property \(I\) .
The use of the principle is to prove that something is impossible. To show that a target state cannot be reached, find an invariant that holds at the start and fails at the target. Often the invariant is stated as a quantity that the moves leave unchanged, such as a parity or a remainder.
Example 3.8: The board with two corners missing
Remove two diagonally opposite corner squares from an \(8\times 8\) chessboard. The remaining \(62\) squares are to be covered by \(31\) dominoes, each covering two squares that share an edge. The count permits it. It is nevertheless impossible.
Colour the board in the usual alternating pattern. Opposite corners have the same colour, so the mutilated board has \(30\) squares of one colour, say white, and \(32\) of the other. Treat the placing of dominoes one at a time as a process whose state is the set of squares covered so far, and let \(I\) be the property “the numbers of white and of black squares covered are equal”. The empty board has property \(I\) . Two squares sharing an edge have opposite colours, so each domino covers one white and one black square, and placing it preserves \(I\) . By the invariant principle, every arrangement of non-overlapping dominoes covers equally many squares of each colour. A complete covering would cover \(30\) white and \(32\) black squares. So there is none.
A computation confirms a little more than the argument claims. Pairing squares by dominoes is a matching between white and black squares, and the largest number of dominoes that can be placed on the mutilated board without overlap is \(30\) , covering all the white squares and leaving two black ones.
Example 3.9: Erasing two numbers and writing their difference
The numbers \(1,2,\dots,10\) are written on a board. A move erases two of the numbers, say \(a\) and \(b\) , and writes \(\lvert a-b\rvert\) in their place. After nine moves a single number remains. Can it be \(0\) ?
Let \(S\) be the sum of the numbers on the board. A move changes the sum from \(S\) to \(S-a-b+\lvert a-b\rvert\) . If \(a\ge b\) the change is \(-2b\) , and otherwise it is \(-2a\) ; in both cases the sum decreases by twice the smaller number, an even amount. So the property “\(S\) is odd” is an invariant. At the start \(S=1+2+\dots+10=55\) , which is odd. By the invariant principle the sum is odd after every move, and in particular the final number, which is the final sum, is odd. It cannot be \(0\) .
The invariant says which final numbers are excluded, and nothing about which are attainable. Exhaustive search over all sequences of moves shows that the possible final numbers are exactly \(1,3,5,7,9\) : every odd value not ruled out by size occurs. An invariant gives a necessary condition for reachability; sufficiency needs a construction.
For termination a different kind of quantity is wanted, one that the moves are forced to change in one direction.
Definition 3.12 (monovariant). A monovariant of a process is a function assigning to each state a natural number, such that every move strictly decreases its value.
Theorem 3.13 (termination). A process that has a monovariant cannot continue forever: starting from a state at which the monovariant has value \(v\) , at most \(v\) moves can be made.
Proof. By induction on the number of moves, after \(n\) moves the monovariant has value at most \(v-n\) , since each move lowers a natural number by at least \(1\) . Its value is never negative, so \(n\le v\) .
Example 3.10: Sorting by adjacent swaps
A list of different numbers is to be sorted into increasing order. A move chooses two adjacent entries that are in the wrong order, the left one larger than the right, and swaps them. Does this always finish, whatever choices are made?
An inversion of a list is a pair of positions holding entries in the wrong order: the earlier entry is the larger. The list \(4,1,3,2\) has four inversions, formed by the pairs of entries \((4,1)\) , \((4,3)\) , \((4,2)\) , and \((3,2)\) . Swapping two adjacent out-of-order entries \(x\) and \(y\) removes the inversion formed by that pair and affects no other: any third entry stands on the same side of both \(x\) and \(y\) before and after the swap, so its order relative to each is unchanged. So each move lowers the number of inversions by exactly \(1\) .
The number of inversions is therefore a monovariant, and by Theorem 3.13 the process stops. It can stop only when no adjacent pair is out of order, which means the list is sorted. Moreover the number of moves is the same on every route: starting from \(4,1,3,2\) , every possible sequence of choices takes exactly \(4\) swaps. A list of \(n\) entries has at most \(n(n-1)/2\) inversions, the number of pairs of positions, so the process never needs more swaps than that.
Invariants and monovariants are the two certificates one asks of any algorithm: a preserved property that makes the final answer correct, and a decreasing quantity that makes the algorithm stop. The next chapter begins with the oldest algorithm that is still in daily use, Euclid’s method for the greatest common divisor, and its analysis consists of exactly these two certificates. A question to carry forward: if two integers are repeatedly replaced by the smaller one and the remainder of the larger on division by the smaller, what stays the same, and what decreases?
Exercises
-
Prove by induction that \(1+2+\dots+n=\frac{n(n+1)}{2}\) for every integer \(n\ge 1\) , writing out the predicate \(P(n)\) , the base case, the induction hypothesis, and the point at which the hypothesis is used.
Hint
Take \(P(n)\) to be the equation itself. The base case is \(1=\frac{1\cdot 2}{2}\) . In the step, add the new term \(k+1\) to the sum of the first \(k\) terms, replace that sum using the hypothesis, and put \(\frac{k(k+1)}{2}+(k+1)\) over a common denominator; the factor \(k+1\) comes out and leaves \(\frac{(k+1)(k+2)}{2}\) .
-
Prove by induction that \(\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}\) for every integer \(n\ge 1\) .
Solution
Let \(P(n)\) be the statement \(\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}\) .
Base case: for \(n=1\) the left side is \(1\) and the right side is \(\frac{1\cdot 2\cdot 3}{6}=1\) .
Inductive step: let \(k\ge 1\) and assume \(P(k)\) . Then, using the hypothesis for the first equality,
\[ \sum_{i=1}^{k+1}i^{2}=\frac{k(k+1)(2k+1)}{6}+(k+1)^{2}=\frac{(k+1)\bigl(k(2k+1)+6(k+1)\bigr)}{6}=\frac{(k+1)(2k^{2}+7k+6)}{6}. \]Since \(2k^{2}+7k+6=(k+2)(2k+3)\) , the sum equals \(\frac{(k+1)(k+2)(2k+3)}{6}\) . This is the right side of \(P(k+1)\) , because \((k+1)+1=k+2\) and \(2(k+1)+1=2k+3\) . By induction \(P(n)\) holds for all \(n\ge 1\) . As a check, for \(n=4\) both sides equal \(30\) .
-
Let \(r\) be a real number with \(r\ne 1\) . Prove by induction on \(n\) that \(\sum_{i=0}^{n}r^{i}=\frac{r^{n+1}-1}{r-1}\) for every \(n\in\mathbb N\) , and say where the hypothesis \(r\ne 1\) is needed.
Solution
Fix \(r\ne 1\) and let \(P(n)\) be the stated equation. Base case: for \(n=0\) the left side is \(r^{0}=1\) and the right side is \(\frac{r-1}{r-1}=1\) . Inductive step: let \(k\ge 0\) and assume \(P(k)\) . Then
\[ \sum_{i=0}^{k+1}r^{i}=\frac{r^{k+1}-1}{r-1}+r^{k+1}=\frac{r^{k+1}-1+r^{k+2}-r^{k+1}}{r-1}=\frac{r^{k+2}-1}{r-1}, \]which is \(P(k+1)\) . The hypothesis \(r\ne 1\) is needed for the formula to make sense at all, since it divides by \(r-1\) ; it is used in the base case and again when the two terms are put over the common denominator \(r-1\) . For \(r=1\) the sum is simply \(n+1\) .
-
Prove by induction that \(7^{n}-1\) is divisible by \(6\) for every \(n\in\mathbb N\) , and that \(n^{3}+2n\) is divisible by \(3\) for every \(n\in\mathbb N\) .
Solution
First claim. Let \(P(n)\) be “\(6\mid 7^{n}-1\) ”. Base case: \(7^{0}-1=0=6\cdot 0\) . Step: assume \(7^{k}-1=6m\) for an integer \(m\) . Then
\[ 7^{k+1}-1=7(7^{k}-1)+6=7\cdot 6m+6=6(7m+1), \]so \(6\mid 7^{k+1}-1\) .
Second claim. Let \(Q(n)\) be “\(3\mid n^{3}+2n\) ”. Base case: \(0^{3}+0=0\) . Step: assume \(k^{3}+2k=3m\) . Then
\[ (k+1)^{3}+2(k+1)=k^{3}+3k^{2}+3k+1+2k+2=(k^{3}+2k)+3(k^{2}+k+1)=3(m+k^{2}+k+1), \]so \(3\mid(k+1)^{3}+2(k+1)\) . In both proofs the key move is to rewrite the expression for \(k+1\) as the expression for \(k\) plus a visible multiple of the divisor, so that the hypothesis can be applied.
-
Determine all natural numbers \(n\) for which \(n^{2}<2^{n}\) is false, and prove by induction that \(n^{2}<2^{n}\) for every integer \(n\ge 5\) .
Solution
For \(n=0\) and \(n=1\) the inequality holds: \(0<1\) and \(1<2\) . For \(n=2,3,4\) it fails: \(4<4\) , \(9<8\) , and \(16<16\) are all false. We show that it holds for every \(n\ge 5\) , so the natural numbers for which it is false are exactly \(2\) , \(3\) , and \(4\) .
Base case: \(5^{2}=25<32=2^{5}\) . Inductive step: let \(k\ge 5\) and assume \(k^{2}<2^{k}\) . First, \(2k+1<k^{2}\) , because \(k^{2}-2k-1=(k-1)^{2}-2\ge 16-2>0\) . Therefore
\[ (k+1)^{2}=k^{2}+2k+1<k^{2}+k^{2}=2k^{2}<2\cdot 2^{k}=2^{k+1}, \]where the last inequality is the induction hypothesis. This is the statement for \(k+1\) .
-
Compute \(\sum_{i=1}^{n}\frac{1}{i(i+1)}\) for \(n=1,2,3,4\) , conjecture a closed formula, and prove your conjecture by induction.
Answer
The sums are \(\tfrac12,\tfrac23,\tfrac34,\tfrac45\) ; the conjecture is \(\frac{n}{n+1}\) . In the inductive step, \(\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{(k+1)^{2}}{(k+1)(k+2)}=\frac{k+1}{k+2}\) .
-
Prove by induction on \(n\) that a set with \(n\) elements has exactly \(2^{n}\) subsets, for every \(n\in\mathbb N\) . In the inductive step, single out one element and sort the subsets according to whether they contain it.
Solution
Let \(P(n)\) be the statement: every set with \(n\) elements has exactly \(2^{n}\) subsets.
Base case: the only set with \(0\) elements is \(\emptyset\) , and its only subset is itself; \(2^{0}=1\) .
Inductive step: let \(k\ge 0\) , assume \(P(k)\) , and let \(A\) be a set with \(k+1\) elements. Choose \(x\in A\) and put \(A'=A\setminus\{x\}\) , a set with \(k\) elements. Sort the subsets of \(A\) into two kinds. Those not containing \(x\) are exactly the subsets of \(A'\) , and by the hypothesis there are \(2^{k}\) of them. Those containing \(x\) correspond to the subsets of \(A'\) by the rule \(S\mapsto S\setminus\{x\}\) , which is a bijection because \(T\mapsto T\cup\{x\}\) is its inverse; so there are \(2^{k}\) of these as well. No subset is of both kinds, so \(A\) has \(2^{k}+2^{k}=2^{k+1}\) subsets. Since \(A\) was an arbitrary set with \(k+1\) elements, \(P(k+1)\) holds.
-
Suppose \(n\) straight lines are drawn in the plane so that no two are parallel and no three pass through one point. Prove by induction that they divide the plane into \(\frac{n^{2}+n+2}{2}\) regions, explaining how many regions the \((k+1)\) -st line cuts in two.
Hint
Add the \((k+1)\) -st line to a picture of \(k\) lines. It meets each old line once, because no two lines are parallel, and the \(k\) meeting points are different, because no three lines are concurrent. These \(k\) points cut the new line into \(k+1\) pieces, and each piece divides one old region in two. So the number of regions grows by \(k+1\) ; check that \(\frac{k^{2}+k+2}{2}+(k+1)\) is the formula with \(k+1\) in place of \(k\) .
-
Prove by strong induction that every integer \(n\ge 8\) can be written as \(3a+5b\) with \(a,b\in\mathbb N\) . Say how many base cases your proof needs and why, and list the positive integers that cannot be so written.
Solution
Let \(P(n)\) be the statement that \(n=3a+5b\) for some \(a,b\in\mathbb N\) . We use strong induction with base cases \(8,9,10\) .
Base cases: \(8=3+5\) , \(9=3\cdot 3\) , \(10=5\cdot 2\) .
Inductive step: let \(k\ge 10\) and assume \(P(j)\) for all \(8\le j\le k\) . Then \(8\le k-2\le k\) , so \(k-2=3a+5b\) for some \(a,b\in\mathbb N\) , and \(k+1=3(a+1)+5b\) . So \(P(k+1)\) holds.
Three base cases are needed because the step obtains \(P(k+1)\) from \(P(k-2)\) , three places back; for \(k+1=11,12,13\) the case it refers to is \(8,9,10\) respectively, and these must have been established directly.
The positive integers that cannot be written this way are \(1,2,4,7\) . For instance \(7\) fails because \(7\) and \(7-5=2\) are not multiples of \(3\) ; and \(3\) , \(5\) , \(6=3\cdot 2\) can be written.
-
A sequence is defined by \(a_0=2\) , \(a_1=5\) , and \(a_n=5a_{n-1}-6a_{n-2}\) for \(n\ge 2\) . Prove that \(a_n=2^{n}+3^{n}\) for every \(n\in\mathbb N\) .
Solution
Let \(P(n)\) be the statement \(a_n=2^{n}+3^{n}\) . The recurrence reaches back two places, so we use strong induction with two base cases.
Base cases: \(2^{0}+3^{0}=2=a_0\) and \(2^{1}+3^{1}=5=a_1\) .
Inductive step: let \(k\ge 1\) and assume \(P(j)\) for all \(0\le j\le k\) . Since \(k+1\ge 2\) the recurrence applies, and using \(P(k)\) and \(P(k-1)\) ,
\[ a_{k+1}=5a_k-6a_{k-1}=5(2^{k}+3^{k})-6(2^{k-1}+3^{k-1})=2^{k-1}(10-6)+3^{k-1}(15-6)=4\cdot 2^{k-1}+9\cdot 3^{k-1}. \]Since \(4\cdot 2^{k-1}=2^{k+1}\) and \(9\cdot 3^{k-1}=3^{k+1}\) , this is \(P(k+1)\) . The first few terms \(2,5,13,35,97\) agree with the formula.
-
Prove by strong induction that every positive integer can be written as a sum of distinct powers of two, where \(2^{0}=1\) counts as a power of two. Treat even and odd integers as separate cases in the inductive step.
Solution
Let \(P(n)\) be the statement that \(n\) is a sum of distinct powers of two. We use strong induction from the base case \(n=1\) , where \(1=2^{0}\) .
Inductive step: let \(k\ge 1\) and assume \(P(j)\) for all \(1\le j\le k\) . Consider \(k+1\) .
If \(k+1\) is even, write \(k+1=2m\) . Then \(1\le m\le k\) , so by hypothesis \(m=2^{e_1}+\dots+2^{e_t}\) with distinct exponents. Doubling gives \(k+1=2^{e_1+1}+\dots+2^{e_t+1}\) , and the exponents \(e_i+1\) are again distinct.
If \(k+1\) is odd, then \(k\) is even and \(k\ge 2\) . Write \(k=2m\) with \(1\le m\le k\) . As in the first case, \(k=2^{e_1+1}+\dots+2^{e_t+1}\) with distinct exponents, all at least \(1\) . Then \(k+1=2^{0}+2^{e_1+1}+\dots+2^{e_t+1}\) , and \(2^{0}\) differs from every other term because their exponents are positive.
In both cases \(P(k+1)\) holds. This is the existence of the binary representation of a positive integer.
-
Prove that the Fibonacci numbers satisfy \(F_1+F_2+\dots+F_n=F_{n+2}-1\) for every integer \(n\ge 1\) .
Hint
Base case: \(F_1=1\) and \(F_3-1=2-1=1\) . In the step, add \(F_{k+1}\) to both sides of the hypothesis and use the recurrence in the form \(F_{k+2}+F_{k+1}=F_{k+3}\) . Ordinary induction suffices, because the step uses only the case \(k\) .
-
Use the well-ordering principle directly, without induction, to prove that every integer \(n\ge 2\) has a prime divisor. Consider the least element of a suitable set of divisors of \(n\) .
Solution
Let \(n\ge 2\) and let \(D\) be the set of divisors \(d\) of \(n\) with \(d\ge 2\) . The set \(D\) is nonempty because \(n\in D\) . By the well-ordering principle \(D\) has a least element \(p\) . We claim that \(p\) is prime.
Suppose not. Since \(p\ge 2\) , Definition 3.6 gives \(p=ab\) with \(1<a<p\) . Then \(a\mid p\) and \(p\mid n\) , so \(a\mid n\) by transitivity of divisibility (Exercise 1.11). Also \(a\ge 2\) . So \(a\in D\) and \(a<p\) , contradicting the choice of \(p\) as the least element of \(D\) . Hence \(p\) is prime, and it divides \(n\) . The argument shows a little more than was asked: the smallest divisor of \(n\) greater than \(1\) is always a prime.
-
Prove that in a finite poset every element \(a\) has a minimal element \(m\) with \(m\preceq a\) . Deduce that a finite poset with exactly one minimal element has a least element, and compare with Exercise 2.22.
Hint
Apply Proposition 3.9 to the set \(L=\{x : x\preceq a\}\) with the order restricted to it; it is finite and nonempty, since it contains \(a\) . Show that a minimal element \(m\) of \(L\) is minimal in the whole poset, because anything below \(m\) is also below \(a\) and so lies in \(L\) . For the deduction: if \(m\) is the only minimal element, then every \(a\) has \(m\preceq a\) . Finiteness was used through Proposition 3.9, which is why the example for Exercise 2.22 had to be infinite.
-
Find the flaw in this argument that all positive integers are equal. “Let \(P(n)\) be: if \(a\) and \(b\) are positive integers with \(\max(a,b)=n\) , then \(a=b\) . Base case: if \(\max(a,b)=1\) then \(a=b=1\) . Step: assume \(P(k)\) and let \(\max(a,b)=k+1\) . Then \(\max(a-1,b-1)=k\) , so \(a-1=b-1\) by \(P(k)\) , so \(a=b\) .”
Solution
The predicate \(P(k)\) is a statement about positive integers: it applies to a pair only if both members are positive. In the step, the pair \((a-1,b-1)\) is fed to \(P(k)\) without checking this, and it can fail: if \(a=1\) or \(b=1\) then \(a-1\) or \(b-1\) is \(0\) .
Run the step at its first value, \(k=1\) . Take \(a=1\) and \(b=2\) , so that \(\max(a,b)=2\) . Then \((a-1,b-1)=(0,1)\) , and \(0\) is not a positive integer, so \(P(1)\) says nothing about this pair. The implication \(P(1)\to P(2)\) has not been proved, and it is false, since \(P(1)\) is true and \(P(2)\) is false. The base case and all the algebra are correct; the error is the use of the induction hypothesis outside the domain for which it was stated.
-
A student claims that \(\sum_{i=1}^{n}i=\frac{(2n+1)^{2}}{8}\) for all \(n\ge 1\) and proves the inductive step: assuming the formula for \(k\) , the sum to \(k+1\) is \(\frac{(2k+1)^{2}}{8}+(k+1)=\frac{(2k+3)^{2}}{8}\) . Check the algebra of the step, and explain why the claim is nevertheless false for every \(n\) .
Answer
The algebra is right: \(\frac{(2k+1)^{2}}{8}+(k+1)=\frac{4k^{2}+4k+1+8k+8}{8}=\frac{4k^{2}+12k+9}{8}=\frac{(2k+3)^{2}}{8}\) . The base case is wrong: for \(n=1\) the sum is \(1\) and the formula gives \(\frac98\) . In fact \(\frac{(2n+1)^{2}}{8}=\frac{n(n+1)}{2}+\frac18\) , so the formula exceeds the true sum by \(\frac18\) for every \(n\) .
-
How many L-shaped pieces does the construction of Theorem 3.4 place at each level of the recursion for a \(2^{n}\times 2^{n}\) board, and how many in total? Explain how the total proves that \(1+4+4^{2}+\dots+4^{n-1}=\frac{4^{n}-1}{3}\) .
Answer
At the top level \(1\) piece is placed, then one in each of the \(4\) quadrants, then one in each of \(16\) sub-quadrants: \(4^{j-1}\) pieces at level \(j\) for \(j=1,\dots,n\) , and \(1+4+\dots+4^{n-1}\) in total. The pieces cover \(4^{n}-1\) squares, three each, so the total is also \(\frac{4^{n}-1}{3}\) .
-
A rectangular chocolate bar of \(m\times n\) unit squares is broken into its \(mn\) unit squares. Each break takes one piece and splits it along a grid line into two pieces. Prove that every way of doing this uses exactly \(mn-1\) breaks, by finding a quantity that each break changes in a fixed way.
Solution
Track the number of pieces. At the start there is one piece, the whole bar. Each break takes a single piece and replaces it by two, so each break increases the number of pieces by exactly \(1\) , whichever piece is chosen and wherever it is split. At the end there are \(mn\) pieces.
Formally, the property “the number of pieces equals one more than the number of breaks made so far” holds at the start, when both sides are \(1\) , and is preserved by every break, so by the invariant principle it holds at every stage. At the final stage it reads \(mn=1+(\text{number of breaks})\) . Hence every way of breaking the bar uses exactly \(mn-1\) breaks. No strategy is faster or slower than any other.
-
Seven coins lie heads up. (a) A move turns over exactly four coins. Prove that the coins can never all be tails. (b) Now a move turns over exactly three coins. Show that all tails can be reached, and find the least number of moves.
Solution
(a) Let \(h\) be the number of coins showing heads. A move turns over four coins; if \(j\) of them show heads and \(4-j\) show tails, then afterwards \(h\) has changed by \((4-j)-j=4-2j\) , which is even. So the parity of \(h\) is an invariant. At the start \(h=7\) , which is odd, so \(h\) is odd after every move. All tails means \(h=0\) , which is even. By the invariant principle it cannot be reached.
(b) Now a move changes \(h\) by \((3-j)-j=3-2j\) , one of \(3,1,-1,-3\) , so parity is no obstacle. Three moves suffice: turn three heads, leaving \(4\) heads and \(3\) tails; turn two heads and one tail, leaving \(3\) heads; turn those three heads, leaving \(0\) . Fewer moves are impossible, because each move lowers \(h\) by at most \(3\) , and two moves lower it by at most \(6<7\) . The least number of moves is \(3\) .
-
Start with a pair of positive integers \((a,b)\) . A move replaces the pair by \((a-b,b)\) if \(a>b\) and by \((a,b-a)\) if \(b>a\) ; no move is possible if \(a=b\) . Show that the set of common divisors of the two numbers is an invariant, find a monovariant, and say what the final pair is when the starting pair is \((21,15)\) .
Hint
For the invariant, use Example 1.6: if \(d\) divides \(a\) and \(b\) then \(d\) divides \(a-b\) , and if \(d\) divides \(a-b\) and \(b\) then \(d\) divides their sum \(a\) . So the pairs \((a,b)\) and \((a-b,b)\) have the same common divisors. For the monovariant try \(a+b\) . The moves from \((21,15)\) are \((6,15)\) , \((6,9)\) , \((6,3)\) , \((3,3)\) .
-
In the game of Example 3.9 played with the numbers \(1,2,\dots,n\) , show that a final number \(0\) is impossible unless \(n\) or \(n+1\) is divisible by \(4\) , and exhibit a sequence of moves that reaches \(0\) when \(n=4\) .
Answer
The parity of the sum is invariant, so a final \(0\) needs the starting sum \(\frac{n(n+1)}{2}\) to be even, that is, \(4\mid n(n+1)\) . One of \(n\) , \(n+1\) is odd, so \(4\) must divide the other. For \(n=4\) : erase \(1\) and \(3\) and write \(2\) , leaving \(2,2,4\) ; erase \(4\) and \(2\) and write \(2\) , leaving \(2,2\) ; erase these and write \(0\) .
-
Show that Theorem 3.2 with \(n_0=0\) is equivalent to the following statement about sets: if \(S\subseteq\mathbb N\) contains \(0\) and contains \(n+1\) whenever it contains \(n\) , then \(S=\mathbb N\) . Explain how to pass from a predicate to a set and back.
Hint
Given a predicate \(P\) , let \(S=\{n\in\mathbb N : P(n)\text{ is true}\}\) ; conditions (i) and (ii) of Theorem 3.2 become “\(0\in S\) ” and “\(n\in S\) implies \(n+1\in S\) ”, and the conclusion becomes \(S=\mathbb N\) . Given a set \(S\) , let \(P(n)\) be the statement \(n\in S\) . Each form of the principle is the other one rewritten.