Sum of naturals (Gaussian Sum)
We could do it by brute force, but that seems tedious and impractical.
Fortunately, there is a formula to sum them for us.
(n * ( n + 1 )) / 2
------
(100 * 101)/2 = 5050
Simple enough, but why does it work?Let's see if we can get an intuition of why it works.
Why Does It Work
We can think of this formula as calculating the area of a rectangle, and then halving it.
The width of the rectangle is n+1 the height is n .
Why is it n * (n + 1) instead of n * n?
We need to add +1 to shift our second triangle over so that it'll be the same area as the first, if we didn't add the +1 our second triangle would start at 0 instead of 1 and end at n - 1 instead of n (look at the interactive above to see it).
Now, we have constructed a rectangle with two triangles of equal area.
Each triangle has an area that is our answer because they are constructed by drawing 1...n.
Therefore, we get our answer by dividing by 2.
The Story Behind This Formula
One day a teacher gave his class some busy work, he made his students sum the numbers 1 to 100.
He was surprised when one of his students finished quickly.
The student's name was Carl Friedrich Gauss. He had devised the formula (n * (n + 1))/2 by noticing that if you listed 1...100 then underneath it listed 100...1 each column would add up to 101, that is 100 101 times or 100 * 101.
Therefore , 100 * 101 divided by 2 is the answer.
Gauss was 9 at the time.
Resources