All right, here's a fun one. It usually comes as part of a story. The story as told is mostly true, though a few details have been a little fudged by the winds of history. It goes like this: when the young Carl Gauss was a small child in school, his teacher wished to kill some time by making the students practice their addition by adding the integers from 1 to 100. Gauss worked for about 10 seconds and turned in the correct answer. His method was exceptionally clever. By doing the problem twice he made the calculation much easier.
First he wrote down the problem, calling the unknown solution N:
Then he did it again, backwards:
It's easy to add the two together. Just do it term by term: 1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101, etc. The two equations are just a string of that term repeated 100 times. As such, we have this:
100 times 101 is 10100. Divide that by 2, and the answer is 5050. Game, set, and match Carl Gauss. The same procedure works just fine for adding to even higher numbers. If you're adding the integers from 1 to n, the same procedure gives you a Sunday Function that will do it in a heartbeat:
If you want to add the integers from one to a million, this will give you the answer a heck of a lot faster than actually sitting down and punching a million numbers into your calculator.
In the grand scheme of things this little trick is the very least of what we owe Gauss. But it's no less a useful thing to know, and I've seen it more than once in useful mathematical physics.
- Log in to post comments
Does the function have a name? Or do you just call the sum of a finite arithmetic progression?
Gauss may have discovered this idea by himself but it was known before him.
I always liked this trick. It was one of those little things one of your friends comes up with in elementary school that no one understands the significance of until they get to college.
Note that this argument really only works for even n. The formula holds for odd n also but then one needs another argument. In fact, generalizing slightly one gets a formula for 1^k + 2^k + 3^k ... + n^k which is related to the Bernoulli numbers.
And you keep going and keep going and after some suspicious-looking hocus pocus you end up with -1/12.
It works perfectly well for odd N.
N is a "triangle number." It is the number of elements in an equilateral trianglular array. Think of bowling pins: N(4) = 10.
Can you extrapolate this to "pyramid numbers?" What is the function that returns the number of tennis balls in a tetrahedral stack, given the number balls along one edge?
The function is also known as "n over 2", one of the binomial coefficients.
Carl, not really. You can do the algebra to show that it works for n odd by using that it works for n-1 which is even. But in that case, what you've really done is just an induction proof in disguise.
@7:
I don't have a nice magic-with-series explanation, but the following argument:
1) We expect Tet(n) to scale roughly with the volume of a tetrahedron. The volume of a tetrahedron is base * height/3. We know our base is Tri(n)=n(n+1)/2, so suddenly it is interesting to ask: what is Tet(n)/Tri(n)?
2
Tet(n)=1, 4, 10, 20, 35, 56...,
Tri(n)=1, 3, 6, 10, 15, 21...,
Tet(n)/Tri(n)=1, 4/3, 5/3, 2, 7/3, 8/3....
3) :-)
4) Ratio is(n+2)/3, so Tet(n)=n(n+1)(n+2)/6
Joshua,
I'm with Carl - I can't see what the problem is with odd n. If Gauss's teacher had asked for the sum of all integers up to 101, his argument would have given that it was 1/2 of 102 (101+1, 100+2,... - I don't think I'll write out the full list!), repeated 101 times. Isn't that right?
Sorry, I'm being stupid here. I'm thinking about the argument in a slightly different fashion then how it was presented here. To use a smaller example let's say we have n=5. So we get 1 and 5 paired to get 6 and same with 2 and 4 but then 3 is left by itself. However, with Matt's way of doing this by actually using two full rows one gets 3+3=6 and it works out.
Huh. I didn't realize you could do it that way. Makes it much nicer. And one doesn't need an ad hoc step for the odd case.
I'll go back into my tea kettle now and try to avoid making any gratuitously brain dead comments the next time I come out.
There is an alternate version of the story in which the numbers from 1 to 100 are "folded" to give 50 pairs:
(1+100) + (2+99) + ...
And you can easily see that the result has to be:
50 * 101 = 5050
This may explain why some people think it only works for even numbers. But for odd numbers you simply fold all but the last one and then add it separately.
I ran across this function thanks to D&D. Was trying to calculate the odds of various dice rolling algorithms for character creation. I liked the feel of this function. Spurred my interest in probabilities.