Every square is a stack of odd numbers

Start adding odd numbers and watch the totals:

$$1,\quad 1+3 = 4,\quad 1+3+5 = 9,\quad 1+3+5+7 = 16.$$

Squares, every time, in order, with none skipped. It keeps working for as long as anyone cares to check, which raises the obvious question of why a fact about odd numbers should know anything about squares.

The answer is that the odd numbers are not really a list of numbers here. They are a list of shapes.

The shape of an odd number #

To grow an $n \times n$ square into an $(n+1) \times (n+1)$ one, a strip has to be added down the right side and another along the bottom, plus a single cell in the corner where the two strips would otherwise miss each other. That is $n + n + 1$ cells, which is to say $2n+1$ — an odd number, and necessarily so, because it is two of something plus one.

The L-shaped piece has a name that predates the arithmetic. The Greeks called it a gnomon, the same word used for the shadow-casting arm of a sundial and for a carpenter’s set square, on the grounds that all three are the shape left over when a smaller rectangle is removed from the corner of a larger one.

So the identity

$$1 + 3 + 5 + \cdots + (2n-1) = n^2$$

is not really a summation at all. It is the observation that a square can be dismantled into shells, one shell per step, and that the shells happen to be the odd numbers because that is what “add a row, a column, and a corner” costs.

Read the picture the other way round and it says something equally true and slightly more useful: the gap between consecutive squares is always odd. $25 - 16 = 9$. $100 - 81 = 19$. In symbols, $n^2 - (n-1)^2 = 2n - 1$, which is a line of algebra, or one glance at a shell.

Falling bodies #

In 1638 Galileo published a rule about objects falling under gravity. Divide the fall into equal intervals of time and measure how far the object travels in each one. The distances come out in the ratio

$$1 : 3 : 5 : 7 : 9 : \cdots$$

This is exactly the gnomon list, and for exactly the gnomon reason. Total distance fallen grows as the square of elapsed time, so after $n$ intervals the object has travelled a distance proportional to $n^2$. The distance covered during the $n$-th interval is therefore proportional to $n^2 - (n-1)^2$, which is $2n-1$.

The odd-number rule is not an additional law of physics sitting alongside the square law. It is the square law, differenced — the same fact told in terms of shells rather than totals. Galileo could measure the interval distances directly by rolling balls down an inclined plane and timing them against a water clock, and the ratios were what he could actually see. The $t^2$ law is the integrated version.

There is something worth pausing on there. A statement about the shape of a square, which is as static and abstract as a fact can be, turns out to be the observable signature of an accelerating body. Nothing in the geometry knows about gravity. The geometry is just where the arithmetic of “one more step” lives.

This is worth pausing on as a matter of method, not just of history. Galileo could not measure instantaneous speed — he had no instrument for it, and the concept itself was not yet stable. What he could do was mark where a ball had reached at the end of each beat of a water clock, and measure the gaps with a ruler. The odd numbers are what a ruler sees. The $t^2$ law, and behind it the whole apparatus of accumulating a quantity by adding up its increments, is the integrated version that came later.

A picture that can be read off an inclined plane with a ruler is worth a good deal more than one that requires the calculus it was used to motivate.

The companion identity #

The odd numbers stack into squares. What do the whole numbers stack into?

$$1 + 2 + 3 + \cdots + n = ?$$

Same method, different shape. A staircase of dots with 1 in the first row, 2 in the second, and so on, does not form anything tidy on its own — it is a triangle with a jagged edge. But two of them do.

Two staircases interlock into a rectangle $n$ by $n+1$, giving

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

The story attached to this one is that Gauss, as a schoolboy, was set the task of adding the numbers from 1 to 100 as busywork and produced 5050 almost immediately by pairing 1 with 100, 2 with 99, and so on — fifty pairs each summing to 101. The anecdote is repeated in a great many mutually inconsistent versions and its details should not be trusted, but the pairing trick is real and it is the same trick as the picture: the rectangle is the two staircases, and the pairs are its rows.

Two ways of counting #

These two identities are the first examples most people meet of a move that never stops being useful: count one thing in two different ways, then set the counts equal.

The square gets counted as $n \times n$, and also as a stack of shells. The rectangle gets counted as $n(n+1)$, and also as two staircases. Neither computation is hard; the content is entirely in the insistence that both must give the same answer.

That is precisely the engine behind the dissection proof of the Pythagorean theorem, where two arrangements of the same four triangles inside the same square force $a^2 + b^2 = c^2$. It is the engine behind most of combinatorics, and it reappears the moment anyone asks how many routes lead to a given place. And it is why so many identities that look like they should require induction can be settled by drawing the right rectangle.

Induction does work here, of course, and works quickly. Assume $1 + 3 + \cdots + (2n-1) = n^2$; add $2n+1$ to both sides; the right side becomes $n^2 + 2n + 1 = (n+1)^2$; done. But notice what that proof provides and what it withholds. It confirms the statement without ever explaining where the squares came from. The picture does the opposite: it makes the answer inevitable and leaves the bookkeeping to look after itself.

Reading a shell backwards factors a number #

The gnomon says that consecutive squares differ by an odd number. Run the sentence in reverse and it says that every odd number is the difference of two consecutive squares — $2n-1 = n^2 - (n-1)^2$ — which turns a fact about drawing into a method for taking numbers apart.

The reason is that a difference of squares always factors:

$$a^2 - b^2 = (a-b)(a+b).$$

So finding any way to write a number as a difference of two squares is finding a factorisation of it. The shell picture supplies one such way for every odd number immediately, but that way is the useless one: it gives $2n-1 = (1)(2n-1)$, the number times itself, which is a factorisation nobody wanted. The interesting question is whether there are other shells — not the thin one of width 1, but a thicker band between two squares further apart.

That is Fermat’s method of factorisation, and it is genuinely a picture. To factor $N$, look for a square just above $N$, subtract, and ask whether the remainder is itself a square. $N = 5959$: the next square up is $78^2 = 6084$, leaving $125$, not a square. Then $79^2 = 6241$ leaves $282$, not a square. Then $80^2 = 6400$ leaves $441$, which is $21^2$. So $5959 = 80^2 - 21^2 = (80-21)(80+21) = 59 \times 101$, found in three steps.

The method’s character is the opposite of trial division. Trial division starts at the small factors and works up, so it is fast when a number has a small factor and hopeless when it does not. Fermat’s method starts from $\sqrt N$ and works outward, so it is fast exactly when the two factors are close together and hopeless when they are far apart. The two are complementary, and the numbers deliberately built to resist both — a large factor and a small one, neither near the square root — are the ones cryptography is made of.

The cost of the method has a formula, which is what turns that last paragraph from a preference into a design rule. The search starts at $a = \lceil\sqrt N\rceil$ and stops when $a$ reaches $(p+q)/2$, so the number of values it must try is

$$\frac{p+q}{2} - \sqrt{N} = \frac{\big(\sqrt q - \sqrt p\big)^2}{2}.$$

For $5959 = 59 \times 101$ that comes to $2.8$, and the search above tried three values of $a$. For $10007 \times 10009$ it comes to $0.00005$: the very first $a$ works, and a nine-digit number falls in one step. For $3 \times 2000003$ — a number of much the same size with its factors as far apart as they can get — it is $997{,}553$, and the search really does take that many steps to factor a seven-digit number that trial division disposes of instantly.

Scaled up, that expression is the rule a key generator obeys. For a $2048$-bit modulus the count is about $\delta^2/8\sqrt N$, where $\delta$ is the gap between the two primes. Two $1024$-bit primes differing by around $2^{520}$ — which is to say agreeing in their leading five hundred bits — sit about $2^{13}$ steps apart, some eight thousand, which is nothing at all. Widen the gap to $2^{600}$ and the count is $2^{173}$, which is nothing anybody will ever do. The entire security of the modulus lives in that exponent, and the exponent came out of a shell.

There is something pleasing in the provenance. A drawing made to explain why $1 + 3 + 5 + 7$ is $16$, read one sentence backwards, is a factoring algorithm still worth implementing, and the reason a modern key generator is careful never to choose its two primes too near each other.

Where else the shells turn up #

Figurate numbers — triangular, square, pentagonal, and onward — were a serious research programme for the Pythagoreans, alongside the regular solids, and the habit of thinking of numbers as arrangements of pebbles produced a startling amount of real mathematics before anyone had algebraic notation to write it down in. The gnomon in particular generalises: pentagonal numbers have their own shell shape, as do hexagonal ones, and each gives a summation identity of the same flavour.

The construction also has a direct descendant in Pascal’s triangle, where the shallow diagonals hold the triangular numbers and the shells of the triangle encode a whole family of these sums at once. And the technique of subdividing something into pieces small enough to count, then letting the number of pieces grow, is the seed of adding up rectangles under a curve — the same instinct, applied where the pieces never stop shrinking.

The next sum up needs another dimension #

The method has a boundary, and finding it is more instructive than extending it.

Odd numbers stack into squares; whole numbers stack into half a rectangle. The natural next question is what the squares stack into — $1 + 4 + 9 + 16 + \cdots$ — and here the flat picture simply stops. There is no L-shaped shell whose cell count is $n^2$ and which grows a plane figure by one step, because the plane has run out of room: a two-dimensional region grown by two-dimensional increments produces totals that grow like $n^2$, not like $n^3$.

The sum of the first $n$ squares grows cubically, so the picture has to become a solid. Stack the squares as square slabs, one on top of the next, and the result is a stepped pyramid of $\tfrac{n(n+1)(2n+1)}{6}$ unit cubes. The proof by picture is that six copies of that pyramid assemble into an $n \times (n+1) \times (2n+1)$ box — the same two-ways-of-counting move as the twin staircases, one dimension up and with six pieces where two sufficed.

That accounts for the formula’s least memorable feature. Nobody has trouble with $\tfrac{n(n+1)}{2}$, and everybody has trouble with $\tfrac{n(n+1)(2n+1)}{6}$, which looks like it was assembled from spare parts. It was: the $6$ is the number of pyramids in the box, and the $2n+1$ is the box’s least obvious edge.

The pattern continues, and it degrades. Sums of cubes need four dimensions to see the same way — though they have a compensating two-dimensional accident, being exactly the square of the triangular number. Sums of fourth powers need five, and no arrangement anyone would call a picture. Faulhaber’s formula gives every case at once and pays for the generality with the Bernoulli numbers, a sequence with no combinatorial picture at all and a habit of turning up wherever an exact discrete sum is wanted.

So the honest summary of the gnomon is narrower than it first appears. It is not a general technique for summation. It is the observation that one particular growth process — a square gaining a row, a column and a corner — has increments that happen to be a famous list, and the technique reaches exactly as far as the dimension it is drawn in.

What the picture cannot show #

The shells make the identity obvious for any $n$ that can be drawn, and drawing stops somewhere around thirty. What the picture cannot do is take the step to all $n$ — that step is made by noticing that no part of the construction referred to the particular size, which is a claim about the argument rather than about the drawing.

This is the same limitation as the dissection proof of the Pythagorean theorem, and it is worth being precise about it rather than pretending the picture does more than it does. A diagram can make a general argument visible; it cannot make it general. Generality comes from checking that the argument never looked at the drawn values.

The ladder from here #

The gnomon is one rung of a longer ladder. Pentagonal and hexagonal numbers have their own shell shapes and their own summation identities, each provable by the same rearrangement. Cubes have a three-dimensional gnomon, and the sum of the first $n$ cubes turns out to equal the square of the sum of the first $n$ integers — a fact with a genuinely startling picture. The figurate numbers connect to Pascal’s triangle, whose third diagonal is the triangular numbers and whose shells encode a whole family of these sums at once.

And the general question — which sums of polynomial powers have closed forms, and why — leads to the Bernoulli numbers and to Faulhaber’s formula.

A square is a stack of odd numbers. It is also, in an inclined-plane experiment in seventeenth-century Padua, a ball picking up speed.