Hi all,

anybody recommends a fastest way to compute the

sum(k^3, k=1...n)?

I tried hard to remember this formula, but keep forgetting it...

Everytime it took me quite a while to derive it...

Any fastest way?

thanks a lot!

From:	Stephen Montgomery-Smith
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 16:29:11 GMT

lucy wrote:
> Hi all,
>
> anybody recommends a fastest way to compute the
>
> sum(k^3, k=1...n)?
>
> I tried hard to remember this formula, but keep forgetting it...
>

If you want to *remember* it - it is

( sum(k, k=1..n) )^2

From:	Robert Israel
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	23 Jan 2005 06:03:11 GMT

In article , lucy wrote:

>anybody recommends a fastest way to compute the

>sum(k^3, k=1...n)?

I don't know if it's "fastest", but my favourite is this one:

(k + 1/2)^4 - (k - 1/2)^4 = 4 k^3 + k

Sum both sides from k=1..n, noticing that the left side is
a telescoping series. You do remember the formula for
sum(k, k=1..n), I hope. If your sum is S,

(n+1/2)^4 - (1/2)^4 = 4 S + n(n+1)/2

so S = ((n+1/2)^4 - (1/2)^4)/4 - n(n+1)/8

Then this can be simplified to the more usual form.

> I tried hard to remember this formula, but keep forgetting it...

Just remember that it's the square of sum(k,k=1..n).

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

From:	kiki
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 13:02:09 -0800

"Robert Israel" wrote in message
news:csvemv$3vb$1@nntp.itservices.ubc.ca...
> In article , lucy
> wrote:
>
>>anybody recommends a fastest way to compute the
>
>>sum(k^3, k=1...n)?
>
> I don't know if it's "fastest", but my favourite is this one:
>
> (k + 1/2)^4 - (k - 1/2)^4 = 4 k^3 + k
>
> Sum both sides from k=1..n, noticing that the left side is
> a telescoping series. You do remember the formula for
> sum(k, k=1..n), I hope. If your sum is S,
>
> (n+1/2)^4 - (1/2)^4 = 4 S + n(n+1)/2
>
> so S = ((n+1/2)^4 - (1/2)^4)/4 - n(n+1)/8
>
> Then this can be simplified to the more usual form.
>
>> I tried hard to remember this formula, but keep forgetting it...
>
> Just remember that it's the square of sum(k,k=1..n).
>
> Robert Israel israel@math.ubc.ca
> Department of Mathematics http://www.math.ubc.ca/~israel
> University of British Columbia Vancouver, BC, Canada

I think this is really a nice trick! Robert always has some nice tricks!

From:	Igor Khavkine
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 01:27:09 -0500

On Sat, 22 Jan 2005 17:36:34 -0800, lucy wrote:

> Hi all,
>
> anybody recommends a fastest way to compute the
>
> sum(k^3, k=1...n)?
>
> I tried hard to remember this formula, but keep forgetting it...
>
> Everytime it took me quite a while to derive it...
>
> Any fastest way?

I like the method of Pascal's triangle, observe:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
....

The formula for the n'th element of the m'th diagonal row is the well
known binomial coefficient (n+m)!/(n!m!). To convince your self that it's
correct, just check it for a few n's and m's (start counting from m=0 and
n=0):

m=0, n!/n!=1: 1 1 1 1 1 ...
m=1, (n+1)!/n!=(n+1): 1 2 3 4 ...
m=2, (n+2)!/n!/2=(n+1)(n+2)/2: 1 3 6 ...
....

The important property of Pascal's triangle is that every number in it
is the sum of the two numbers directly above it. This property is
actually equivalent to the n'th number in the m'th row being the sum
of the n+1 numbers in the (m-1)'th row directly above it. This is not
as hard as it sounds, just observe:

m=1: 1 = 1, 2 = 1 + 1, 3 = 1 + 1 + 1, ...
m=2: 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, ...
m=3: 1 = 1, 4 = 1 + 3, ...
....

Writing this identity in terms of the formulas for the binomial
coefficients gives us:

sum_{k=0 to n} (k+m-1)!/(k!(m-1)!) = (k+m)!/(k!m!) or
sum_{k=0 to n} (k+1)(k+2)...(k+m-1)/(m-1)! = (k+1)(k+2)...(k+m)/m!

To see why this is useful, let me look at the case m = 2 in detail:

sum_{k=0 to n} (k+1) = (sum_{k=0 to n} k) + (n+1) = (n+1)(n+2)/2
sum_{k=0 to n} k = n(n+1)/2.

Ah but this is the familiar formula for the sum of an arithmetic
progression. Notice how the answer was found. The left hand side of the
original equality contained the desired sum of k from k=0 to n and an
extra term, the sum of 1's from k=0 to n. But we already know how to sum
that, the answer is just n+1 which we then subtract from the right hand
side and which is also known. And voila, the sum of the first power of k
from 0 to n is found.

How about case m=3? Observe:

sum_{k=0 to n} (k+1)(k+2)/2 = 1/2 sum_{k=0 to n} (k^2 + 3k + 2)
1/2 (sum_{k=0 to n} k^2) + 3n(n+1)/2 + (n+1) = (n+1)(n+2)(n+3)/6
sum_{k=0 to n} k^2 = (n+1)(n+2)(n+3)/3 - 3n(n+1) - 2(n+1)
= simplify here if you wish ...

Tada! We have derived the formula for the sum of squares from 0 to n.
Once again, the left hand side contained a sum of k^2 and other terms.
But we already know how to sum the other terms, namely 3k and 2, so
we perform those sums and subtract them from the already known
right hand side. The only thing that remains is to multiply the
whole equation by 2 to get rid of the 1/2 prefactor.

You can derive the sum of cubes by considering the row m=4, the
sum of fourth powers by considering the row m=5, etc. You can go
as high as you wish. I think this method is pretty easy to remember
and hope this is what you were looking for.

Igor

From:	Ignacio Larrosa Cañestro
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 23:00:47 +0100

En el mensaje:csuv33$btc$1@news.Stanford.EDU,
lucy escribió:
> Hi all,
>
> anybody recommends a fastest way to compute the
>
> sum(k^3, k=1...n)?
>
> I tried hard to remember this formula, but keep forgetting it...
>
> Everytime it took me quite a while to derive it...
>
> Any fastest way?
>
> thanks a lot!

2^4 = (1 + 1)^4 = 1^4 + 4*1^3 + 6*1^2 + 4*1 + 1
3^4 = (2 + 1)^4 = 2^4 + 4*2^3 + 6*2^2 + 4*2 + 1
4^4 = (3 + 1)^3 = 3^4 + 4*3^3 + 6*3^2 + 4*3 + 1
....
(n + 1)^4 = n^4 + 4*n^3 + 6*n^2 + 4*n + 1

Adding and canceling terms,

(n+1)^4 = 1 + 4*Sum(k^3, k, 1, n) + 6*Sum(k^2, k, 1, n) + 4*Sum(k, k, 1, n)
+ n*1 ==>

Sum(k^3, k, 1, n) = (1/4)((n + 1)^4 - 6*Sum(k^2, k, 1, n) - 4*Sum(k, k, 1,
n) - (n + 1)) =

= (1/4)((n + 1)^4 - 6*n(n+1)(2n+1)/6 - 4*n(n+1)/2 - (n + 1))

= ((n+1)/4)((n+1)^3 - n(2n+1) - 2n - 1) = ((n+1)/4)(n^3 + n^2) =
n^2(n+1)^2/4 = (n(n+1)/2)^2

By the way, Sum(k^3, k, 1, n) = (Sum(k, k, 1, n)^2.

The method is easily generalizable for Sum(k^m, k, 1, n).

--
Best regards,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUITARMAYUSCULAS@mundo-r.com

From:	Christian Bau
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 10:24:27 +0000

In article ,
"lucy" wrote:

> Hi all,
>
> anybody recommends a fastest way to compute the
>
> sum(k^3, k=1...n)?
>
> I tried hard to remember this formula, but keep forgetting it...
>
> Everytime it took me quite a while to derive it...
>
> Any fastest way?

Make a guess that it is a polynomial of degree four, that is

sum(k^3, k=1...n) = p4 (n).

Then obviously p4(n) = p4(n-1) + n^3. Expand the polynomial p4(n-1) and
you get some very simple equations for the coefficients.

From:	Jannick
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 02:42:05 +0100

On 1/23/2005 2:36 AM, lucy wrote:

>Hi all,
>
>anybody recommends a fastest way to compute the
>
>sum(k^3, k=1...n)?
>
>I tried hard to remember this formula, but keep forgetting it...
>
>Everytime it took me quite a while to derive it...
>
>Any fastest way?
>
>thanks a lot!
>
>
>
>
the result is a polynomial of degree 4.

From:	Jannick
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 03:41:40 +0100

On 1/23/2005 2:42 AM, Jannick wrote:

> On 1/23/2005 2:36 AM, lucy wrote:
>
>> Hi all,
>>
>> anybody recommends a fastest way to compute the
>>
>> sum(k^3, k=1...n)?
>>
>> I tried hard to remember this formula, but keep forgetting it...
>>
>> Everytime it took me quite a while to derive it...
>>
>> Any fastest way?
>>
>> thanks a lot!
>>
> the result is a polynomial of degree 4.

let p(n) be the polynomial (of degree 4). write p(n) = a4 n^4 + ... +
a0. then apply it to p(n+1) - p(n) = (n+1)^3 or determine the constants
ai by calculating p(n) for 5 natural number n.

From:	igor.kh at gmail.com
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	23 Jan 2005 01:52:48 -0800

lucy wrote:
> Hi all,
>
> anybody recommends a fastest way to compute the
>
> sum(k^3, k=1...n)?
>
> I tried hard to remember this formula, but keep forgetting it...
>
> Everytime it took me quite a while to derive it...
>
> Any fastest way?

I like the method of Pascal's triangle, observe:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
....

The formula for the n'th element of the m'th diagonal row is the well
known
binomial coefficient (n+m)!/(n!m!). To convince your self that it's
correct,
just check it for a few n's and m's (start counting from m=0 and n=0):

m=0, n!/n!=1: 1 1 1 1 1 ...
m=1, (n+1)!/n!=(n+1): 1 2 3 4 ...
m=2, (n+2)!/n!/2=(n+1)(n+2)/2: 1 3 6 ...
....

The important property of Pascal's triangle is that every number in it
is the sum of the two numbers directly above it. This property is
actually equivalent to the n'th number in the m'th row being the sum
of the n+1 numbers in the (m-1)'th row directly above it. This is not
as hard as it sounds, just observe:

m=1: 1 = 1, 2 = 1 + 1, 3 = 1 + 1 + 1, ...
m=2: 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, ...
m=3: 1 = 1, 4 = 1 + 3, ...
....

Writing this identity in terms of the formulas for the binomial
coefficients
gives us:

sum_{k=0 to n} (k+m-1)!/(k!(m-1)!) = (k+m)!/(k!m!) or
sum_{k=0 to n} (k+1)(k+2)...(k+m-1)/(m-1)! = (k+1)(k+2)...(k+m)/m!

To see why this is useful, let me look at the case m = 2 in detail:

sum_{k=0 to n} (k+1) = (sum_{k=0 to n} k) + (n+1) = (n+1)(n+2)/2
sum_{k=0 to n} k = n(n+1)/2.

Ah but this is the familiar formula for the sum of an arithmetic
progression.
Notice how the answer was found. The left hand side of the original
equality
contained the desired sum of k from k=0 to n and an extra term, the sum
of 1's from k=0 to n. But we already know how to sum that, the answer
is just
n+1 which we then subtract from the right hand side and which is also
known.
And voila, the sum of the first power of k from 0 to n is found.

How about case m=3? Observe:

sum_{k=0 to n} (k+1)(k+2)/2 = 1/2 sum_{k=0 to n} (k^2 + 3k + 2)
1/2 (sum_{k=0 to n} k^2) + 3n(n+1)/2 + (n+1) = (n+1)(n+2)(n+3)/6
sum_{k=0 to n} k^2 = (n+1)(n+2)(n+3)/3 - 3n(n+1) - 2(n+1)
= simplify here if you wish ...

Tada, we have derived the formula for the sum of squares from 0 to n.
Once again, the left hand side contained a sum of k^2 and other terms.
But we already know how to sum the other terms, namely 3k and 2, so
we perform those sums and subtract them from the already known
right hand side. The only thing that remains is to multiply the
whole equation by 2 to get rid of the 1/2 prefactor.

You can derive the sume of cubes by considering the row m=4, the
sum of fourth powers by considering the row m=5, etc. You can go
as high as you wish. I think this method is pretty easy to remember
and hope this is what you were looking for.

Igor

From:	igor.kh at gmail.com
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	23 Jan 2005 01:50:47 -0800

From:	Daniel Yoo
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 02:23:49 +0000 (UTC)

lucy wrote:
: Hi all,

: anybody recommends a fastest way to compute the

: sum(k^3, k=1...n)?

: I tried hard to remember this formula, but keep forgetting it...

: Everytime it took me quite a while to derive it...

Hello Lucy,

I've been reading Concrete Mathematics, and the book gives a simple
derivation for k^3 by using finite calculus on Page 51.

If we define a falling factorial power k^(m_) as

k^(m_) = k*(k-1)*(k-2)*...*(k-m+1),

then we can do a finite "integration" of a factorial power like this:

sum(k^(m_), k=0..n-1) = (1/m+1) * n^(m+1_)

And this looks almost like the rule for integrating regular powers in
regular calculus.

For example, since k^1 = k^(1_), we have

sum(k, k=0..n-1)

= sum(k^(1_), k=0..n-1)

= n^(2_)/2

= n(n-1)/2

which is a really easy way to remember how to do sum(k, k=0..n-1).

The falling factorial representation of k^3 is:

k^3 = k^(3_) + 3k^(2_) + k^(1_)

so we can just use the discrete integration rule above to trivially
evaluate the sum.

Here's a relevant MathWorld entries:

http://mathworld.wolfram.com/FallingFactorial.html

which talks more about falling factorial powers.

Best of wishes!

From:	kiki
Subject:	Re: fastest way to derive sum(k^3, for k=1, ...n)?
Date:	Sun, 23 Jan 2005 13:01:05 -0800

"Daniel Yoo" wrote in message
news:csv1rl$20f8$1@agate.berkeley.edu...
> lucy wrote:
> : Hi all,
>
> : anybody recommends a fastest way to compute the
>
> : sum(k^3, k=1...n)?
>
> : I tried hard to remember this formula, but keep forgetting it...
>
> : Everytime it took me quite a while to derive it...
>
>
> Hello Lucy,
>
> I've been reading Concrete Mathematics, and the book gives a simple
> derivation for k^3 by using finite calculus on Page 51.
>
>
> If we define a falling factorial power k^(m_) as
>
> k^(m_) = k*(k-1)*(k-2)*...*(k-m+1),
>
> then we can do a finite "integration" of a factorial power like this:
>
> sum(k^(m_), k=0..n-1) = (1/m+1) * n^(m+1_)
>
> And this looks almost like the rule for integrating regular powers in
> regular calculus.
>
>
>
> For example, since k^1 = k^(1_), we have
>
> sum(k, k=0..n-1)
>
> = sum(k^(1_), k=0..n-1)
>
> = n^(2_)/2
>
> = n(n-1)/2
>
> which is a really easy way to remember how to do sum(k, k=0..n-1).
>
>
> The falling factorial representation of k^3 is:
>
> k^3 = k^(3_) + 3k^(2_) + k^(1_)
>
> so we can just use the discrete integration rule above to trivially
> evaluate the sum.
>
>
> Here's a relevant MathWorld entries:
>
> http://mathworld.wolfram.com/FallingFactorial.html
>
> which talks more about falling factorial powers.
>
>
> Best of wishes!

Aaha, this looks like an interesting idea... but is it the most fastest way
of deriving sums?

But are there any easier way to write out?

k^3 = k^(3_) + 3k^(2_) + k^(1_)
k^4, etc.?

And after doing "integration" with k^(3_), k^(2_), etc.

you need to convert them back to normal powers of k...

maybe this is hard/slower...