Go to Fun_Math Content Table Sums of Integers and Series

S_{1}[N] = 1 + 2 + 3 + .... + N = (1/2)N(N+1) S_{2}[N] = 1^{2}+ 2^{2}+ 3^{2}+ .... + N^{2}= (1/6)N(N+1)(2N+1) S_{3}[N] = 1^{3}+ 2^{3}+ 3^{3}+ .... + N^{3}= (1/4){N(N+1)}^{2}

In 1636,a simple recursive procedure was derived by Pierre de Fermat (1601- 1665).

S_{k}[N] = a_{k+1}N^{(k+1)}+ a_{k}N^{k}+ a_{k-1}N^{(k-1)}+ .. + a_{1}N + a_{0}(1)

If all the coefficients a_{k+1}, a_{k}, a_{k-1},..., a_{1}, a_{0}are found ,then it is possible to

define S_{k}[N] for any number k.

Let us try to derive S_{4}[N]. By definition S_{4}[k+1] = S_{4}[k] + (k+1)^{4}(2) And we assume according to (1), S_{4}[N] = a_{5}N^{5}+ a_{4}N^{4}+ a_{3}N^{3}+ a_{2}N^{2}+ a_{1}N + a_{0}(3) Since S_{4}[0] = 0, a_{0}= 0. Substituting (1) into (2), and collecting terms including constants a_{*}to the left , the result looks like this.Left Hand Side: Right Hand SideN: 5a^{4}_{5}= 1N: 10a^{3}_{5}+ 4a_{4}= 4N: 10a^{2}_{5}+ 6a_{4}+ 3a_{3}= 6N: 5a^{1}_{5}+ 4a_{4}+ 3a_{3}+ 2a_{2}= 4N: a^{0}_{5}+ a_{4}+ a_{3}+ a_{2}+ a_{1}= 1 The first line gives a_{5}= 1/5. Substituting this to the second line yields a_{4}= 1/4, and so on. Results: a_{5}= 1/5 a_{4}= 1/2 a_{3}= 1/3 a_{2}= 0 a_{1}= -1/30 a_{0}= 0 Finally: S_{4}[N] = (1/5)N^{5}+ (1/2)N^{4}+ (1/3)N^{3}- (1/30)N^{1}= (1/30)N(N+1)(2N+1)(3N^{2}+ 3N - 1)

For example ,using the formula for the first n tetrahedral numbers,

for i = 1 to nIn 1654, Blaise Pascal (1623 - 1662) found an improved method ,using a binomial expansion formula. His method is shown for the case k = 4.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)ni^{3}+ (1/2)ni^{2}+ (1/3)ni and obtained a formula forni^{3}in terms of the sums of the lower powers. Formula for the next higher power isni(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,ni^{4}can be solved. This method is general , but becomes cumbersome for the higher powers.

(i + 1)But neither Fermat nor Pascal could discover the general formula.^{5}- i^{5}= o^{5}_{1}pi^{4}+ o^{5}_{2}pi^{4}+o^{5}_{3}pi^{2}+o^{5}_{4}pi + 1 This is valid for any value of i.Substituting i = 1, 2, ..., n, and add them up all. Then the result isn[(i + 1)^{5}- i^{5}] = 5ni^{4}+ 10ni^{3}+ 10ni^{2}+5ni^{1}+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) = 5ni^{4}+ 10ni^{3}+ 10ni^{2}+5ni^{1}+n1 Sinceni^{3},ni^{3},ni^{3}are already known, we arrive at the following result.ni^{4}= (1/5)n^{5}+ (1/2)n^{4}+ (1/3)n^{3}- (1/30)n

That was done first by Johann Faulhaber(1580 - 1635) in his book

S_{k-1}[N] = 1^{k-1}+ 2^{k-1}+ 3^{k-1}+ .... + N^{k-1}= (1/k)[N^{k}+ o^{k}_{1}pN^{k-1}x(1/2)+ o^{k}_{2}pN^{k-2}x(1/6) + o^{k}_{3}pN^{k-3}x(0) + o^{k}_{4}pN^{k-4}x(-1/30) + . . .](4) where o^{k}_{i}p is the coefficient used in the binomial exapansion,i.e.: (x + y)^{p}= no^{n}_{p}px^{p-n}y^{n}( for n = 0 to p ) (5)

Although constant terms like (1/2), (1/6), 0 , (-1/30), ..., look awkward, it looks like the issue has finally been settled by this generalized formula by Faulhaber.

But for a genius like Jacob (Jacques) Bernoulli (1654 - 1705) ,this is not clean enough.By a stroke of genius, he not only showed the clear process to arrive the Faulhaber's formula (4), but simplified the final formula expressed in such a concise form that even after more than 200 years later,many still wonder how he came up with this brilliant idea. In The posthumous masterpiece,

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)] = S_{1}[n-1]/[n(n-1)] = 1/2 Therefore S_{1}[n-1] = (1/2)[n(n-1)] Replacing n-1 by n,S,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)nn_{1}[n] = (1/2)n(n+1)^{2}-(3/2)nn^{1}+ n(1) = (1/6)n(n-1)(n-2)= (1/6)(n^{3}- 3n^{2}+ 2n) So, (1/2)nn^{2}= (1/6)(n^{3}- 3n^{2}+ 2n) + (3/2)nn^{1}- n(1) but (3/2)nn^{1}= (3/2)(1/2)n(n+1) = (3/4)n(n+1) and n(1) = n Substituting , we have (1/2)nn^{2}=(1/6)n^{3}+ (1/4)n^{2}+ (1/12)n Therefore,SSimilarly the 4-th column gives the following relation. nn(n-1)(n-2)(n-3)/(1x2x3) = (1/6)nn_{2}[n] = nn^{2}= (1/3)n^{3}+ (1/2)n^{2}+ (1/6)n^{3}- nn^{2}+ (11/6)nn - n1 = n(n-1)(n-2)(n-3)/(1x2x3x4) Using nn^{2}= (1/3)n^{3}+ (1/2)n^{2}+ (1/6)n, nn^{1}= (1/2)n(n+1) and n(1) = n (1/6)nn^{3}= (n^{4}- 6n^{3}+ 11n^{2}- 6n)/24 + (1/3)n^{2}+ (1/2)n^{2}- (11/12)n^{2}- (11/12)n + n = (1/24)n^{4}+ (1/12)n^{3}+ (1/24)n^{2}OrSThus , step by step, we can go higher powers with ease, and obtain the following table:_{3}[n] = nn^{3}= (1/4)n^{4}+ (1/2)n^{3}+ (1/4)n^{2}Sum of Powersnn^{1}= (1/2)n^{2}+ (1/2)n^{1}nn^{2}= (1/3)n^{3}+ (1/2)n^{2}+ (1/6)nnn^{3}= (1/4)n^{4}+ (1/2)n^{3}+ (1/4)n^{2}nn^{4}= (1/5)n^{5}+ (1/2)n^{4}+ (1/3)n^{3}- (1/30)n^{1}nn^{5}= (1/6)n^{6}+ (1/2)n^{5}+ (5/12)n^{4}- (1/12)n^{2}nn^{6}= (1/7)n^{7}+ (1/2)n^{6}+ (1/2)n^{5}- (1/6)n^{3}+ (1/42)n^{1}nn^{7}= (1/8)n^{8}+ (1/2)n^{7}+ (7/12)n^{6}- (7/24)n^{4}+ (1/12)n^{2}nn^{8}= (1/9)n^{9}+ (1/2)n^{8}+ (2/3)n^{7}- (7/15)n^{5}+ (2/9)n^{3}- (1/30)nnn^{9}= (1/10)n^{10}+ (1/2)n^{9}+ (3/4)n^{8}- (7/10)n^{6}+ (1/2)n^{4}- (3/20)n^{2}nnBernoulli 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^{10}= (1/11)n^{11}+ (1/2)n^{10}+ (5/6)n^{9}- (1)n^{7}+ (1)n^{5}- (1/2)n^{3}+ (5/66)nsince they are discussed extensively in Bernoulli's book. The formula seems to have connection with binomial theorem, so all those constants are written BBernoulli numbers^{0}=1, B^{1}= 1/2 , B^{2}= 1/6, B^{3}= B^{5}= B^{7}= ... = 0 B^{4}= B^{8}= -1/30, B^{6}= 1/42, B^{10}= 5/66, ... as if they are the powers of B.(They are not !) Then the formula can be written more concisely asSwhere B's power terms inside "{ }" should be interpreted as_{k-1}[N] = 1^{k-1}+ 2^{k-1}+ 3^{k-1}+ .... + N^{k-1}= (1/k)"{(n+B)^{k}- B^{k}}". 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)Bernoulli numbers^{11}- B^{11}} = (1/11)(x^{11}+11B^{1}x^{10}+55B^{2}x^{9}+330B^{4}x^{7}+462B^{6}x^{5}+165B^{8}x^{3}+11B^{10}x) where x = 1000, and B^{1}= 1/2, B^{2}= 1/6, B^{4}= -1/30, B^{6}= 1/42, B^{8}= -1/30,B^{10}= 5/66,

- Conway,J.H., Guy,R.K.: The Book of Numbers. Springer-Verlag,New York, p.106-109, 1995.
- Smith, David Eugene : A Source Book in Mathematics. On the "Bernoulli Numbers". Dover, 1959. Original in 1929.
- Young, Robert M. : Excursions in Calculus. Mathematical Association of America, 1992.

Go to Fun_Math Content Table Sums of Integers and Series

All comments should be sent to Takaya Iwamoto

Last Updated July 9-th, 2006

Copyright 2006 Takaya Iwamoto All rights reserved. .