The Infinite Stairway

I’m sure you’ve counted (“One, two, three, . . . ”) on too many occasions to count. The process can be boring (counting sheep), exciting (counting your winnings at a casino), or menacing (“If you kids aren’t at the dinner table by the time I reach ten, I’ll …”). But one thing counting is not is liberating. What could be less free than the inexorable succession of the counting numbers? And yet the very regularity of counting numbers gives us the freedom to think about them in multiple ways, arriving at conclusions along delightfully varied paths.

Consider the classic problem of adding all the numbers from 1 up to 100. The obvious method of computing the sum takes a long time, which is why (according to a legend that may or may not be true) a certain schoolteacher in Germany a few centuries ago asked his students to work it out on their slates; he wanted to buy himself a bit of peace. Unfortunately for him, one of his students was the young Carl Friedrich Gauss, future doyen of European mathematics, who knew even then that when you add up a bunch of numbers, the order in which you add them doesn’t matter. That regularity gave Gauss the freedom to add them in a different order, peeling off the numbers from both ends of the list in alternation:

1+100+2+99+3+98+…+49+52+50+51

Pairing up the numbers two by two as

(1+100)+(2+99)+(3+98)+…+(49+52)+(50+51),

Gauss quickly saw that the answer was 101 + 101 + 101 + … + 101 + 101, or 101 × 50, and astonished his teacher by writing “5050” on his slate before even a minute had passed.¹

Gauss wasn’t the first person to figure out how to add the numbers from 1 up to n; the ancient Greeks (and probably other civilizations whose mathematical ideas weren’t as amply recorded or don’t get as much attention) knew that the sum is always half of the product of n and n+1. The way they proved it was by cutting an n-by-(n+1) array of dots into two triangles, as shown below for n = 10:

The triangular region to the left of the diagonal, read by rows from top to bottom, has 1+2+…+10 dots, and the triangular region to the right of the diagonal, read by rows from bottom to top, also has 1+2+…+10 dots. So, taking inventory of all the dots in the 10-by-11 rectangle, we see that twice 1+2+…+10 must equal 10 times 11, which implies that 1+2+…+10 must equal half of 10 times 11.

The same reasoning shows that for any counting number n, the sum 1+2+…+n must equal n(n+1)/2. For any counting number n. No matter how big! The fact that we can know this is a pretty amazing thing when you stop to think about it. There are bigger numbers than we can ever count to, bigger numbers than we could ever write down, bigger numbers than we will ever imagine with our finite brains – yet our argument shows that no matter how big n is, there’s a relationship between the value of n and the value of the sum of all the counting numbers up to n.²

MATHEMATICAL INDUCTION

Let’s look at a different proof. It won’t give the same jolt of insight that you get from looking at the picture on the previous page, but the method scales up to tackle harder problems (like showing that 1⁴ + 2⁴ + . . . + n⁴ = n(n+1)(2n+1)(3n²+3n−1)/30, say) in a way that the geometrical approach doesn’t.

Let’s start by examining the proposition 1+2+3+…+99+100 = 5050 and the proposition 1+2+3+…+99 = 4950. Please forget for a moment that you already know that the former proposition is true, because that will distract you from the subtler point I’m trying to make. Let’s give these propositions names. Let P be the proposition “1+2+3+…+99 = 4950” and Q be the proposition “1+2+3+…+99+100 = 5050”. (Note that P and Q are not numbers; they’re assertions of numerical equality.) I claim that the left-hand side of Q is 100 more than the left-hand side of P and that the right-hand side of Q is 100 more than the right-hand side of P. Check it out:

P : 1+2+3+…+99 =4950

Q: 1+2+3+…+99+100=5050

The left-hand side of Q is just like the left-hand side of P, except that there’s an extra 100; and the right-hand side of Q is 5050, which is 100 more than 4950. So Q is just P with 100 added to both sides, and P is just Q with 100 subtracted from both sides. P and Q either stand together or fall together. They’re either both true or both false.

You may wonder: Where am I going with this? All the way down to 1, is where! (That’s as low as we can go; I’m not considering zero to be a counting number.) For each counting number n between 1 and 100, let P_n be the proposition 1+2+. . .+n = n(n+1)/2. So for instance P₁ is the proposition 1 = (1)(2)/2, P₂ is the proposition 1 + 2 = (2)(3)/2, P₃ is the proposition 1 + 2 + 3 = (3)(4)/2, and so on. What we saw in the previous paragraph is that P₉₉ and P₁₀₀ have the same truth-status; either both are true or both are false. But there’s nothing special about the numbers 99 and 100 in the assertion made in the previous sentence, aside from the fact that they’re consecutive. Consider any two consecutive counting numbers, which we may as well call n−1 and n, and consider the proposition P_n, which asserts that 1+2+…+(n−1)+n = (n)(n+1)/2, and the proposition P_n−1, which asserts that 1+2+…+(n−1) = (n−1)(n)/2. It’s clear that the left-hand side of P_n is exactly n more than the left-hand side of P_n−1 (since it’s the same sum with the extra term n tacked on at the end), and a little bit of algebra shows us that the right-hand side of P_n is exactly n more than the right-hand side of P_n−1.³

Have I proved P₁₀₀ yet? Not quite. But I’ve shown that you that P₁₀₀ and P₉₉ are either both true or both false, and that P₉₉ and P₉₈ are either both true or both false, and so on, ending with the claim that P₂ and P₁ are either both true or both false. So it’s a package deal: you must either believe all one hundred of these assertions or disbelieve all hundred of them.

And now for the punchline: go back and look at P₁ again. It asserts merely that 1 = (1)(2)/2, which I’m sure you believe. So you must buy the whole package, and assent to all one hundred of the propositions, including P₁₀₀, the one we were interested in to begin with.

Note that to make the argument work we didn’t actually need to know that for each n the propositions P_n−1 and P_n must either both be true or both be false; all we really needed to know is that if P_n−1 is true then P_n must be true as well, and that this implication holds for all n up to 100.

But why stop at 100? The same reasoning applies to larger numbers too. For every counting number n, if P_n  is the proposition that 1+2+…+n = n(n+1)/2, then for every n the truth of P_n−1 implies the truth of P_n , so once we know that P₁ is true, it follows that all the infinitely many propositions P₂, P₃, …, P₉₉, P₁₀₀, …, P₁₀₀₀, … are true as well. This way of reasoning is called mathematical induction, and it’s one of the main levers mathematicians use when trying to prove infinitely many propositions at once. The principle asserts that if you have propositions P₁, P₂, P₃, …, and you know that P₁ is true, and you know that P_n  is true whenever P_n−1 is true, then P_n  is true for all n.⁴ The individual propositions P₁, P₂, P₃, … cease to be isolated facts and become nodes in a network of implications. The principle of mathematical induction is the glue that holds the counting numbers together.

Warning: Even though there are infinitely many counting numbers, you shouldn’t get the idea that infinity is itself a counting number. It isn’t. The infinite stairway has a bottom marked 1, but it doesn’t have a top marked ∞. Finite staircases always have a top tread, but our fictional infinite staircase doesn’t. Some find this wonderfully odd while others find it disturbing. Indeed, some mathematicians think that because the human mind is finite, we need a radically finite mathematics that banishes the infinite. These are the finitists, who want us to view the infinite stairway not as a completed thing (not even a fictional one) but as a blueprint for a structure that can never be completed. The radical wing of finitism is ultrafinitism, which asserts that really really really big counting numbers don’t exist.

My own prediction, based on what I know of mathematical history, is that mathematics, with its track record of expanding to accommodate different philosophies of mathematics, will eventually build a big enough tent to house the ultrafinitists. But I also predict that ultrafinitistic proofs will be more complicated than their infinitistic counterparts and will be very difficult to understand for those who lack a grounding in infinitistic mathematics. By way of analogy, consider the way we teach Newtonian physics as a prologue to Einsteinian physics; the former is just an approximation to the latter, but it’s hard to understand the truer relativistic theory without understanding its less-true non-relativistic precursor. So the role played by the infinite stairway in the philosophy of mathematics may change in the coming centuries, but it is not likely to be supplanted as a mental image for the working mathematician or for the student learning mathematics.

GET OUT YOUR CRAYONS

If all this talk about sums and propositions and truth seems too abstract and colorless, here’s a down-to-earth way to think about induction via a coloring game.

I write down the numbers from 1 to n in a row (in the picture I’ve chosen n = 10), I mark the number 1 with a smear of blue crayon and the number n with a smear of red crayon and then I hand the blue crayon to you.

After that, we’ll take turns making marks on not-yet-marked numbers, with you marking numbers blue and me marking numbers red. The game ends when there are two consecutive numbers (call them k−1 and k) with k−1 marked blue and k marked red (call this a “blue-red pair”); at that instant, whoever just moved (creating the blue-red pair) loses instantly. Blue-red pairs are forbidden but red-blue pairs are allowed; if k−1 is marked red and k is marked blue, play may continue.

Perhaps you’re wondering, what happens when there aren’t any not-yet-marked numbers and nobody’s lost the game yet? Perhaps you should try to construct a line of play that ends in a draw before you read further.

A famous theorem called Sperner’s Lemma tells us that a draw can’t happen. Specifically, the assertion that a draw can’t occur in our game is the 1-dimensional case of Sperner’s Lemma. (Sperner’s Lemma is usually discussed only in 2 dimensions and higher, where it’s far more interesting.) We can prove this by induction. We know that 1 is blue, so if 2 ever gets colored red, a blue-red pair is formed and somebody loses. So a draw can only happen if 2 is colored blue at the end of the game. What about 3? The same reasoning applies: we’ve shown that if there’s a draw, 2 must be colored blue at the end of the game, and is 3 is colored red, then a blue-red pair is present and the game wasn’t a draw after all. And so on. Ultimately, we reach n−1, and show that it too must eventually be colored blue. But at the instant that that happens, n−1 and n will form a blue-red pair, and somebody (namely the blue player, namely you) loses. So a draw is impossible.

Notice that we can state this result in a less combative way: regardless of whether the players compete or collaborate, there’s no way to color the numbers 1 through n so as to simultaneously satisfy the constraints (a) 1 is blue, (b) n is red, and (c) there are no blue-red pairs. The three conditions are incompatible.⁵

The reason I’ve taken this detour is that the fact that we just learned about the Sperner game (to wit, that conditions (a), (b), and (c) are incompatible) isn’t just an application of induction; you can turn things around and use the incompatibility result to prove the principle of mathematical induction!

Suppose we have some propositions P₁, P₂, P₃, … and we’d like to prove that they’re all true. Furthermore, suppose that P₁ is true, and suppose that whenever P_k−1 is true, P_k is true, for all k up to 10, say. How would we show that P₁₀ is true? Let’s color the numbers 1 through 10, where k is blue if P_k is true and k is red if P_k is false. Since P₁ is true, 1 is blue, so condition (a) is satisfied. Furthermore, our supposition that whenever P_k−1 is true, P_k is true, translates into the supposition that whenever k−1 is blue, k is blue; that is, blue-red pairs don’t exist, so condition (c) is satisfied. We now know that conditions (a) and (c) are satisfied, but Sperner’s lemma tells us that conditions (a), (b), and (c) are incompatible, so we have no choice but to conclude that condition (b) is not satisfied. That is, 10 is not red. That is, 10 is blue. That is, P₁₀ is true. And what works for 10 works for all larger numbers as well. So the 1-dimensional Sperner lemma (which I originally proved by induction) can also be used to justify induction. Either one can be taken as an axiom characterizing the counting numbers.

[Hey readers: Did you like this section? It’s a bit of an unusual take on induction. Was it helpful or was it distracting? Let me know in the Comments!]

BANISHING PHANTOMS

Mathematical induction is great for proving that certain things always happen, but it can also be used to show that certain things never happen. (This shouldn’t be surprising, though, since Never is just another kind of Always.)

Say you want to draw a regular octagon on graph paper, like this:

This first effort isn’t bad, but it’s fairly evident that the horizontal and vertical sides are slightly longer than the diagonal sides. Can we do better? For that matter, why settle for merely better: can we do it perfectly?

What we are looking for are numbers a and b to replace 2 and 3 in the picture that will give us a regular octagon. That is, we want whole numbers a and b with the property that the hypotenuse of an isosceles right triangle with both its legs of length a has length equal to b. By the Pythagorean theorem, this is equivalent to the equation 2a² = b². In other words, we are looking for a perfect square (a²) which when doubled (2a²) equals another perfect square (b²). 

So, you charge up the infinite stairway, looking for a counting number a with the property that 2a² is a perfect square. Surely you’ll find one; in an infinite universe (so goes the cliché) everything you can imagine is bound to happen somewhere eventually, and the stairway is infinite, so surely you’ll eventually find the object of your quest!

Onward, past one million. You haven’t found such an a yet, but remember, success favors the bold, not the quitter. Onward, past one billion. Don’t give up now! You’ve invested so much in the search; why throw in the towel and throw all that effort away? Onward, past one trillion. Ignore all the nay-sayers, including the ones in your own head. Believe in yourself! Keep going! …

Well, no — please don’t. You are chasing a phantom; no such number a exists. One of the most amazing things about the stairway is that it’s possible for us to know, beyond doubt, that certain number-properties that we can formulate (such as the property “2a² is a perfect square”) are not satisfied by any counting number a whatsoever. We don’t prove this by conducting an exhaustive survey of the stairway, which the human mind can’t do. Instead, we make use of a curious asymmetry of the stairway: you can ascend forever and never hit an obstacle, but any downward trip in the stairway must eventually end.⁶

I wrote about the method of proof by descent in Reasoning and Reckoning so I won’t give the full details in this essay. But I’ll summarize here one of the conclusions I established there, which is that if a is a counting number with the property that 2a² is a perfect square, then a/5 (call it a′) is a smaller counting number with the property that 2a′² is a perfect square. Applying this same argument a second time, we find that a′/5 (call it a′′) is an even smaller counting number with the property that 2a′′² is a perfect square. And so on, ad infinitum. We get an infinite sequence of ever-smaller counting numbers a, a′, a′′, … , each with the property that its square, doubled, is a perfect square. But wait a minute: how can we have an unending sequence of counting numbers, each smaller than the one before? There’s no such thing! So we conclude that there’s no such number a. It was never more than a phantom.

Here’s a more geometrical way to banish the phantom from the infinite stairway, discovered by Joel Hamkins. Draw an octagon with corners labeled A through H:

We can draw a new octagon by swinging the edges through 90 degrees about an endpoint. For instance, we swing edge AB 90 degree clockwise about A, and call the new point A′; we swing edge BC 90 degree clockwise about B, and call the new point B′; and so on, around the octagon.

Here are the two things to notice: (a) if A through H are grid-points, then A′ through H′ must be grid-points as well; and (b) if AB···H is a regular octagon, then A′B′···H′ is a regular octagon. So if our original octagon had both properties, we can repeat the process as many times as we like, obtaining ever-smaller regular octagons with corners in the square grid. But all these octagons have side-lengths equal to counting numbers, so we get a sequence of ever-smaller counting numbers, which we know is impossible.

This method of argument was a favorite of Pierre Fermat’s. He used it for instance to prove the n=4 case of what is now called Fermat’s Last Theorem. Specifically, he showed that there don’t exist positive integers x, y, z satisfying x⁴ + y⁴ = z⁴. In fact, he used the method of descent to prove something stronger: there don’t exist positive integers x, y, z satisfying x⁴ + y⁴ = z². He showed that if there were a phantom solution, there’d be a smaller phantom solution, and a smaller phantom solution, and so on, ad infinitum, which is impossible, since there cannot be an infinite sequence of ever-smaller counting numbers.

So you could say that the way to banish phantoms from the infinite stairway is to kick them down the stairs!

UP THE DOWN STAIRCASE

If the preceding results strike you as having a depressing vibe (“no way”; “can’t be done”; “impossible”; “don’t waste your time trying”), you’ll be glad to learn that the downward impossibility results can sometimes be flipped into upward possibility results.

Let’s look again at the picture of the two nested octagons and follow the action more carefully. The big octagon is determined by the two numbers 5 and 7 (the horizontal displacement from A to B is 7 and the horizontal displacement from B to C is 5), and the reason the octagon is so close to regular is that twice 5² is very close to 7². Likewise, the small octagon is determined by the two numbers 2 and 3 (the horizontal displacement from A′ to B′ is 3 and the horizontal displacement from B′ to C′ is 2), and the reason the octagon is somewhat close to regular is that twice 2² is somewhat close to 3² . The recipe for getting from a = 5, b = 7 to a′ = 2, b′ = 3 is to take a′ = b−a, b′ = 2a−b.

But this method of descent, as I promised you, has a flip side: a method of ascent that let us create infinitely many near-misses that come close to solving the original problem, and lets us systematically create ever-better grid-approximations to a regular octagon. It’s the descent process, run in reverse: a = a′+b′, b = 2a′+b′. Or if we prefer, a = b′+a′, b = a′+a. Here’s a graphical depiction of the process:

The picture is made of little number-snippets (1,1,2,3; 3,2,5,7; 7,5,12,17; 17,12,29,41, etc.) arranged in three-quarters circles. In each snippet, the third number is the sum of the first and second, and the fourth number is the sum of the second and third. If we wanted to continue the pattern, we’d have 41+29=70 at the top right and 29+70=99 beneath it. We get infinitely many pairs a, b satisfying 2a² − b² = ±1. Although the discrepancy between 2a² and b² never goes below 1 in absolute magnitude, in relative magnitude (compared to a and b, which keep growing exponentially) the discrepancy is getting exponentially smaller. 

The Indian mathematician Brahmagupta knew all this, and he came up with an even faster method of getting really good approximations by combining two known approximations. Specifically, he discovered that if u²−2v² = ±1 and w²−2x² = ±1, then putting y = uw+2vx and z = ux+vw we get a new solution y² − 2z² = ±1. In a later essay, I’ll explain why this seemingly miraculous way of building new solutions from old is perfectly sensible and unsurprising when viewed through the lens of algebraic number theory.

THE BIGGEST MYSTERY

There are many odd features of this imaginary stairway, equipped with a bottom but no top. One is the futility of attempting to climb it. There may be an illusion of progress, but no matter how many treads we surmount in absolute terms, we have made, in relative terms, no progress at all. For no matter how far we’ve come, the part of the stairway that we have passed is finite, while the part that remains before us is infinite; compared to what lies ahead, what lies behind is negligible. You’re always just beginning your journey; in relative terms, you never get off that first tread.

And yet we can know things about the number-stairway, and know them with certainty, even facts that pertain to parts of the stairway we’ll never visit. We can say, for instance, that the far reaches of the stairway contain infinitely many numbers a for which 2a² − 1 is a perfect square, yet none for which 2a² is a perfect square. The way in which the infinite stairway combines knowability and unknowability is part of its allure.

But for me, the most wondrous thing is the way the rigidly one-dimensional stairway, refracted through the human mind, kaleidoscopically unfolds into something more like a landscape than a corridor. This is a landscape not of numbers but of knowledge. The facts of math are not arranged in a line, but rather lie scattered about, and we must arrange them into patterns and then organize the patterns into some sort of story. Facts fall into networks bound together by filaments of logic, and these networks communicate with other networks, forming larger networks which are parts of even larger networks. Indeed, to know the facts beyond doubt, we must construct the sorts of stories that are called proofs. Proofs are a bit like the stairway, in that they are linear, and following the links in a chain of deductions can be a bit like climbing the stair, but devising a proof that works is quite different. The landscape of what’s true doesn’t come with a map, let alone an itinerary, and sometimes the shortest path leading us from the things we already know to the thing we want to know is extremely circuitous, and requires wandering far from where anyone has journeyed. 

The staircase is linear but human thought is not. Sometimes intuition leaps over steps in a proof and then fills in those steps after the fact; Gauss himself once said “I have had my results for a long time but I do not yet know how I am to arrive at them.” But for him, a proof was more than a certificate of truth; it was also a source of understanding. A bad proof can tell you that something is true without telling you why it’s true, and even a good proof can fail to satisfy; mathematicians often want multiple proofs that illuminate some aspect of mathematical reality from various angles. Gauss himself sought proof after proof of the fundamental theorem of algebra because he wanted to understand it deeply. The quest for understanding is more central to mathematics than the quest for mere certainty.

In an earlier, more fanciful draft of this essay, I wrote: “We do not know Who built the stairway, but They did not build it for us.” But I don’t really believe in such a Them, so it seems disingenuous to try to raise readers’ goosebumps in this cheesy fashion.

Still: if there exist beings of infinite mind outside our physical universe who can encompass the stairway and all that it contains, they must have a very different relationship to mathematical truth than we do. They need no proof that counting-number solutions to 2a² = b² don’t exist; they just see it at a glance, by surveying all counting number at once. For us, P₃ was true because P₂ is true because P₁ is true. For them, P₁ is true and P₂ is true and P₃ is true, just because they’re self-evident. There’s a huge leveling, and a huge loss, when all mathematical facts are equally transparent. In a way I envy such mathematically omniscient beings, but in way I pity them. They’re missing out on the stories that connect the facts, and the struggle to construct such stories when one has a finite mind and only a partial understanding of the landscape. For me, the human struggle to know what’s true, and why it’s true, is what gives the quest for mathematical knowledge its drama, its dignity, and its joy.

Thanks to Sandi Gubin.

ENDNOTES

#1. Some skepticism about this anecdote is in order here. Also, I don’t like the way it reinforces the genius myth. For more on the Gauss story, see my essay Reasoning and Reckoning. The essay you’re reading now can be viewed as something like a second draft of that earlier essay. For more on the genius myth, see my essay The Genius Box.

#2. The pioneering 20th century neuroscientist Warren McCulloch, whose ideas about neurons and computation foreshadowed advances in our own century, decided when he was young that he would devote his life to the two-part question “What is number, that man may know it, and what is man, that he may know a number?” We still don’t have a good answer.

#3. The right-hand side of P_n is (n)(n+1)/2, or n/2 times n+1, while the right-hand side of P_n−1 is (n−1)(n)/2, or n/2 times n−1. Subtracting, we see that the difference is n/2 times (n+1)−(n−1), or n/2 times 2, which is n.

#4. The principle of mathematical induction has many variants that are equivalent to it, so if you’re thinking “Wait, the induction step means showing that P_n implies P_n+1, not P_n−1 implies P_n!”, then you’re remembering a version of the principle that’s equivalent to the one I’ve stated.

#5. I think the game is interesting, so if any of you know anything about it, either because it’s already been studied by others or because you played around with it and figured some things out, please let me know in the Comments!

#6. Let P_n be the proposition that any downward trip that starts with n or some lower number must eventually end. Clearly P₁ is true. Now suppose P_n−1 is true. We’d like to prove that P_n is true. That is, we’d like to show that every downward trip that starts with n or some lower number must eventually end. So, focus on one particular downward trip that starts with n or some lower number. If it starts with n−1 or some lower number, then P_n−1 tells us that the trip must end, and we’re all set. All that remains is to consider the case where the trip starts with n. In this case, the trip proceeds to its second step, which must be a number less than n; call it m. But now, proceeding from m (which is less than n), we are taking a “sub-trip” that begins with a number that’s n−1 or less, and so, by virtue of P_n−1, that sub-trip must eventually end, and this implies that the full trip must eventually end. So in both cases – whether the trip starts with n or something smaller – we find that the downward trip must end. So we’ve shown that P_n is true. Since we proved that P₁ is true, and we proved that P_n is true whenever P_n−1 is true, mathematical induction tells us that P₁, P₂, P₃,… are all true.

#7. The pictures above show octagons with horizontal and vertical sides, but the argument also works for canted octagons like this:

The conclusion is that you can have a regular octagon, and you can have an octagon whose corners are on the square grid, but you can’t have an octagon that achieves both feats at the same time. A variant of this arguments works for grids in d dimensions for all d > 2. So if you’re one of those people who thinks that our seemingly continuous physical world is actually made up of little cubes analogous to the pixels that constitute digital photographs, then no regular octagons for you!