More applications of induction
An excerpt from Proof and the Art of Mathematics
This is a free extended excerpt from chapter 4 of my book Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing, for aspiring mathematicians who want to learn how to write proofs.
Proof and the Art of Mathematics teaches the art of proof-writing in the diverse contexts of a variety of mathematical subjects, but always with mathematical theorems and statements that carry their own inherent interest and fascination—compelling mathematical results with interesting, elementary proofs.
Buckets of Fish via nested induction
Let us consider now a somewhat more fanciful instance of induction, which also illustrates the idea of nested induction. Consider the game I call Buckets of Fish, played with two players on the beach.
The game begins with finitely many buckets arranged in a row, each bucket containing some finite number of fish, with a large supply of additional fish available nearby, as many as needed, fresh off the boats. Each player, in turn, takes a fish from one bucket and adds to each of the buckets to the left, if any, as many fish from the extra supply as he or she likes. If we label the buckets 1, 2, 3, and so on, from left to right, then it would be a legal move for a player to take one fish out of bucket 4 and add ten fish (from the extra supply) to bucket 1, no fish to bucket 2, and ninety-four fish (from the extra supply) to bucket 3. The winner is whoever takes the very last fish from the buckets, leaving them empty.
Since huge numbers of fish can often be added to the buckets during play, but only one fish removed, a skeptical reader could reasonably wonder whether we'll really always even get a winner. By adding fish suitably, can the players prolong the game indefinitely? Or does every play of the game Buckets of Fish necessarily come to an end?
The answer is that, indeed, every play of the game must eventually come to an end. Regardless of how the players might conspire to add fish to the buckets during play, even with an endless supply of fish from the boats, nevertheless they will eventually run out of fish in the buckets and one of the players will take the last fish. I shall give several proofs.
Theorem. Every play of the game Buckets of Fish ends in finitely many moves. All the fish in the buckets, including all the new fish that may have been added during play, will eventually run out by some finite stage during play.
Before proving this theorem, let me first prove a weaker claim, namely, that either player may force the game to end in finitely many moves. The way to do this is simply to take fish always only out of the rightmost bucket. Since that bucket is never replenished, it follows that eventually it will become empty, and then there will be in effect strictly fewer buckets. By now taking fish only from the new rightmost bucket, we can eventually ensure that that bucket also becomes empty, and so on. In this way, by induction, we can ensure that the number of buckets with fish eventually reduces to just one bucket, which is eventually emptied. Thus, either player can play so as to ensure that the game ends in finitely many moves. But this is a weaker claim than made in the theorem, which states that actually all ways of playing the game will end in finitely many moves.
First proof. We prove the claim by (nested) induction on the number of buckets. If there is only one bucket, then there are no buckets to the left of it, and consequently there is no possibility in this case to add fish to the game; so if the one bucket contains k fish, then the claim clearly ends in k moves.
Assume by induction that all plays using at most n buckets end in finitely many moves, and suppose that we have a game situation with n + 1 buckets, with k fish in bucket n + 1. We now prove by induction on k that all such games terminate. This argument is therefore an instance of nested induction, because we are currently inside our proof by induction on n, in the induction step of that proof, and in order to complete it, we are undertaking a separate full induction on k. If k = 0, then there are no fish in bucket n + 1, and so the game amounts really to a game with only n buckets, which terminates in finitely many steps by our induction hypothesis on n.
So, let us assume that all plays with k fish in bucket n + 1 terminate in finitely many moves. Consider a situation where there are k + 1 many fish in that bucket. I claim that eventually one of those fish must be taken, since otherwise all the moves will be only on the first n buckets, and all plays on only n buckets terminate in finitely many moves. So at some point, one of the players will take a fish from bucket n + 1, possibly adding additional fish to the earlier buckets. But this produces a situation with only k fish in bucket n + 1, which by our induction assumption on k we know will terminate in finitely many steps.
So we have proved that no matter how many fish are in bucket n + 1, the game will end in finitely many moves, and so the original claim is true for n + 1 buckets. Thus, the theorem is true for any finite number of buckets. ☐
Second proof. Let me now give another proof. We want to prove that there is no infinitely long play of the game Buckets of Fish. Suppose toward contradiction that there is a way for the players to conspire to produce an infinite play, starting from some configuration of some finite number n of buckets, each with finitely many fish in them.
Fix the particular infinitely long play. Let m be the rightmost bucket from which infinitely often a fish was taken during that infinite course of play. It follows, for example, that m < n, since bucket n can be used only finitely often, as it never gets replenished. Since bucket m starts with only finitely many fish in it, and each time it is replenished, it is replenished with only finitely many fish, it follows that in order to have been used infinitely many times, it must also have been replenished infinitely often. But each time it was replenished, it was because there was some bucket farther to the right that had been used. Since there are only finitely many buckets to the right of bucket m, it follows that one of them must have been used infinitely often. This contradicts the choice of m as the rightmost bucket that was used infinitely often. ☐
Let me mention briefly a third proof of the theorem, making use of the concept of transfinite ordinals, with which some readers might be familiar. (If you are not familiar with ordinals yet, please do not worry about it; you might learn about them in an introductory set theory class at your university.) Specifically, we associate with each Buckets-of-Fish position a certain ordinal. With the position
for example, we associate the ordinal
In general, the number of fish in each bucket of a position becomes the coefficient of the corresponding power of ω, using higher powers for the buckets farther to the right. The key observation to make is that these associated ordinals strictly descend for every move of the game, since one reduces a higher-power coefficient and increases only lower-power coefficients. Since there is no infinite descending sequence of ordinals, it follows that there is no infinite play in the game Buckets of Fish. This idea also shows that the ordinal game values of positions in this game are bounded above by ωω, and every ordinal less than ωω is realized by some position.
So now we know that the game will always end. But how shall we play? What is the winning strategy? Say you are faced with buckets having fish in the following amounts:
What is your winning move? Please give it some thought; we shall return to the topic in a later chapter, The Theory of Games, where we will provide the winning strategy for Buckets of Fish.
Every number is interesting
I should like to conclude this chapter with an informal “proof” that every natural number is interesting. For example, 0 is interesting, since it is the additive identity, which is an interesting property for a number to have. Similarly, the number 1 is the multiplicative identity, which also is quite interesting. The number 2 is the first prime number, 3 is the first odd prime number, 4 is the first composite number, and so on.
I claim that every number is interesting. To prove this, observe that if there were any uninteresting numbers, then by the least-number principle, there would have to be a number n that was the smallest uninteresting number. But that is an extremely interesting property for a number to have! This therefore contradicts the assumption that n was uninteresting, and so there must not be any uninteresting numbers. So we may rejoice: every number is interesting! The reader will criticize this argument in the exercises.
Habits
Understand induction deeply. Grasp the idea that mathematical induction is about the impossibility of minimal counterexamples. Learn how this manifests in the various forms of induction — common induction, strong induction, the least-number principle — and understand deeply why these are valid.
Use induction flexibly. Do not insist upon a rigid format for proofs by induction but, rather, adopt a flexible approach, choosing whichever valid form of induction fits your argument best.
Distinguish sharply between example and proof. Key examples can be extremely valuable and insightful, but examples do not prove a universal statement. Examples can offer evidence in favor of a mathematical conjecture, but proving a universal claim will require a general argument. Examples can prove an existential statement, however, and they can refute a universal statement, in which case they are called counterexamples.
Exercises
Show by induction that 2n < n! for all n ≥ 4.
Show by induction that
\(\sum_{k = 0}^nk × k! = (n + 1)! -1.\)Show by induction that f0 + ··· + fn = fn+2 - 1 in the Fibonacci sequence.
Show by induction that fn < 2n in the Fibonacci sequence.
Consider an alternative Fibonacci sequence, starting with 0, 2. Can you prove the analogue of the theorem about summing the squares of the sequence?Generalize the result as far as you can.
In analogy with the triangular numbers, define the pentagonal numbers and the hexagonal numbers. Can you find and prove a formula for the nth pentagonal number and the nth hexagonal number?
Show by induction that a finite set with n elements has exactly 2n many subsets.
Prove by induction that the following equation holds for every positive integer n.
\(1 + 4 + 4^2 + ··· + 4^{n-1} = (4^n-1)/3\)Prove that
\(\frac1{1 · 2} + \frac1{2 · 3} + \frac1{3 · 4} + ··· + \frac1{n(n + 1)} = \frac n{n + 1}.\)Prove that
\(1 · 2 + 2 · 3 + 3 · 4 + ··· + n · (n + 1) = \frac {n(n + 1)(n + 2)}{3}.\)Show that every natural number has a unique base 3 representation.
Prove that if you divide the plane into regions using finitely many straight lines, then the regions can be colored with two colors in such a way that adjacent regions have opposite colors. [Hint: Use induction on the number of lines.]
True or false: every flying polka-dotted elephant in this room is smoking a cigar.
Criticize the following “proof.” Claim. All horses are the same color. Specifically, every finite set of horses is monochromatic. Proof. We argue by induction. The statement is clearly true for sets of size 1. Assume by induction that all sets of n horses are monochromatic, and consider a set of size n + 1. The first n horses are all the same color. The last n horses are all the same color. Because of the overlap, this means that all n + 1 horses are the same color. So by induction, all finite sets of horses are all the same color, and so all horses are the same color. ☐
Criticize the following “proof.” Claim.
\(\sum_{i = 1}^ ∞ \frac 1i < ∞. \)Proof. Let
\(S(n) = \sum_{i = 1}^n\frac 1i,\)and consider the statement asserting S(n) < ∞. This statement is true for n = 1, since 1/1 = 1 < ∞. And if it is true for n, then it is true for n + 1, since the next sum
\(S(n + 1) = \sum_{i = 1}^{n + 1}\frac 1i\)is equal to the previous sum
\(\sum_{i = 1}^n\frac 1i \)plus the next term 1/(n + 1), or in other words, S(n + 1) = S(n) + 1/(n + 1), and this is the sum of two finite numbers. So S(1) is true, and S(n) implies S(n + 1). So we have therefore proved
\(\sum_{i = 1}^ ∞\frac 1i < ∞\)by induction. ☐
Prove the following common induction principle variation: Assume that A is a set of integers with some k ∈ A, and furthermore, that whenever n ∈ A, then also n + 1 ∈ A. Then A contains all integers above k.
Prove that the least-number principle, the common induction principle, and the strong induction principle are all equivalent. Assuming any one of them, you can prove the others.
Criticize the argument that every number is interesting, given at the end of the chapter.
Continue reading more about this topic in the book itself: