Summing power series

By Michael Doré (P904) on Saturday, July 10, 1999 - 02:42 pm :

Is it possible to evaluate:

n
å
r=1

r^k

in general (without knowing what k is)?
This is how far I've got:

1) The answer is always a polynomial in n of degree k+1. This is easy enough to prove.

2) Suppose that:

n
å
r=1

r^k = a₀ + a₁ n + a₂ n² + ¼+ a_k+1 n^k+1

then experimentally I have found:

a_t = k!/t! C(k-t)

where

c(-1) = -1
c(0) = 1/2
c(1) = 1/12
c(2) = 0
c(3) = -1/720
c(4) = 0
c(5) = 1/30240
c(6) = 0
c(7) = -1/1209600
c(8) = 0
c(9) = 1/47900160
c(10) = 0
c(11)= -691/13076743368000
c(12) = 0
c(13) = 1/74724249600
c(14) = 0
c(15) = -3617/10670622842880000
c(16) = 0

The notation is a bit unclear so I'll run through a couple of examples to clarify the situation.

Suppose we want to predict the leading coefficient of the sum of r^k where r varies from 1 to n, i.e. the coefficient of n^k+1 in the answer:

a_t = k!/t! C(k-t)

So:

a_k+1 = k!/(k+1)! C(k-k-1)
= 1/(k+1) C(-1) = 1/(k+1)

So for instance if we sum r² , k=2 and the leading coefficient is 1/(k+1)=1/3. This can be verified as we know the answer is 1/6n(n+1)(2n+1) so the coefficient of n³ is indeed 1/3.

For summing r³ , k=3 so we predict the leading coefficient is 1/4. This agrees with the standard result 1/4n² (n+1)² .

If we want to predict the second highest coefficient:

t=k

a_t = k!/t! C(k-t)

so

a_k = k!/k! C(k-k) = C(0) = 1/2.

In other words, if you sum the first n r^k s, then the coefficient of the second highest power is always 1/2.

e.g. 1/2n(n+1) has coefficient of n as 1/2.
1/6n(n+1)(2n+1) has coefficient of n² as 1/2.
1/4n² (n+1)² has coefficient of n³ as 1/2.

As for the coefficient of n (at the other end of the scale):

t=1
a_t = k!/t! C(k-t)

so

a₁ = k! C(k-1)

So the coefficient of n in the sum of r² should be 2! C(1) = 2 * 1/12 = 1/6 and it is as the result 1/6n(n+1)(2n+1) suggests.

In general c(p) = 0 if p is even and p> 0. The odd terms alternate between being positive and negative and decrease in magnitude each time. Apart from this I can't see any patterns.

If I could find an expression for c(x) (even a recurrence relationship) then it should be possible to prove the patterns I have found by induction.

3) One other related result that I stumbled on (and managed to prove by induction) is that:

n
å
r=1

r(r+1)¼(r+k-1)=1/(k+1)[n(n+1)¼(n+k)]

If it were possible to expand out r(r+1)(r+2)...(r+k) in powers of r then we could possibly use this result to find the sum of simple polynomials and thus solve the problem.

None of these ideas appear to be adequately covered in my A-level textbooks so I would be grateful for any help you could offer.

Thank-you,

Michael

By Chris Jefferson (Caj30) on Tuesday, July 13, 1999 - 01:23 pm :

Getting a precise answer out will be quite difficult, but here's some thoughts anyway.

Can you explicitly get the expansion for, say
n
å
r=1
r

and
n
å
r=1
r²

without knowing what they are before hand?

The way I would do it at least is as follows:

Assume answer is in form a₀+a₁ n¼

and then we know that a₀+a₁ n¼a_k+1n^k+1+(n+1)^k+1=a₀+a₁(n+1) ¼a_k+1(n+1)^k+1

Does that make sense? Here is an example for
n
å
r=1
r

We know answer will be like a+b n +c n²

we also know that a+b n+c n² + n+1=a+b(n+1)+c(n+1)²

So checking powers of n:

a+1=a+b+c

b+1=b+2c

c=c

So, c=1/2, b=1/2 and then by explicitly checking n=1, we get a=0 giving
n
å
r=1
r=(1/2)×n(n+1)

, as we all knew.

This could be expanded upwards, but I'm not sure how simple it would be to do, I'm going to try tonight when I get home from work, I think.

Sorry if I'm telling you what you already knew!

Anyway, see what you get and get back to me, Chris

By Michael Doré (P904) on Wednesday, July 14, 1999 - 04:15 pm :

Dear Chris,

Thank you for your reply.

I used a similar method to you. I wrote out the polynomial with its coefficients in the same way as you, but then put in individual values of n, solved the resulting simultaneous equations to get the answer. I then proved this for all n by induction.

However, I still have not found a complete pattern. (The patterns I found are summarized in my previous message -for example the coefficient of n^k in the answer is always 1/2). Using your equations (in a slightly different form to simplify the calculations), however, we can get:

a₁ n + a₂ n² + ...+ a_k+1 n^k+1 = n^k + a₁ (n-1) + a₂ (n-1)² + ...+ a_k+1 (n-1)^k+1

and:

a₁ (n-[n-1]) + a₂ (n² -[n-1]² ) + ... + a_k+1 (n^k+1 - (n-1)^k+1 ) = n^k

(a_i is the coefficient of nⁱ in the expression which is the sum of r^k where r varies from 1 to n)

Using the binomial expansion we can show:

a₁ - a₂ + a₃ + ... - (-1)^k+1 a_k+1 = 0 (equating constant terms)

2a₂ - 3a₃ + ... + (k+1)(-1)^k+1 a_k+1 = 0 (equating 1st degree terms)

etc.

In general by equating n^r coefficients we get

k+1
å
i=r+1

ⁱ C_r a_i(-1)ⁱ=0

(*)

In case this hasn't come out clearly: that says that the sum, when i varies from r + 1 to k + 1, of i choose r multiplied by a_i , multiplied by -1 to the i is always 0. This holds for integral r where 0 < = r < = k-1. (Outside this range the coefficient of n^r may not be zero).

In addition we can equate the coefficient of n^k and we get:

1 = (1+k)a_k+1

So a_k+1 = 1/(k+1)

Now let r = k-1. Using my formula (*):

k+1
å
i=k

ⁱ C_k-1 a_i (-1)ⁱ = 0

ka_k =1/2k(k+1)a_k+1

Now a_k+1 = 1/(k+1) so a_k = 1/2k/k = 1/2 as I had already found.

To generalise this if we now write a_i as k! / i! C(k-i) (where c(x) is a function that I outlined earlier) using (*) we get:

k+1
å
i=r+1

(-1)ⁱ C(k-i)/(i-r)!=0

for 0 £ r £ k-1
(all other factors in the equation are constant so cancel)

For instance:

C(0)/1! - C(-1)/2! = 0 (where r = k-1)
C(1)/1! - C(0)/2! + C(-1)/3! = 0 (where r = k-2)
C(2)/1! - C(1)/2! + C(0)/3! - C(-1)/4! = 0 (where r = k-3)
C(3)/1! - C(2)/2! + C(1)/3! - C(0)/4! + C(-1)/5! = 0 (where r = k-4)

etc.

So we have a recurrence relationship for C(x), and we could use it to check my experimental table in my first message. We know that C(-1) = 1 as:

a_i = k! / i! C(k-i)
a_k+1 = k! / (k+1)! C(k-(k+1))

So C(-1) = a_k+1 (k+1) = 1 using our result for a^k+1 .

That also proves that c(x) is only dependant on x as I found experimentally earlier on. (c(-1) is a constant so c(x) must be constant as it can be found from the recurrence relationship above).

I think I'm going to need help in solving the recurrence relationship though. If this is possible then we've finished the problem as we can predict all the coefficients in the sum expression. I've tried a few things but have not yet got anything to work.

Many thanks for your time,

Michael

By Alex Barnard (Agb21) on Wednesday, July 21, 1999 - 10:16 am :

Hello there...

Just some quick stuff about the numbers you've found called C(n). The following sequence is a very well known one:

1 , -1/2 , 1/6 , 0 , -1/30 , 0 , -1/42 ...

They are called the Bernoulli numbers . You'll see that your C(n) are these divided by n!. I don't know much about their properties but they are pretty irregular. One way to find them is to find the Taylor series of x / (e^x - 1). Try it and you'll see.

AlexB.

by Michael Doré (P904) on Wednesday, July 21, 1999 - 08:26 pm :

Dear Chris and AlexB,

Thank you for your replies. After looking at your list of Bernoulli numbers I think the connection between these and C(x) is:

B(x) = (-1)^x C(x-1) x!

Where B(x) are the Bernoulli numbers. I've assumed that by convention the zeroth Bernoulli number is 1, i.e. that the series B(x) starts at x=0.

(By the way, there is an error in my original message. I wrote C(-1) = -1 when in fact C(-1) = 1.)

Now the formula a_i = k! / i! C(k - i) predicts the coefficient of nⁱ in the sum of r^k (where r varies from 1 to n.) By replacing C(k -i) with a Bernoulli number we can get:

a_i = (-1)^{k - i + 1} B(k - i + 1) k! / [i! (k - i + 1)!]

So at least now we can predict any coefficient in the sum of r^k in terms of Bernoulli numbers, which you say are relatively well known.

To check:

let i = k + 1

a_k+1 = (-1)⁰ B(0) k!/[(k+1)!0!] = 1/(k+1)

as we knew. (In the sum of r^k the leading coefficient i.e. that of n^k+1 is 1/(k+1).)

We can also derive a recurrence relationship for the Bernoulli numbers. In my second message I gave:

k+1
å
i=r+1

(-1)ⁱ C(k-i)/(i-r)!=0

(for 0 £ r £ k-1)

Replacing C(k-i) with Bernoulli numbers:

k+1
å
i=r+1
B(k-i+1)/[(i-r)!(k-i+1)!]=0

Now make the substitutions a=k-i+1 and b=k-r+1:

a=b-1
å
a=0
B(a)/[(b-a)! a!]=0

for b ³ 2.

So:

B(1)/[1!1!] + B(0)/[0!2!] = 0
B(2)/[2!1!] + B(1)/[1!2!] + B(0)/[0!3!] = 0
B(3)/[3!1!] + B(2)/[2!2!] + B(1)/[1!3!] + B(0)/[0!4!] = 0
B(4)/[4!1!] + B(3)/[3!2!] + B(2)/[2!3!] + B(1)/[1!4!] + B(0)/[0!5!] = 0

etc

Is this a standard result?

You also suggested using the Taylor expansion for x/(e^x -1). My knowledge of Taylor expansions is limited as I have not yet started the Further Maths A-Level. However I know a little about them from a book I read, so here goes:

The formula is

f(a + x) = f(a) + x f'(a) + x² f''(a) /2! + ...

and

let f(x) = x/(e^x -1)

So if we want to find f(x), then a = 0, and it becomes the Maclurin expansion.

But f(0) = 0/(1-1) = undef. So a can't be 0, as we have an undefined constant term. I can't think of a suitable value of a offhand. If the successive coefficients are going to be Bernoulli numbers then a must be 0 as x = e^x -1 (giving a coefficient of 1 normally) only when x = 0. I'm afraid I am going to need a bit of guidance with the Taylor expansion!

Thank you again,

Michael

By Alex Barnard (Agb21) on Thursday, July 22, 1999 - 11:18 am :

Okay; here is how to work out the Taylor series... By the way there was a slight error in my definition of the Bernoulli numbers, they should be the coefficient of xⁿ /n! in the Taylor expansion not the coefficient of xⁿ . But that doesn't really matter.

The Taylor series of e^x - 1 is:

x + x² /2 + x³ /3! + ... [Hopefully you'll know this - otherwise look it up/work it out/believe me]

So x / (e^x - 1) is:

1 / (1 + x/2! + x² /3! + ... ) [Okay??]

Now the Taylor series of 1/(1+y) is:

1 - y + y² - y³ + y⁴ ... [Again look it up if you don't know]

Finally use this series with y = x/2! + x² /3! ... to get the Bernoulli numbers.

I hope that made sense... Let me know if you don't follow any of this.

AlexB

By Michael Doré (P904) on Friday, July 23, 1999 - 07:59 pm :

Thanks, that was very helpful. I did think of doing it exactly that way but for some reason was worried that 1 -y + y² -y³ + ...could not be expanded when y = x/2! + x² /3! + ...In fact it works out fine. (Of course it would have been impossible to collect the terms if y had been 1 + x/2! + x² /3! + ...but this is not the case.)

I think I have also found a way to prove that the coefficients of xⁿ /n! in the expansion of x/(e^x - 1) are the Bernoulli numbers.

I will define Bernoulli numbers by the recurrence relationship I pointed out in my last message:

a=b-1
å
a=0

B(a)/[(b-a)! a!]=0

and B(0) = 1.

You showed that x/(e^x - 1) can be written as an infinite power series. (It converges for e^x < 2x + 1 which means x =/= 0 and x< 1.57.)

So let:

x/(e^x -1) = a(0) + a(1) x + a(2) /2! x² + a(3) /3! x³ + ...(*)

in other words let the coefficient of xⁿ be a(n)/n! Now I just need to show that a(n) = B(n) for all n. (B(n) are the Bernoulli numbers.)

Rearranging (*):

x = [a(0) + a(1) x + a(2) /2! x² + a(3) /3! x³ + ...][e^x - 1]

x = [a(0) + a(1) x + a(2) /2! x² + a(3) /3! x³ + ...][x + x² /2! + x³ /3! + ...]

or

¥
å
r=0

x^r a(r)/r!

¥
å
r=1

x^r/r!

Equating powers of x:

a(0) = 1

Equating powers of xⁿ where n > = 2:

n-1
å
r=0

a(r)/[(n-r)! r!]=0

which is the same recurrence relationship as for B(x). Also a(0) = B(0) = 1. Therefore the coefficients are the Bernoulli numbers divided by n!. Of course this is a useful result for summing powers of integers as the Bernoulli numbers can be used to predict the coefficients of nⁱ in the sum of r^k .

Next I will try to prove that B(2x + 1) = 0 where x is a positive integer. If I make any progress then I'll write back.

Thank you,

Michael

By Alex Barnard (Agb21) on Monday, July 26, 1999 - 03:31 pm :

I have a one line proof that B(2x+1)=0... but I won't spoil your fun by posting it yet. Let me know when you've worked out a proof of your own or given up and I'll post it then.

AlexB.

By Michael Doré (P904) on Monday, July 26, 1999 - 07:02 pm :

Well, I've certainly thought up a proof but it is not one line I'm afraid.

We know

x/(e^x -1) = B(0) + B(1)x + B(2)x² /2! + B(3)x³ /3! + ...

will converge for x< 1.57 and x =/= 0. So for any x in the range -1.57 x < 1.57 (excluding x=0) the above formula will work for x and -x. Therefore:

x/(e^x -1) = B(0) + B(1)x + B(2)x² /2! + B(3)x³ /3! + ...

-x/(e^-x -1) = B(0) - B(1)x + B(2)x² /2! - B(3)x³ /3! + ...

for the above domain. Subtract the 2nd equation from the first:

-x = 2B(1)x + 2B(3)x³ /3! + 2B(5)x⁵ /5! + ...

(The left hand side simplifies to -x as e^x -1 =/= 0 as x =/= 0.)

Now B(1)=-1/2 so the equation becomes:

0 = B(3)x³ /3! + B(5)x⁵ /5! + B(7)x⁷ /7! + ...

for -1.57 x < 1.57, x =/= 0. Cancelling the x³ :

0 = B(3)/3! + B(5)x² /5! + B(7)x⁴ /7! + ...

Now by successively differentiating both sides and letting x get very close to 0 it is possible to show B(3)=B(5)=B(7)=...=0

(All the terms with x^r in them disappear as the terms decrease faster than a geometric progression, at any -1 x < 1. This is because the Bernoulli numbers always decrease in magnitude as my recurrence relationship earlier showed, and the factorials on the denominator get larger.)

Am I on the right track?

Michael

By Michael Doré (P904) on Monday, July 26, 1999 - 08:11 pm :

In my last message, the Taylor expansion should converge for x =/= 0 and (approximately) x< 1.26 not x< 1.57. The important thing is that in both cases x< 1 is not excluded.

Sorry about that!

Michael

By Alex Barnard (Agb21) on Wednesday, July 28, 1999 - 12:35 pm :

It looks okay. The quick proof is as follows. Differentiate x/(e^x -1) twice and the result you get is an even function [ie. f(-x)=f(x)]. If you know that the power series of an even function has only even powers of x then you've finished.

AlexB.

By Michael Doré (P904) on Tuesday, August 3, 1999 - 01:56 pm :

Actually they are really quite similar methods. I felt sure that it would be necessary to use the Taylor expansion, rather than proving B(2x + 1)=0 by induction with the recurrence relationship I found earlier; this does not appear to be possible.

The consequence for the sum of powers of integers is that while the coefficient of the 2nd highest power in the answer is 1/2, the coefficients of the 4th, 6th, 8th ... etc highest powers are all zero, which is an interesting result in itself. It is the coeffcients of the 3th, 5th, 7th ...etc highest coefficients whose prediction requires use of the Bernoulli sequence, (or a separate calculation).

Thanking you for your help,

Michael

By The Editor :

The following posts were originally posted in a separate thread, in response to the above discussion.

By Alex Barnard (Agb21) on Thursday, July 22, 1999 - 01:22 pm :

When I get time over the next few days I'll put up several messages about how to work out the sums like:

1^r + 2^r + 3^r + ... + n^r

Most of the stuff that I'll do is fairly complex and if you don't understand but would like to then add a message whit the bits you want in more detail.

Okay, set f(x) = 1 + e^x + e^2x + e^3x + ... + e^nx .

What happens if we differentiate this?? Well we get:

f'(x) = e^x + 2e^2x + 3e^3x + etc...
f''(x) = e^x + 2² e^2x + 3² e^3x + etc...
f'''(x) = e^x + 2³ e^2x + 3³ e^3x + etc...

Now if we put x=0 in these we get:

1 + 2 + 3 + ... + n in the first case
1² + 2² + 3² + ... + n² in the second case
1³ + 2³ + 3³ + ... + n³ in the third case

So now it should be clearer why I picked f(x) to be what it was. Somehow its derivatives are the sums we are looking for. In fact if we differentiate f(x) r times and then put x=0 we get the sum of the first n r'th powers.

Now if you know how to sum up geometric series then you should see that:

f(x) = (e^(n+1)x - 1) / (e^x - 1)

So:

f(x) = [e^(n+1)x / (e^x - 1)] - [e^0x / (e^x - 1)]

So it looks like we should think about the function:

G(x) = e^mx / (e^x - 1)

in order to better understand f(x). However for reasons I'll explain later I'll actually look at the function:

g(x) = x / (e^x - 1)

The function g(x) has a Taylor expansion which goes like:

g(x) = b(0) + b(1)x + b(2)x² /2! + b(3)x³ /3! + ...

And the numbers b(i) are called the Bernoulli numbers .

To be continued...

By Alex Barnard (Agb21) on Friday, July 30, 1999 - 02:10 pm :

Ignoring the factor of x in the definition of g(x) for now we see that we want to calculate the derivatives of g(x) x e^mx . We can do this by using something which looks like the binomial theorem...

What do the derivatives of f(x) x g(x) look like?

[0th] f*g
[1st] f'*g + f*g'
[2nd] f''*g + 2f'*g' + f*g''
[3rd] f'''*g + 3f''*g' + 3f'*g'' + f*g'''

So when we differentiate g(x) x e^mx r times we get terms like:

(r choose k) x [k'th deriv of g] x [m^r-k e^mx ]

Now the k'th derivative of g at x=0 is b(k), so these terms are like:

(r choose k) x b(k) x m^r-k .

When m=0 the only term that is left is b(r).

So the r'th derivative at x=0 of x(e^mx -1) / (e^x - 1) is:

Sum[(r choose k) x b(k) x m^r-k ,k=0...r] - b(r)

So finally we have to work out how to calculate the derivatives of (e^mx -1)/(e^x - 1) from the ones we have just calculated. Well we use the binomial like theorem to write down what the r'th derivative of x x(e^mx -1)/(e^x - 1) is. When x=0 only one term is left:

r x [(r-1)'st derivative of (e^mx -1)/(e^x - 1)]

Hence the r'th derivative we want is:

(1/(r+1)) x(Sum[((r+1) choose k) x b(k) x m^r+1-k ,k=0...(r+1)] - b(r+1))

And this is therefore a formula for the sum of the first (m-1) r'th powers of the integers.

Sorry this is so complicated, but there isn't a particularly easy way to do it. The messages here are mainly to explain a different way of doing things.

AlexB