Fun with integers

The other day I was looking at Andy Hertzfeld’s site, which consists of a series of anecdotes about the creation of the original Macintosh computer. Most of the stories—there are over a hundred—were written be Andy himself, but there are several guest contributors. It’s a fun site to hop around in if you were one of the early Mac users and can remember its programs and how they worked. (I will always revere Andy for writing Switcher, a program I always thought was better than the later MultiFinder. I wish Linux window managers had that cool Lazy Susan screen animation.)

One of the stories is about Steve Jobs persuading Bill Atkinson to add rounded-corner rectangles to the QuickDraw portion of the Mac Toolbox. It’s a good story, one that illustrates the good and bad parts of Jobs’s personality in a just a few words. I’d read other versions of the story before, but Andy’s telling has this odd arithmetic fact:

Bill’s technique [of drawing ovals and circles] used the fact the sum of a sequence of odd numbers is always the next perfect square (For example, 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16, etc). So he could figure out when to bump the dependent coordinate value by iterating in a loop until a threshold was exceeded. This allowed QuickDraw to draw ovals very quickly.

I had never before heard that the sum of a sequence of consecutive odd numbers always adds to a perfect square. In fact, after looking at it a while, I saw that the rule was even better than Andy says: the sum of the first n odd digits is the square of n. What a bizarre and beautiful result! I had to figure out why it works.

If you’ve ever heard the story of the young Carl Fredrich Gauss adding all the integers from one to one hundred, you’ll know where I got the idea for what follows. Start by writing out the sum as you normally would:

1 + 3 + 5 + ... + (2n-1)

Note that (2n-1) is the nth odd number. Now underneath that sum, write it again, but this time going from high to low.

  1    +   3    +   5    + ... + (2n-1)
(2n-1) + (2n-3) + (2n-5) + ... +   1

Now add these two sums column-wise.

  1    +   3    +   5    + ... + (2n-1)
(2n-1) + (2n-3) + (2n-5) + ... +   1
  2n   +   2n   +   2n   + ... +   2n

Each pair of terms adds to 2n, and there are n of them, so the sum is 2n2. Because we’ve added all the odd numbers twice, this is twice the number we’re looking for. Therefore, the sum of the first n odd digits is n2.

Since I’m no Bill Atkinson and I’m not trying to write a graphics library for a machine with no floating point processor, I have no idea how I could use this fact. But it’s worth knowing just for the sake of it’s beauty and simplicity. And it’s good to know that my middle-aged brain can still do arithmetic.