The sum of the first n odd integers
THINGS EVERYONE ELSE KNEW THAT I JUST LEARNED: The sum of the first n odd integers is .
I was reading a Hacker News comment thread and ,as in every other one, someone referred to incompetence among programming interviewees, this time those who couldn’t write a program to calculate the sum of the first n odd integers. This lament is usually phrased in terms of such folks being unable to program FizzBuzz . Having been programming for a long part of my adult life, I figured I could handle this is a number of languages, but I figured I’d try to calculate it in closed form.
Now, I did remember that the sum of the first n integers is . I specifically remember that one because it was always stated along with a story (apocryphal?) about a restless nine year old Gauss being told by his teacher to calculate the sum of the first 100 integers to keep him busy. Well, Gauss being Gauss, he developed the closed form rather than busying himself with the actual arithmetic. My buddy Jon and I used to joke as teenagers : “Hey, Gauss derived the closed form for the sum of the first n integers when he was 9. What are you doing this summer ?”
DERIVATION OF CLOSED FORM:
Let’s piggyback on our 9 year old pal Gauss here and consider what a short sequence of the first n odd integers might look like. In this case n is 5.
O = 1,3,5,7,9
Consider this as part of a larger sequence we construct containing all integers (even and odd), which goes one beyond our sequence of only odd integers
A =- 1,2,3,4,5,6,7,8,9,10.
This sequence is of length 10 here, or 2n in the general case. Note that the larger sequence A is really made up of two smaller sequences, one containing only the even numbers (call this sequence E) and one containing only the odd numbers (the sequence O).
Note also that the sum of the integers in A is the sum of the integers in E + the sum of the integers in O. Our goal is to find the sum of the integers in O. Thanks to Gauss, we know that the sum of A is the sum of the first 2n integers or .
Now the trick is to consider the sum of E, since we can calculate the sum of O as the sum of A minus the sum of E. What does the sum of E look like in a general case?
sum(E) = (2+4+6+….+ 2n) = 2*(1+2+3+ …+n)
But we know the last term in parends there as the sum of the first n integers and can calculate that using Gauss’ formula as , so the sum(E) is just twice that.
Then we can calculate
sum(O) = sum(A) – sum(E) = – 2*
=
=
.
This was a fairly interesting result in that I can’t recall ever running across it before, and that it seems fairly obvious when you look at the progression. I guess teenage me should have spent his summers reading more math and cracking wise a little less.