Math Induction: Prove 1^4+2^4+3^4+...+n^4=frac(n)(n+1)(2n+1)(3n^2+3n-1)/30

[matadorqk]

Homework Statement

Prove:
1^{4}+2^{4}+3^{4}+...+n^{4}=\frac{(n)(n+1)(2n+1)(3n^{2}+3n-1)}{30}

Homework Equations

Umm, I am not using any.

The Attempt at a Solution

So my first step:
1) Check for n=1
1^{4}=\frac{1(1+1)(2(1)+1)(3(1)^{2}+3(1)-1)}{30}=\frac{(2)(3)(5)}{30}=1

2)Now if n=k
P_{k}=1^{4}+2^{4}+3^{4}+...+k^{4}=\frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30} is assumed true.
So, when n=k+1
So I would be expecting to get: P_{k+1}:1^{4}+2^{4}+3^{4}+...+k^{4}+(k+1)^{4}=\frac{(k+1)(k+2)(2k+3)(3(k+1)^{2}+3k+3-1)}{30}

Since we assumed Pk to be true, and P_{k}+(k+1)^{4}=P_{k+1}
Lets prove it. The Left Hand Side (LHS) is the same, but the RHS is giving me trouble.

I am supposed to obtain
\frac{(k+1)(k+2)(2k+3)(3k^{2}+9k+6)}{30}

By doing something to: \frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30}+(k+1)^{4}

So my first try, i'll take out (k+1) as a common factor.

So: (k+1)(\frac{(k)(2k+1)(3k^{2}+3k-1)}{30}+(k+1)^{3})

Any hints on what to do now :S?

 

[bel]

Factor \frac{1}{30} out of every term first, i.e., multply the (k+1)^4 term by thirty and put it atop the fraction as well, then expand and factorise, using the remainder theorem, of course, since you know what factors to expect.

 

[Dick]

Just expand P(k+1)-P(k). If you get (k+1)^4 then you win.

 

[dynamicsolo]

Wow, I suspected there was a formula for the sum of fourth powers of integers, but I'd never seen it before.

Having gone through the induction proofs for the formulas up to third powers, I think I can say you're on the right track. You want to avoid multplying multinomials as long as you can manage. Unfortunately, I think you're at the point where you just have to bite the bullet and work out

\frac{(k)(2k+1)(3k^{2}+3k-1)}{30}+(k+1)^{4}

to show that it is

\frac{(k+2)(2k+3)(3k^{2}+9k+6)}{30} .

There was something comparable to do for the squares and cubes of integers, and it just gets worse with successively higher powers...

 

[matadorqk]

Wow, I suspected there was a formula for the sum of fourth powers of integers, but I'd never seen it before.

Having gone through the induction proofs for the formulas up to third powers, I think I can say you're on the right track. You want to avoid multplying multinomials as long as you can manage. Unfortunately, I think you're at the point where you just have to bite the bullet and work out

\frac{(k)(2k+1)(3k^{2}+3k-1)}{30}+(k+1)^{4}

to show that it is

\frac{(k+2)(2k+3)(3k^{2}+9k+6)}{30} .

There was something comparable to do for the squares and cubes of integers, and it just gets worse with successively higher powers...

Yeah, the problem after this is the same but with the sum of fifth powers. I also did the sum of 2nd and 3rd powers already, those weren't very hard. The sum of fifth powers is:
1^{5}+2^{5}+3^{5}+...+n^{5}=\frac{n^{2}(n+1)^{2}(2n^{2}+2n-1)}{12}

We have to proof that too, but for now, I am following Dick's advise, if I get stuck, I'll go with Bel's.

 

[matadorqk]

Ok Dick

Ok Dick, I have followed your advise, in search of (k+1)^4.. so:
My problem is now:
\frac{(k+1)(k+2)(2k+3)(3k^{2}+9k+6)}{30} - \frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30}
I have to get this to be equal to (k+1)^{4}

So I first factor out 1/30 and k+1 which seem to be common in both equations so:

(\frac{k+1}{30})((k+2)(2k+3)(3k^{2}+9k+6)-(k)(2k+1)(3k^{2}+3k-1))

I'm expanded but got a polynomial degree 3 which factored into imaginary, so I am going to expand again just incase I did any mistakes.

So when I expand I get
(6k^{4}+39k^{3}+93k^{2}+96k+36) - (6k^{4}+9k^{3}+k^{2}-k)

Which essentially comes down to:
30k^{3}+92k^{2}+97k+36

(We still have the (k+1)/30 on the outside)

wow.. I think a lightbulb just turned on, one second.

 

[Dick]

You're making a mistake. I get that 3(k+1)^2+3(k+1)-1=3k^2+9k+5. You got something else. I actually did do this and it does work. I'm not guessing.

 

[matadorqk]

You're making a mistake. I get that 3(k+1)^2+3(k+1)-1=3k^2+9k+5. You got something else. I actually did do this and it does work. I'm not guessing.

3(k+1)^{2}+3(k+1)-1=3k^{2}+9k+5

(Looks better)

Hmm, let me try again, am I right up until taking out the 1/30 and (k+1) or did you expand the (k+1) aswell?

Wow.. where did you get the equal sign from?

I thought in Mathematical induction (according to my teacher)
If were solving from P_{k+1}-P_{k}=(k+1)^{4} you can't change the (k+1)^{4} because that's what we want to get, or in her words, what were "inducing", if we change the other one, we'd be "deducing" the right side (or something like that hehe)

 

[Hurkyl]

Wow, I suspected there was a formula for the sum of fourth powers of integers, but I'd never seen it before.

The proof for this, and higher powers, is another inductive argument. The key is

<br /> n^{k+1} - 1^{k+1}<br /> = \left( n^{k+1} - (n-1)^{k+1} \right)<br /> + \left( (n - 1)^{k+1} - (n-2)^{k+1} \right)<br /> + \cdots + \left( 2^{k+1} - 1^{k+1} \right)<br />

which can be reduced to sums of k-th powers, plus sums of k-1-th powers, plus sums of k-2-th powers, plus ...

 

[Dick]

I expanded the whole thing (1/30)'s and all, and I got x^4+4x^3+6x^2+4x+1. Which equals (x+1)^4.

 

[matadorqk]

I expanded the whole thing (1/30)'s and all, and I got x^4+4x^3+6x^2+4x+1. Which equals (x+1)^4.

x^{4}+4x^{3}+6x^{2}+4x+1

Hmm, let me try and expand the whole thing.

one sec.

 

[dynamicsolo]

The proof for this, and higher powers, is another inductive argument. The key is

<br /> n^{k+1} - 1^{k+1}<br /> = \left( n^{k+1} - (n-1)^{k+1} \right)<br /> + \left( (n - 1)^{k+1} - (n-2)^{k+1} \right)<br /> + \cdots + \left( 2^{k+1} - 1^{k+1} \right)<br />

which can be reduced to sums of k-th powers, plus sums of k-1-th powers, plus sums of k-2-th powers, plus ...

Thanks! I've never actually seen these formulas derived (other than the familiar sums of integers result). Must be loads of fun to untangle...

 

[Hurkyl]

Must be loads of fun to untangle...

Once you know there is a formula, you can use linear algebra to figure it out. You can prove that the closed form for the sum of k-th powers is a polynomial of degree k+1. So, you just need to directly compute k+2 values, and you have a linear system of equations for the k+2 coefficients of your polynomial.

 

[matadorqk]

I expanded the whole thing (1/30)'s and all, and I got x^4+4x^3+6x^2+4x+1. Which equals (x+1)^4.

Are you expanding:
\frac{(k+1)(k+2)(2k+3)(3k^{2}+9k+6)}{30} - \frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30}

Because I've tried multiple times, getting the same wrong answer...Dam, stupid mistake
I did a dumb error, its actually:
\frac{(k+1)(k+2)(2k+3)(3k^{2}+9k+5)}{30} - \frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30}

ARGHHH ****... sorry.. let me do this again

 

[Dick]

I thought we agreed it should be 3k^2+9k+5? How did the 6 get back in there? You are just making mistakes, which is doesn't mean you have any conceptual problems. I think you are ok on concepts. Do you know what I do confronted with an expansion like that? I use a machine. Because I can't necessarily add 3+3-1 and get 5 reliably either. And I don't think it's important that you can.

 

[matadorqk]

I thought we agreed it should be 3k^2+9k+5? How did the 6 get back in there? You are just making mistakes, which is doesn't mean you have any conceptual problems. I think you are ok on concepts. Do you know what I do confronted with an expansion like that? I use a machine. Because I can't necessarily add 3+3-1 and get 5 reliably either. And I don't think it's important that you can.

Thanks, I finally solved it correctly :). Stay tuned, I am going to try the sum to degree 5 in a couple minutes, ill post if i get stuck, which hopefully I wont.. but meh, who knows.