Little Gödel

One day, little Gödel went to class. For whatever reason—perhaps, an unhappy love affair or a bad hangover—little Gödel’s teacher did not feel like teaching. Instead, he instructed the class to sum all of the integers to one hundred, that is, to calculate $\sum_{i=1}^{100}$ .

The teacher correctly expected most of the class to do what I now consider the most inefficient method of performing this operation; they started as follows:

$1+2 = 3\\ 3 + 3 = 6\\ 4 + 6 = 10\\ ...$

At about this point, little Gödel walks up to his school master and writes 5025 on the chalk board and proclaims, “I’m done!” Perplexed by the rapidity with which little Gödel solved this problem, the instructor inquires him to “show his work”.

Little Gödel goes on to illustrate that while thinking about the problem he realized that
$100 + 0 = 100\\ 99 + 1 = 100\\ 98 + 2 = 100\\ 97 + 3 = 100\\ ...\\ 51 + 49 = 100$

“This means we have $50*100$ or $\frac{1}{2}n*n$ 100’s to sum. But summing the same number over and over is multiplication, that’s easy! However we can’t add 50 to anything–there is no other number between 0 and $n$ that hasn’t been used which will sum to 100. Therefore, at the end of our multiplying spree we must add 50 or $\frac{1}{2}n$ .

Therefore, the sum must be $\frac{1}{2}n * n + \frac{1}{2}n$ .” He quickly simplifies this equation to
$\sum_{i=1}^{n} = \frac{n^2 + n}{2}$

We all learned something that day! Too bad about the teacher, though.