Sum of integers cubed

### Summary of sums of integer raised to the power of 1, 2 & 3

Here is the summary of what we have shown in this section.
```	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

```

### Now how about Sk[N] when k P 4 ?

It is easy to guess that Sk[N] can be expressed in the polynomial form like
```      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, 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)
```
In 1636,a simple recursive procedure was derived by Pierre de Fermat (1601- 1665).
For example ,using the formula for the first n tetrahedral numbers,
```   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)n
```
But neither Fermat nor Pascal could discover the general formula.
That was done first by Johann Faulhaber(1580 - 1635) in his book Academiae Algebrae(1631). His general formula is
```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)
```

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, Ars Conjectandi(1713),his arguments begins with arranging the "Pascal's" Tirangle in a particular way
```
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,

```

#### References

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. .