Mathematica Mathematical Induction

  • Thread starter matadorqk
  • Start date
96
0
1. Homework Statement
Prove:
[tex]1^{4}+2^{4}+3^{4}+...+n^{4}=\frac{(n)(n+1)(2n+1)(3n^{2}+3n-1)}{30}[/tex]


2. Homework Equations
Umm, Im not using any.


3. The Attempt at a Solution
So my first step:
1) Check for n=1
[tex]1^{4}=\frac{1(1+1)(2(1)+1)(3(1)^{2}+3(1)-1)}{30}=\frac{(2)(3)(5)}{30}=1[/tex]

2)Now if n=k
[tex]P_{k}=1^{4}+2^{4}+3^{4}+...+k^{4}=\frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30}[/tex] is assumed true.
So, when n=k+1
So I would be expecting to get: [tex]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}[/tex]

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

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

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

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

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

Any hints on what to do now :S?
 
Last edited:

bel

154
0
Factor [tex]\frac{1}{30}[/tex] out of every term first, i.e., multply the [tex](k+1)^4[/tex] 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

Science Advisor
Homework Helper
26,258
618
Just expand P(k+1)-P(k). If you get (k+1)^4 then you win.
 

dynamicsolo

Homework Helper
1,648
4
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

[tex]\frac{(k)(2k+1)(3k^{2}+3k-1)}{30}+(k+1)^{4}[/tex]

to show that it is

[tex]\frac{(k+2)(2k+3)(3k^{2}+9k+6)}{30}[/tex] .

There was something comparable to do for the squares and cubes of integers, and it just gets worse with successively higher powers...
 
Last edited:
96
0
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

[tex]\frac{(k)(2k+1)(3k^{2}+3k-1)}{30}+(k+1)^{4}[/tex]

to show that it is

[tex]\frac{(k+2)(2k+3)(3k^{2}+9k+6)}{30}[/tex] .

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:
[tex]1^{5}+2^{5}+3^{5}+...+n^{5}=\frac{n^{2}(n+1)^{2}(2n^{2}+2n-1)}{12}[/tex]

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

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

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

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

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
[tex](6k^{4}+39k^{3}+93k^{2}+96k+36) - (6k^{4}+9k^{3}+k^{2}-k)[/tex]

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

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

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

Dick

Science Advisor
Homework Helper
26,258
618
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.
 
96
0
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.
[tex] 3(k+1)^{2}+3(k+1)-1=3k^{2}+9k+5[/tex]

(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 [tex]P_{k+1}-P_{k}=(k+1)^{4}[/tex] you cant change the [tex](k+1)^{4}[/tex] 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:

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

[tex]
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)
[/tex]

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

Science Advisor
Homework Helper
26,258
618
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.
 
96
0
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.
[tex]x^{4}+4x^{3}+6x^{2}+4x+1[/tex]

Hmm, let me try and expand the whole thing.

one sec.
 

dynamicsolo

Homework Helper
1,648
4
The proof for this, and higher powers, is another inductive argument. The key is

[tex]
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)
[/tex]

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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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.
 
96
0
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:
[tex]\frac{(k+1)(k+2)(2k+3)(3k^{2}+9k+6)}{30} - \frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30}[/tex]

Because I've tried multiple times, getting the same wrong answer....


Dam, stupid mistake
I did a dumb error, its actually:
[tex]\frac{(k+1)(k+2)(2k+3)(3k^{2}+9k+5)}{30} - \frac{(k)(k+1)(2k+1)(3k^{2}+3k-1)}{30}[/tex]

ARGHHH ****... sorry.. lemme do this again
 
Last edited:

Dick

Science Advisor
Homework Helper
26,258
618
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:
96
0
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, im 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.
 

Related Threads for: Mathematical Induction

Replies
3
Views
2K
Replies
5
Views
1K
Replies
4
Views
2K
Replies
7
Views
3K
Replies
0
Views
1K
Replies
4
Views
2K
Replies
15
Views
3K
Replies
2
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top