Young Gauss
There is an often repeated story that when a teacher assigned as seat work to add the numbers from 1 to 100, young Karl Friedrich Gauss (1777-1855) solved it immediately, discovering the formula n*(n+1)/2 for the sum of the first n natural numbers.
Task. Find the sum of the squares of the first 100 natural numbers.
A solution.
If you guess (correctly) that the sum of squares of the first n numbers is a polynomial of the 3rd degree of n, a0 + a1n + a2n2 + a3n3 = sum, the rest is easy.
(1) Compute the first four values.
| n: | sum: |
| 1 | 1 |
| 2 | 1 + 4 = 5 |
| 3 | 1 + 4 + 9 = 14 |
| 4 | 1 + 4 + 9 + 16 = 30 |
We put in n= 1 in the above polynomial:
a0 + a1 + a2 + a3 = 1
Now n=2:
a0 + 2a1 + 4a2 + 8a3 = 5
Now n=3:
a0 + 3a1 + 9a2 + 27a3 = 14
Now n=4:
a0 + 4a1 +16a2 +64a3 = 30
We’ll use matrices to solve for a0, a1, a2, and a3.
(2) Set [A] and [B] to be,
| [[1 1 1 1] | [[1] | |
| [1 2 4 8] | [5] | |
| [1 3 9 27] | [14] | |
| [1 4 16 64]] | [30]] |
(3) Execute, [A]-1*[B]→[C]. You see,
[A]-1[B]→[C]
[[1.1E-12]
[.1666666667]
[.5]
[.3333333333]
You figure out that these numbers are approximations of the common fractions 1/6, 1/2, and 1/3, and that the first number, 1.1/1012, should be 0, and is the result of a rounding error. So the coefficients of your polynomial are 0, 1/6, 1/2, and 1/3.
(4) You execute 6*[C], and you see,
6*[C]
[[6.6E-12]
[1]
[3]
[2]]
Thus your formula is (n + 3*n2 + 2*n3)/6
(5) Test this formula for some other n, until you start believing that it is right, or (if you can) prove its correctness.
(6) The answer is:
The sum of the squares of the first 100 natural numbers is
(100 + 3*1002 + 2*1003)/6 = 338,350.
Calculus Index