Tag Archives: natural numbers

Sweet first proof

Posted on by
Reply

Carl Friedrich Gauss (1777 – 1855) by G. Biermann (1824-1908)

Earlier today, enjoying a warm cup of coffee with a friend of mine,we got into a discussion about some math and ended up contemplating on how to prove the sum formula for the n first natural numbers.

The proof is rumored to first have been done by Gauss when he was only a child.

Let S_n = 1 + 2 + 3 + . . . + (n-2) + (n-1) + n

just rewriting the terms backwards we get

S_n = n + (n-1) + (n-2) + \ldots + 3 + 2 +1

now adding these two expressions for the sum we obtain

2 S_n = (n+1) + (n+1) + (n+1) + \ldots+ (n+1) + (n+1) + (n+1)

and since we had n terms in the original sum we now have n \cdot (n+1)‘s, so

2 S_n = (n+1) + (n+1) + (n+1) + \ldots+ (n+1) + (n+1) + (n+1) = n(n+1)

so..

S_n = \frac{ n(n+1) }{2}

Neat. On a computer this would severely reduce the number of operations that would have to be done to compute such a sum. Imagine having to sum up the first million natural numbers and let’s suppose the computer requires one operation for adding, multiplying, dividing and so forth. Then implementing this formula would reduce the numbers of operations from 10^6 to 3.