# Mathematical Induction

1. Sep 27, 2007

1. The problem statement, all variables and given/known data
Prove:
$$1^{4}+2^{4}+3^{4}+...+n^{4}=\frac{(n)(n+1)(2n+1)(3n^{2}+3n-1)}{30}$$

2. Relevant equations
Umm, Im not using any.

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

Last edited: Sep 27, 2007
2. Sep 27, 2007

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

3. Sep 27, 2007

### Dick

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

4. Sep 27, 2007

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

Last edited: Sep 27, 2007
5. Sep 27, 2007

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, im following Dick's advise, if I get stuck, I'll go with Bel's.

6. Sep 27, 2007

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

Last edited: Sep 27, 2007
7. Sep 27, 2007

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

8. Sep 27, 2007

$$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 cant 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)

Last edited: Sep 27, 2007
9. Sep 27, 2007

### Hurkyl

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

$$n^{k+1} - 1^{k+1} = \left( n^{k+1} - (n-1)^{k+1} \right) + \left( (n - 1)^{k+1} - (n-2)^{k+1} \right) + \cdots + \left( 2^{k+1} - 1^{k+1} \right)$$

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

10. Sep 27, 2007

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

11. Sep 27, 2007

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

Hmm, let me try and expand the whole thing.

one sec.

12. Sep 27, 2007

### dynamicsolo

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

13. Sep 27, 2007

### Hurkyl

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

14. Sep 27, 2007

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.. lemme do this again

Last edited: Sep 27, 2007
15. Sep 27, 2007

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

Last edited: Sep 27, 2007
16. Sep 27, 2007