Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical Induction

  1. Sep 27, 2007 #1
    1. The problem statement, all variables and given/known data

    2. Relevant equations
    Umm, Im not using any.

    3. The attempt at a solution
    So my first step:
    1) Check for n=1

    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

    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: Sep 27, 2007
  2. jcsd
  3. Sep 27, 2007 #2


    User Avatar

    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.
  4. Sep 27, 2007 #3


    User Avatar
    Science Advisor
    Homework Helper

    Just expand P(k+1)-P(k). If you get (k+1)^4 then you win.
  5. Sep 27, 2007 #4


    User Avatar
    Homework Helper

    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


    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: Sep 27, 2007
  6. Sep 27, 2007 #5
    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:

    We have to proof that too, but for now, im following Dick's advise, if I get stuck, I'll go with Bel's.
  7. Sep 27, 2007 #6
    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:


    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:

    (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
  8. Sep 27, 2007 #7


    User Avatar
    Science Advisor
    Homework Helper

    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.
  9. Sep 27, 2007 #8
    [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: Sep 27, 2007
  10. Sep 27, 2007 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 ...
  11. Sep 27, 2007 #10


    User Avatar
    Science Advisor
    Homework Helper

    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.
  12. Sep 27, 2007 #11

    Hmm, let me try and expand the whole thing.

    one sec.
  13. Sep 27, 2007 #12


    User Avatar
    Homework Helper

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


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  15. Sep 27, 2007 #14
    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: Sep 27, 2007
  16. Sep 27, 2007 #15


    User Avatar
    Science Advisor
    Homework Helper

    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
  17. Sep 27, 2007 #16
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook