Gaussian formula

A formula young Gauss discovered when trying to add the numbers 1-100, which goes n(n+1)/2, which is (100*101)/2, or 5050. He found it by discovering that 100+1=101, 99+2=101, 3+98=101...50+51=101. He found out that by wrapping the numbers around, that is adding (100-1) and (1-100) together, he would get the number 100 at every term. He then multiplied 100 times the number of terms, and got his answer, when dividing it by 2, because he had added twice the sum he wanted. Hence the sum of all integers between 1 and 100 is 101*50=5050.

{Editorial note: Thanks to whizkid for helping to correct the errors originally in this node.}

If I remember the story correctly, when Gauss was in grade school, his teacher made his students do long practice problems before they would be allowed to go to play. One day the teacher had them add up all the numbers from one to one hundred, Gauss made the observation discribed above, and handed in the answer almost immediately. The teacher, thinking that Gauss was trying to cheat, scolded Gauss and told him to do the problem "the right way", when the answer Gauss found quickly turned out to be correct, the teacher was, to say the least, stunned.

The Gaussian formula can be generalized to find the sum of any set of consecutive integers from a to b, i.e., a, a+1, a+2, ... b-1, b, where a < b.

For our first generalization let us assume the set consists of positive integers only (a > 0). To calculate the result, we subtract the sum of numbers from 1 to b from the sum of the numbers going from 1 to a - 1:

    sum = (b(b + 1) - (a - 1)(a - 1 + 1)) / 2

This can be simplified to:

    sum = (b + a)(b - a + 1) / 2

Secondly, we need to find the generalization for the case where a and b are negative integers. All we have to do is count the sum of all integers between -b and -a, then reverse the sign. That gives us:

    sum = -(-a + (-b))((-a) - (-b) + 1) / 2

That simplifies to:

    sum = (b + a)(b - a + 1) / 2

Finally, if a is negative and b is positive, we simply need to count the sum of all integers between 1 and -a and subtract it from the sum of integers between 1 and b. That looks like this:

    sum = (b(b + 1) - (-a)(-a + 1)) / 2

This can be simplified to:

    sum = (b + a)(b - a + 1) / 2

Obviously, if a equals -b, the sum is zero, and need not be calculated (though the formula will still work, of course).

As you can see, in all three cases we have obtained the same formula:

        sum = (b + a)(b - a + 1) / 2

One thing not mentioned in whizkid's writeup above is that there's nothing magic about that formula: you can rewrite (b + a)(b - a + 1) / 2 as:

b(b + 1)     a(a + 1)
--------  -  -------- + a
   2            2

meaning that the sum of the numbers between and including two integers a < b is just the sum of the numbers from 1 to b, minus the sum of the numbers from 1 to a, plus a again (since we subtracted it in the sum from 1 to a).

The point is that there's really no extra work to be done to accomodate the fact that a, or b, or both could be negative. The easiest proof of n(n + 1)/2 is by induction (in fact it is done in one of the writeups for induction). While induction is at its core a demonstration that something is equivalent to the natural numbers (an "inductive set"), the negative integers are equivalent to the natural numbers as well (by trivially multiplying by -1) so induction works equally well there.

Since you then automatically know that the sum of the numbers from -1 to -n (or -n to -1 if you prefer) is -n(n + 1)/2, i.e. just the negative of the sum from 1 to n where n is positive, the more general result follows from the ordinary laws of addition.

It's probably also worth mentioning that Gauss, being one of the greatest mathematicians that ever lived, has his name on a mind-bogglingly large number of formulas, theorems and ideas in mathematics, so the name of this node is kind of misleadingly general, although I grant you that "Gauss's Consecutive Integer Sum Formula" is kind of wordy...