Debbie's fascination that the sum of the first n odd numbers is n^{2} is understandable, but this is also easy to prove. The key is that the "triangle sum", the sum of the numbers from 1 to n, is equal to n(n+1)/2. (See note at bottom for a quick visual proof.) The triangle sum is easy to demonstrate by induction; it is often used in a classroom setting as an introductory example of how induction works. In fact it's proved in a writeup in the induction node. Hey wait a minute, *it's proved in Debbie's writeup in the induction node.*

So Debbie--you already know a way to demonstrate this.

n^{2} = 1 + 3 + 5 + 7 + ... + 2n-1
= 1+2+3+4+5+6+7+ ... + 2n-1 *(sum of all integers up to 2n-1)*
- 2 + 4 + 6 + ... +2n *(less the even integers up to 2n)*

But we can represent both of those as a triangle sum T: the first is just T_{2n-1}, the sum of the numbers from 1 to (2n-1), and the second, the sum of the even integers up to 2n is just 2T_{n}, twice the sum of the integers up to n:

= T_{2n-1} - 2*T_{n-1}
(2n-1)*2n (n-1)*n
= --------- - 2*(--------)
2 2
= (2n-1)*n - (n-1)*n
= (2n-1-n+1)*n
= n*n = n^{2}

Pretty neat, but now you need something else to ponder. How about the sum of the first n integers squared (1 + 4 + 9 + ...)? That's trickier, but doable. See the first couple chapters of Concrete Mathematics by Knuth et al if you get stuck; they do a great job with it.

(NOTE: T_{n} is called the "triangle sum" because it can be visualized as a triangle. Imagine a set of bowling pins arranged as:

o
o o
o o o
o o o o
o o o o o
...

The number of pins is clearly 1 + 2 + ... + n, where n is the last row. Now put that triangle together with another triangle arranged upside-down, and you get an n x (n+1) rectangular matrix of pins. So the number of pins in the triangle is half that, n*(n+1)/2.)