What is the sum of 1 8

back • Math pages overview
Sum formulas up to n10 • ... for cube numbers

The sum of the natural numbers from 1 to n and the square numbers to n²

On this page the empirical formulas are derived "naively" (by appropriate writing) and proven by complete induction.

Sum 1 + 2 + 3 + ... + n

The anecdote of little Carl Friedrich Gauss has been handed down that he surprised his village school teacher, who wanted to keep the group of little ones busy for a long time by having them work out the sum of the numbers from one to a hundred. After a few moments, Carl Friedrich had the right solution ready. He must have noticed that the numbers can be paired sensibly: the first with the last, the second with the penultimate - the result is always the same sum, namely 100 + 1 (generally n + 1). Since there are 50 (generally n / 2) such pairs, the sum had to be (101) * 50.

1  +   100  = 101
2  +   99  = 101
3  +   98  = 101
4  +   97  = 101
······     ···
······     ···
49  +   52  = 101
50  +   51  = 101
5050

Little Gauss had discovered the sum formula:

n
Σ
i = 1
i = 1 + 2 + 3 + ... + n =n (n + 1)
2

The formula also applies to odd n. The middle number has no partner when pairing. So you form (n-1) / 2 pairs with the respective sum (n + 1), add the middle number (n + 1) / 2 and you also get this sum formula:

   n - 1
2
(N + 1)  +   n + 1
 2 
  =  (n-1) (n + 1) + n + 1
2
  =  n² - 1 + n + 1
2
  =  n (n + 1)
2
Proof by complete induction

The proof procedure of complete induction can be compared a little with the complete falling of an (infinitely long) row of dominoes. In order for such a row to fall over without being broken off, basically two conditions must be met:

(1)  You have to knock down a first stone.
(2)  Every stone must knock over its successor when it falls.

It is quite similar with the complete induction of propositions whose definition set is the set of natural numbers. The falling of a certain domino corresponds to the validity of the statement for a certain natural number:

(1)  The statement must be for a smallest number n0 be valid. This can usually be calculated very easily.
(2)  From the validity of the statement for n, the validity for the successor n + 1 must follow. This must be shown in general (not with concrete numerical values ​​for n).

We denote the sum of the natural numbers from 1 to n by S (n) and try to prove that S (n) = ½ · n · (n + 1) for all n ∈N is.

Condition (1), which is also called induction start, is quickly ticked off. We calculate the sum of the natural numbers up to 1, which is of course 1, according to the formula: S (1) = ½ · 1 · (1 + 1) = ½ · 1 · 2 = 1. Correct.

For condition (2), which is also called the induction step, we assume that the statement holds for any n, ie S (n) = ½ · n · (n + 1) and S (n + 1) = ½ · (n +1) · (n + 1 + 1) = ½ · (n + 1) · (n + 2) are correct.

Now you can also calculate the sum of the natural numbers up to n + 1, i.e. S (n + 1), by taking the sum of the natural numbers up to n and adding the next number n + 1. So one can write S (n + 1) as S (n) + n + 1. That is certainly correct if S (n) gives the correct sum up to n, and we assume that.

If one can now prove that S (n) + n + 1 is identical to S (n + 1) according to the formula, then condition (2) is fulfilled:

n (n + 1) S (n) + n + 1 = ——————— + n + 1 2 n² + n + 2n + 2 = ——————————————— —— 2 (n + 1) (n + 2) = ———————————— = S (n + 1) J 2

The correctness of S (n) thus implies the correctness of S (n + 1), which proves the statement for all natural numbers n ≥ 1.

The sum of the natural numbers from 1 to n
n (n + 1) 1 + 2 + 3 + 4 + ... + n = ———————————2

 

The sum of the square numbers from 1 to n²

Unfortunately, the square numbers 1, 4, 9, 16, 25, 36, etc. cannot be paired as nicely as the natural numbers, so that the empirical formula cannot easily be found naively. (In any case, I don't know that little Gauss would have shaken this formula out of his sleeve ...)

First we consider the differences between consecutive squares:

0149162536496481100...
Differences:135791113151719...

It is quickly proven that the differences form the complete set of (positive) odd numbers. One simplifies the term for the general difference between the square number n² and its predecessor (n-1) ²:
n² - (n-1) ² = n² - (n² - 2n + 1) = n² - n² + 2n - 1 = 2n - 1
and get 2n-1 as the difference between (n-1) ² and n².
The term 2n-1 yields for n∈N exactly the set of (positive) odd numbers.

Now the square number n² can also be written as the sum of the differences up to n². For example, 7² = 49 equals 1 + 3 + 5 + 7 + 9 + 11 + 13.

n² can thus be represented as 1 + 3 + 5 + ... + 2n-1.

With this knowledge, the square numbers can be written down a little more "linearly". The sum of the square numbers up to 5² would be the sum of these numbers:

9 7 7 5 5 5 3 3 3 3 1 1 1 1 1 ——— ——— ——— ——— ——— =1² =2² =3² =4² =5²

Obviously there are 1 + 2 + 3 + 4 + 5 numbers in this triangle. The number of the numbers in the triangle for n² is the sum of the natural numbers from 1 to n: S (n), the formula of which we have already proven above.

Unfortunately, the numbers in the triangle can still not be paired as nicely as the one above.

But you can get further with the following trick. We rearrange the numbers twice and add them in places to the original triangle. The sum of the numbers in the triangle that is obtained is then three times the sum of the square in question.

First we move the columns in the triangle so that the triangle becomes nicely symmetrical:

9 7 7 5 5 5 3 3 3 3 1 1 1 1 1

Now we mirror the numbers once on the bisector from bottom right to top left and once on the other axis:

1 1 3 1 1 3 5 3 1 1 3 5 7 5 3 1 1 3 5 7 9 7 5 3 1 1 3 5 7 9

If you add the numbers of the three triangles in places, you get

      11
11  11
11  11  11
11  11  11  11
11  11  11  11  11

Wow!

That there are always the same numbers everywhere, i.e. in all tripled sum of squares, is shown in the appendix (see below). At first only, Which Pay it is. Let's look at the number at the top. In the example it is the sum of 1 + 1 + 9. The 9 is the largest difference in the representation of n² which, as we saw above, equals 2n-1.
Add the two ones and you get 2n + 1. In fact, this results in 11 for n = 5.

We now remember how many numbers are in the triangle, or count them again to be on the safe side: There are 1 + 2 + 3 + 4 + 5 elves, i.e. S (n) pieces.

The general tripled Triangle therefore consists of the n (n + 1) / 2 times occurring number 2n + 1, or of S (n) times (2n + 1).

We have already noticed that this is three times the sum of the squares in question, which means that S (n) · (2n + 1) simply has to be divided by 3 to get the sum of squares formula:

S (n) · (2n + 1) n (n + 1) · (2n + 1) n (n + 1) (2n + 1) ———————————— = ———— —————————— = ————————————— 3 2 · 3 6

This is the formula for the sum of the square numbers 1² + 2² + 3² + ... n².

 

induction

Here, too, the proof by complete induction. We denote the "alleged" sum of the square numbers 1² + 2² + ... + n², as the formula seems to provide, with Q (n).

(1): We calculate that Q (1) is the sum of the squares up to 1²: Q (1) = 1 · 2 · 3/6 = 1. Correct.

(2): Let Q (n) be correct. Then Q (n + 1) = (n + 1) (n + 2) (2 (n + 1) +1) / 6 = (n + 1) (n + 2) (2n + 3) / 6

If Q (n) is the sum of the squares up to n², then Q (n) + (n + 1) ² is certainly the sum of the squares up to (n + 1) ². We show that Q (n) + (n + 1) ² = Q (n + 1):

n (n + 1) (2n + 1) Q (n) + (n + 1) ² = ————————————— + (n + 1) ² 6 2n³ + 3n² + n 6n² + 12n + 6 = ——————————————— + ——————————————— 6 6 2n³ + 9n² + 13n + 6 = ———— ————————————————— 6 (n + 1) (n + 2) (2n + 3) Q (n + 1) = —————————— ——————— (see above) 6 2n³ + 9n² + 13n + 6 = ————————————————————— 6

This proves the formula.
 

The sum of the square numbers from 1 to n²
n (n + 1) (2n + 1) 1² + 2² + 3² + 4² + ... + n² = ———————————————————6

 


© Arndt Brünner, October 9, 2004
Version: October 1, 2006
→ Sum formulas up to n10
→ Proof for the sum of the cube numbers

 

 

attachment

Proof that in the triple difference triangle there is 2n + 1 in all places.

We number the lines of the difference triangles from bottom to top with i (1 ≤ i ≤ n) and the position within the line with j. The number in the i. Line at the j. Place we call z (i, j).

For the original triangle, z (i, j) only depends on the row.
It is the highest difference in each case, so z (i, j) = 2i-1.
9 7 7 5 5 5 3 3 3 3 1 1 1 1 1

We consider the two mirrored triangles z '(i, j) and z "(i, j) together, especially with regard to their sum. The symmetry of these triangles results in identical numbers when adding in each row, namely 1 plus the largest number in the row. The largest number depends on row i and n. In the top row it is 2n-1. Since we number the rows from bottom to top, unfortunately we cannot use 2i-1, because that In the example, the top row would not be 1, but 9. We have to replace i by n + 1-i, so that, for example, in the bottom row we calculate with n instead of i = 1 and in the top row correctly instead of i = 5 with 5 + 1-5 = 1.

In the i. Line is 2 (n + 1-i) -1 plus 1, so z '(i, j) + z "(i, j) = 2n-2i + 2. These numbers no longer depend on the column number .

1 1 3 1 1 3 5 3 1 + 1 3 5 7 5 3 1 1 3 5 7 9 7 5 3 1 1 3 5 7 9 ——————————————————————————————————— 2 4 4 6 6 6 8 8 8 8 10 10 10 10 10

As a result, the sum of the three triangles for all numbers in the i. Row equals z (i, j) + z '(i, j) + z "(i, j) = 2i-1 + 2n-2i + 2 = 2n + 1.
So it depends neither on the column nor on the row, but only on n, and is, as was to be proven, constant 2n + 1.