Go to Fun_Math Content Table Sums of Integers and Series
S1[N] = 1 + 2 + 3 + .... + N = (1/2)N(N+1)
S2[N] = 12 + 22 + 32 + .... + N2 = (1/6)N(N+1)(2N+1)
S3[N] = 13 + 23 + 33 + .... + N3 = (1/4){N(N+1)}2
In 1636,a simple recursive procedure was derived by Pierre de Fermat (1601- 1665).
Sk[N] = ak+1N(k+1) + akNk + ak-1N(k-1) + .. + a1N + a0 (1)
If all the coefficients ak+1, ak, ak-1 ,..., a1, a0 are found ,then it is possible to
define Sk[N] for any number k.
Let us try to derive S4[N]. By definition S4[k+1] = S4[k] + (k+1)4 (2) And we assume according to (1), S4[N] = a5N5 + a4N4 + a3N3 + a2N2 + a1N + a0 (3) Since S4[0] = 0, a0 = 0. Substituting (1) into (2), and collecting terms including constants a* to the left , the result looks like this. Left Hand Side: Right Hand Side N4 : 5a5 = 1 N3 : 10a5 + 4a4 = 4 N2 : 10a5 + 6a4 + 3a3 = 6 N1 : 5a5 + 4a4 + 3a3 + 2a2 = 4 N0 : a5 + a4 + a3 + a2 + a1 = 1 The first line gives a5 = 1/5. Substituting this to the second line yields a4 = 1/4, and so on. Results: a5 = 1/5 a4 = 1/2 a3 = 1/3 a2 = 0 a1 = -1/30 a0 = 0 Finally: S4[N] = (1/5)N5 + (1/2)N4 + (1/3)N3 - (1/30)N1 = (1/30)N(N+1)(2N+1)(3N2 + 3N - 1)
for i = 1 to n ni(i + 1)(i + 2)/(1.2.3) = n(n + 1)(n + 2)(n + 3)/(1.2.3.4) He expanded the left hand side as (1/6)ni3 + (1/2)ni2 + (1/3)ni and obtained a formula for ni3 in terms of the sums of the lower powers. Formula for the next higher power is ni(i + 1)(i + 2)(i + 3)/(1.2.3.4) = n(n + 1)(n + 2)(n + 3)(n + 4)/(1.2.3.4.5) By expanding the left hand side as before, ni4 can be solved. This method is general , but becomes cumbersome for the higher powers.In 1654, Blaise Pascal (1623 - 1662) found an improved method ,using a binomial expansion formula. His method is shown for the case k = 4.
(i + 1)5 - i5 = o51pi4 + o52pi4 +o53pi2 +o54pi + 1 This is valid for any value of i.Substituting i = 1, 2, ..., n, and add them up all. Then the result is n[(i + 1)5 - i5] = 5ni4 + 10ni3 + 10ni2 +5ni1 + n1 In the left hand side, many terms cancells out, and only the first and last terms remain. So the result is (n + 1)5 - (n + 1) = 5ni4 + 10ni3 + 10ni2 +5ni1 + n1 Since ni3,ni3,ni3 are already known, we arrive at the following result. ni4 = (1/5)n5 + (1/2)n4 + (1/3)n3 - (1/30)nBut neither Fermat nor Pascal could discover the general formula.
Sk-1[N] = 1k-1 + 2k-1 + 3k-1 + .... + Nk-1 = (1/k)[Nk + ok1pNk-1x(1/2)+ ok2pNk-2x(1/6) + ok3pNk-3x(0) + ok4pNk-4x(-1/30) + . . .] (4) where okip is the coefficient used in the binomial exapansion,i.e.: (x + y)p = nonppxp-nyn ( for n = 0 to p ) (5)
Pascal's Triangle left adjusted
Column #
1 2 3 4 5 6 7 8 9 10 11 12
-------------------------------------------------------
Row #
1 1 0 0 0 0 0 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0 0 0 0 0
3 1 2 1 0 0 0 0 0 0 0 0 0
4 1 3 3 1 0 0 0 0 0 0 0 0
5 1 4 6 4 1 0 0 0 0 0 0 0
6 1 5 10 10 5 1 0 0 0 0 0 0
7 1 6 15 20 15 6 1 0 0 0 0 0
8 1 7 21 35 35 21 7 1 0 0 0 0
9 1 8 28 56 70 56 28 8 1 0 0 0
10 1 9 36 84 126 126 84 36 9 1 0 0
11 1 10 45 120 210 252 210 120 45 10 1 0
12 1 11 55 165 330 462 462 330 165 55 11 1
Let us take a look at column #2 downward beginning with the first 0.
Adding all the numbers up to row #4 ,for example, and dividing the sum by number of terms(=4)
multiplied by the last number (=3), we get (0 + 1 + 2 + 3)/(4 x 3) = 1/2.
If we go one more, then (0+ 1 + 2 + 3 + 4)/(5 x 4) = 1/2 again !.
This holds true for any row numbers, and if the same operation is done up to n-th row,
the result will be
[0 + 1 + 2 + 3 + ... + (n-1)]/[n x (n-1)] = S1[n-1]/[n(n-1)] = 1/2
Therefore
S1[n-1] = (1/2)[n(n-1)]
Replacing n-1 by n,
S1[n] = (1/2)n(n+1)
,which is a sum of natural numbers we already know.
Now let us go to the Column #3. The result up to 4-th row is (0 + 0 + 1 + 3 )/(4 x 3) = 1/3.
And 5-th row result is (0 + 0 + 1 + 3 + 6)/(5 x 6) = 1/3 !
So doing this ratio taking operation up to n-th row, we get
(Summation up to n-th row)/(n x n-th row number) = 1/3
Since the n-th row entry of the 3-rd column is expressed as (n-1)(n-2)/(1x2),
summation up to n-th row is
n{(1/2)(n-1)(n-2)} = (1/2)nn2 -(3/2)nn1 + n(1)
= (1/6)n(n-1)(n-2)= (1/6)(n3 - 3n2 + 2n)
So, (1/2)nn2 = (1/6)(n3 - 3n2 + 2n) + (3/2)nn1 - n(1)
but (3/2)nn1 = (3/2)(1/2)n(n+1) = (3/4)n(n+1)
and n(1) = n
Substituting , we have
(1/2)nn2 =(1/6)n3 + (1/4)n2 + (1/12)n
Therefore, S2[n] = nn2 = (1/3)n3 + (1/2)n2 + (1/6)n
Similarly the 4-th column gives the following relation.
nn(n-1)(n-2)(n-3)/(1x2x3) = (1/6)nn3 - nn2 + (11/6)nn - n1 = n(n-1)(n-2)(n-3)/(1x2x3x4)
Using nn2 = (1/3)n3 + (1/2)n2 + (1/6)n,
nn1 = (1/2)n(n+1) and n(1) = n
(1/6)nn3 = (n4 - 6n3 + 11n2 - 6n)/24 + (1/3)n2 + (1/2)n2 - (11/12)n2 - (11/12)n + n
= (1/24)n4 + (1/12)n3 + (1/24)n2
Or S3[n] = nn3 = (1/4)n4 + (1/2)n3 + (1/4)n2
Thus , step by step, we can go higher powers with ease, and obtain the following table:
Sum of Powers
nn1 = (1/2)n2 + (1/2)n1
nn2 = (1/3)n3 + (1/2)n2 + (1/6)n
nn3 = (1/4)n4 + (1/2)n3 + (1/4)n2
nn4 = (1/5)n5 + (1/2)n4 + (1/3)n3 - (1/30)n1
nn5 = (1/6)n6 + (1/2)n5 + (5/12)n4 - (1/12)n2
nn6 = (1/7)n7 + (1/2)n6 + (1/2)n5 - (1/6)n3 + (1/42)n1
nn7 = (1/8)n8 + (1/2)n7 + (7/12)n6 - (7/24)n4 + (1/12)n2
nn8 = (1/9)n9 + (1/2)n8 + (2/3)n7 - (7/15)n5 + (2/9)n3 - (1/30)n
nn9 = (1/10)n10 + (1/2)n9 + (3/4)n8 - (7/10)n6 + (1/2)n4 - (3/20)n2
nn10 = (1/11)n11 + (1/2)n10 + (5/6)n9 - (1)n7 + (1)n5 - (1/2)n3 + (5/66)n
Bernoulli arrived the formula, which is basically the same as Faulhaber's result, and he
gave full credit to Faulhaber, but the constants in the formula are known as the
Bernoulli numbers since they are discussed extensively in Bernoulli's book.
The formula seems to have connection with binomial theorem, so all those constants are
written
B0=1, B1 = 1/2 , B2 = 1/6, B3 = B5 = B7 = ... = 0
B4= B8 = -1/30, B6 = 1/42, B10 = 5/66, ...
as if they are the powers of B.(They are not !)
Then the formula can be written more concisely as
Sk-1[N] = 1k-1 + 2k-1 + 3k-1 + .... + Nk-1 = (1/k)"{(n+B)k - Bk}"
where B's power terms inside "{ }" should be interpreted as Bernoulli numbers .
This is a better looking formula !!
Bernoulii stated in his book that he could calculate the sum of the tenth power of the
first 1000 integers in 7 and half minutes !!
If any of you wants to challenge him, here is the formula you can use to beat him.
(1/11){(x+B)11 - B11} = (1/11)(x11+11B1x10+55B2x9+330B4x7+462B6x5+165B8x3+11B10x)
where x = 1000, and
B1 = 1/2, B2 = 1/6, B4 = -1/30,
B6 = 1/42, B8 = -1/30,B10 = 5/66,
All comments should be sent to Takaya Iwamoto
Last Updated July 9-th, 2006
Copyright 2006 Takaya Iwamoto All rights reserved.