2100.33 – Sum of Odd Numbers

What is the sum of the first $n$ odd numbers? There is a simple pattern. Find it!

Solution

Here is the pattern:

\begin{aligned} 1 = 1 &=& 1^2 \\ 1 + 3 = 4 &=& 2^2 \\ 1+3+5 = 9 &=& 3^2 \\ 1+3+5+7 = 16 &=& 4^2 \end{aligned}

In other words, $1 + 3 + \ldots (2n-1) = n^2$ .

The diagram below gives a picture-proof using geometry. By necessity a geometric proof uses an example (here $n = 4$ ) which is supposed to generalize to any $n$ . Do you find this picture-proof convincing, that is do you see how it works for any $n$ ? If you do, then you don't need to read further.

For a more formal proof ('formal' means 'using algebra'), a proof by induction seems a good way to go. Here it is.

INDUCTION PROOF. STEP 1: With $k$ as our working variable,

$k = 1$ gives $1 = \left(\frac{1+k}{2}\right)^2 = \left(\frac{1+1}{2}\right)^2 = 1^2 = 1$ . Good!

INDUCTION PROOF. STEP 2: Now we assume that our conjecture is true for an arbitrary value of $k$ , and see if it's true for $k + 1$ . We want to get $\left(\frac{1 + (k + 2)}{2}\right)^2.$

We assume that $1 + 3 + 5 + ... + k = \left(\frac{1+k}{2}\right)^2.$

And we work with $1 + 3 + 5 + ... + k + (k + 2)$ .

\begin{aligned} 1 + 3 + 5 + ... + k + (k + 2) &=& (\frac{1+k}{2})^2 + k + 2 \\ &=& \frac{1 + 2k + k^2}{4} + k + 2 \\ &=& \frac{1 + 2k + k^2 + 4k + 8}{4} \\ &=& \frac{k^2 + 6k + 9}{4} \\ &=& \frac{(k + 3)^2}{4} \\ &=& \left(\frac{1 + (k + 2)}{2}\right)^2. \end{aligned}

Bingo! Thus $1 + 3 + 5 + ... + n = (\frac{1+n}{2})^2.$

(In teaching induction, some use the analogy of climbing a ladder with an infinite number of rungs. If you can get onto the first rung, and if you know that no matter what rung you're on you can get to the next one, then you can climb the ladder.)