# The Challenge

Your teacher just told you to add every whole number from 1 to 100 together. Do you just start crunching the numbers? 1+2+3+4+5+6+7+8+9+ ... +97+98+99+100 = ? That's going to take so long!

# A Simple Case: 1 + 2 + 3 + 4

Maybe there's a pattern you can leverage here. Let's think about this for a simpler case of adding all the numbers from 1 to 4. That's pretty easy to just do in your head with 1+2+3+4=10.

What does that look like if you make a series of stacks of blocks with 1 block, then 2 blocks, then 3 blocks, and finally, 4 blocks?

Well, there's no quick formula for determining the number of blocks there. If it were a rectangle, you could multiply the number of rows times the number of columns to get the total number of blocks. Hrmmm, you think to yourself. How could you turn that into a rectangle? And, if you know the number of blocks in that rectangle, how would that let you know the number of blue blocks above?

## Make A Rectangle?

Let's say you double the number of blocks and make the new ones red. Now, you have the following setup.

Perhaps, you can rotate the red blocks around so that they combine together with the blue ones to make a rectangle?

Perfect! Now, you have a rectangle that is 4 blocks wide and 5 blocks tall, so there are 4 * 5 or 20 blocks in total. Half of these are the original blue ones, so we can divide 20 by 2 to get 10, and 10 is what you expected to get for the sum of all the numbers from 1 to 4.

## A Possible General Solution

How does this help you figure out the sum of all numbers from 1 to 100? You think on this a moment... If you always can make a rectangle where:

$$width = highest\_number = n$$

$$height = highest\_number + 1 = n+1$$

then you think the sum of all the whole numbers from 1 to any number **n** should be (width * height / 2) for that rectangle, or:

$$total\_sum = \frac {n*(n+1)}{2} = 1 + 2 + 3 + ... + (n - 1) + n$$

So, for the sum of the numbers from 1 to 100, that would be 100 * (100 + 1) / 2 = 10,100 / 2 = 5,050. But, how can you prove that formula always works?

# Prove It

Our formula above, n*(n+1)/2, can be called a function. It takes n as an input, where n refers to the highest number we are going to add when adding all the numbers from 1 to that number. The result is then the sum of all whole numbers from 1 to n. This may be written as:

$$f(n) = \frac {n*(n+1)}{2}$$

where "f(n)" is read as "f of n". It just means that when you write something like f(5), you are saying that 5 is the input, and you replace all instances of n in the function formula with 5. So, you get 5 * (5 + 1) / 2 as the thing that will give you the value of f(5), which is 15 in this case.

You can ask yourself, "Is that formula for f(n) correct for 1?"

You can prove that is correct for n=1 by calculating f(1) = 1 * (1 + 1) / 2 = 1. If you add all the numbers from 1 to 1, you are just adding 1, so that is correct!

Then, you are going to show that if the formula is correct for f(n), it is also correct for f(n+1). Essentially, if it's true for f(1), it's true for f(2), and if it's true for f(2), it's true for f(3), and so on, all the way up to f(100) and beyond (side note: this type of reasoning is called a proof by induction).

Say that you are adding all the numbers up to (n+1):

$$f(n + 1) = 1 + 2 + 3 + ... + (n - 1) + n + (n + 1)$$

and you assume that your formula f(n) is correct for 1 + 2 + 3+ ... + (n-1) + n, then you can write the above as:

$$f(n + 1) = f(n) + (n + 1)$$

You can then replace f(n) with your formula for the sum of 1 to n and then see if you can show that f(n+1) will fit the same pattern as f(n):

$$f(n + 1) = \frac {n*(n+1)}{2} + (n + 1)$$

Multiply the numerator and denominator both by 2 on the term on the right (this is the same as multiplying by 1 which is always allowed):

$$f(n + 1) = \frac {n*(n+1)}{2} + \frac{2*(n + 1)}{2}$$

Combine the terms since a/c + b/c = (a+b)/c:

$$f(n + 1) = \frac {n*(n+1) + 2*(n + 1)}{2}$$

Apply the distributive property where ac + bc = (a + b)c, and where a is n, b is 2, and c is (n+1) in this case:

$$f(n + 1) = \frac {(n+2)*(n+1)}{2}$$

Use the commutative property on the numerator (multiplication can be done in any order):

$$f(n + 1) = \frac {(n+1)*(n+2)}{2}$$

Rewrite (n+2) as ((n+1) + 1) so it matches the pattern of our original formula:

$$f(n + 1) = \frac {(n+1)*((n + 1) + 1)}{2}$$

Let k = n+1, and then replace (n+1) with k everywhere:

$$f(k) = \frac {k*(k + 1)}{2}$$

which is what you expected for f(n + 1) and has the same form as f(n), so the proof by induction holds.

As such, you have confirmed the correctness of your earlier calculation that the sum of all the numbers from 1 to 100 is 5,050. Bravo!

# Clarifications

In this article, we make frequent use of the word "number". However, here we are really only talking about "natural numbers" which are the "positive whole numbers" such a 1, 2, 3, 4, 5, etc. "Number" can generally include values in between whole numbers such as 1.2, 4.666667, pi, etc, and there are an infinite number of those numbers in between any two numbers that are not the same number.

# Further Exercises

What's the sum of all whole numbers from 1 to 1,000?

What's the sum of all whole numbers from 1 to 10,000?

## Use A Computer Program To Check Your Work

Go to DotNetFiddle to easily try out the C# programming language online.

Paste the following code into the script editor and click "Run" button at the top.

```
int highestNumber = 10000;
int total = 0;
int i = 1;
// Keep running the code in the curly braces with i = 1, 2, 3, ..., highestNumber
while (i <= highestNumber)
{
// Add i to our running total.
total = total + i;
i = i + 1;
}
// Print out the total of all the whole numbers from
// 1 to highestNumber added together.
System.Console.WriteLine(total);
```

Try different values for highestNumber in the code.

Try modifying the code so that you also calculate and print the total of all the numbers using the n * (n + 1) / 2 formula.

- Hint: int totalShortcut = highestNumber * (highestNumber + 1) / 2;