1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction Proofs

  1. May 25, 2006 #1
    Prove that [tex] 1^{3} + 2^{3} + 3^{3} + ... + n^{3} = (1 + 2 + 3 + ... + n)^{2} [/tex]. So for [tex] n =1 [/tex] [tex] 1^{3} = 1^{2} [/tex]. For [tex] n = k [/tex], [tex] 1^{3} + 2^{3} + 3^{3} + ...+ k^{3} = (1+2+3+...+ k )^{2} [/tex]. For [tex] n = k+1 [/tex],[tex] 1^{3} + 2^{3} + 3^{3} +...+ k^{3} + (k+1)^{3} = (1+2+3+..+ (k+1))^{2} [/tex]. So do I then do this:

    [tex] 1^{3} + 2^{3} + 3^{3} + ... + k^{3} + (k+1)^{3} = (1+2+3+...+ k)^{2} + (k+1)^{3} [/tex] to show that it is equal to [tex] n = k+1 [/tex]?

    Thanks
     
    Last edited: May 25, 2006
  2. jcsd
  3. May 25, 2006 #2

    VietDao29

    User Avatar
    Homework Helper

    You must use your induction hypothesis, i.e:
    [tex]1 ^ 3 + 2 ^ 3 + ... + k ^ 3 = (1 + 2 + ... + k) ^ 2[/tex] (1)
    To prove that:
    [tex]1 ^ 3 + 2 ^ 3 + ... + k ^ 3 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2[/tex]. (2)
    i.e if the equation is true for n = k, it also holds when n = k + 1.
    ------------------
    So let's go from what we have:
    [tex]1 ^ 3 + 2 ^ 3 + ... + k ^ 3 = (1 + 2 + ... + k) ^ 2[/tex]
    the LHS of the equation (2) has an extra term (k + 1)3. So let's add (k + 1)3 to both sides of the above equation:
    [tex]\Leftrightarrow 1 ^ 3 + 2 ^ 3 + ... + k ^ 3 + (k + 1) ^ 3 = (1 + 2 + ... + k) ^ 2 + (k + 1) ^ 3[/tex] (3)
    You have to prove that
    [tex]1 ^ 3 + 2 ^ 3 + ... + k ^ 3 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2[/tex], right?
    Or in other words, you have to prove:
    [tex](1 + 2 + ... + k) ^ 2 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2[/tex]
    Can you go from here? :)
     
    Last edited: May 25, 2006
  4. May 25, 2006 #3
    yes. thank you
     
  5. May 26, 2006 #4

    Curious3141

    User Avatar
    Homework Helper

    Hint, an easy way to do it is to use [tex]1 + 2 + ... + k = \frac{1}{2}k(k+1)[/tex]
     
  6. May 26, 2006 #5
    Indeed , and [tex]1^3 + 2^3 + ... + k^3 = (\frac{1}{2}k(k+1))^2[/tex]

    But that is what the question is asking us to prove, by induction.
    So the direct formulae are not applicable (only the assumed tautology can be used) and VietDao's method is the probably the only straightforward method to do this problem .

    Arun
     
  7. May 26, 2006 #6
    How can you show that [tex] (-1)^{k+1} (1+2+...+k)k^{2} + (-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+ k + (k+1)) [/tex]?
     
  8. May 26, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You can sum 1+2+3+...+r so why don't you? You can also divide everything by (-1)^{k+1} to remove any doubts about signs. Of course it looks false: the LHS is (the same as) a poly in k^3 and the RHS in k^2
     
    Last edited: May 26, 2006
  9. May 26, 2006 #8
    The original problem was: Prove that [tex] 1-4+9-16 + ... + (-1)^{n+1} n^{2} = (-1)^{n+1} (1+2+... + n) [/tex]. For [tex] n =1 [/tex] [tex] 1 =1 [/tex]. For [tex] n = k [/tex], [tex] 1-4+9-16+...+(-1)^{k+1} k^{2} = (-1)^{k+1} ( 1+2+...+n) [/tex]. For [tex] n = k+1 [/tex], [tex] 1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+k+(k+1)) [/tex]. So I want to show that: [tex] 1-4+9-16+...+ (-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2} = (-1)^{k+1}(1+2+...+k)+(-1)^{k+2}(k+1)^{2} [/tex] or [tex] (-1)^{k+1}(1+2+...+k)k^{2}+(-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+ k + (k+1)) [/tex]. When I divide through I get: [tex] (1+2+...+k)k^{2} - (k+1)^{2} = - (1+2+...+k+(k+1)) [/tex] or [tex] \frac{1}{2}k(k+1)k^{2} - (k+1)^{2} = -(\frac{1}{2}(k+1)(k+2)) [/tex]

    Isn't this correct?
     
    Last edited: May 26, 2006
  10. May 26, 2006 #9

    Curious3141

    User Avatar
    Homework Helper

    The question is asking one to prove [tex](1 + 2 + ... + k)^2 = 1^3 + 2^3 + ... + k^3[/tex] not that [tex]1 + 2 + ... + k = \frac{1}{2}k(k+1)[/tex]. It's a pretty safe bet that the latter result can be assumed, if not, proof of that by AP sum or induction is trivial.

    And, in fact, VietDao hadn't given an explicit method to prove what needs to be proved viz. [tex](1 + 2 + ... + k) ^ 2 + (k + 1) ^ 3 = (1 + 2 + ... + k + (k + 1)) ^ 2[/tex] He merely stated it at something that needs to be proved, how is up to the individual. I'm merely suggesting a valid way to go about proving that proposition.
     
    Last edited: May 26, 2006
  11. May 26, 2006 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Something is wrong in your algebra, and general presentation.

    You *cannot* write the thing you wish to prove as if it is true:

    [tex] 1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = (-1)^{k+2}(1+2+...+k+(k+1)) [/tex]

    should under no circumstances be the first thing you write down.

    I have no idea how you came to the last line from the one immediately preceding it.

    Start with:
    [tex] 1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = \ldots[/tex]


    and put in something that the inductive hypothesis allows you to do (which is the only valid thing you can do, by the way), namely sum the first k terms using the formula you are assuming and then add the last term on, now rearrange and the answer drops out.
     
  12. May 26, 2006 #11
    So [tex] 1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = 1-4+9-16+...+(-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2}[/tex]
     
  13. May 26, 2006 #12

    Curious3141

    User Avatar
    Homework Helper

    Right. Now apply the inductive hypothesis.
     
  14. May 26, 2006 #13
    [tex] 1-4+9-16 + ...+ (-1)^{k+2}(k+1)^{2} = 1-4+9-16+...+(-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2}= 1-4+9-16+...+(-1)^{k+1} k^{2} = (-1)^{k+1}( 1+2+...+n)+(-1)^{k+2}(k+1)^{2}[/tex]
     
    Last edited: May 26, 2006
  15. May 26, 2006 #14

    Curious3141

    User Avatar
    Homework Helper

    Don't mix up the n with the k (n has no place in the expressions).

    There's still something wrong with the algebra. You seem to have dropped a term here :


    [tex]1-4+9-16+...+(-1)^{k+1}k^{2} + (-1)^{k+2}(k+1)^{2}= 1-4+9-16+...+(-1)^{k+1} k^{2}[/tex]

    Anyway, how would you proceed?
     
  16. May 26, 2006 #15
    got it. thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Induction Proofs
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...