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

Proof by Induction question

  1. Jun 12, 2006 #1
    I'm new to Proof by Induction. I've gotten a few so far, but this one has eluded me for some reason.

    " Prove that [tex] 1^3 + 2^3 + 3^3.....k^3 = (1 +2 + 3....k)^2 [/tex]"

    I checked for n =1 and , yes it does work. So, I assumed A(k) is true, so I'll try for A(k+1)

    I started assuming A(k) and added [tex] (k+1)^3 [/tex] to both sides (as this would be the next term

    [tex] 1^3 + 2^3 .... k^3 + (k+1)^3 = (1 + 2.... k)^2 + (k+1)^3 = (1 + 2....k + (k + 1) )^2 [/tex]

    So, I must now show that

    [tex](1 +2 + .... k + (k+1))^2 = (1 + 2 + ....k)^2 + (k+1)^3 [/tex]
    Does this look right so far?

    Unfortunately, I haven't thought of a way to demonstrate this yet. If I prove that statement true, I prove the original assertion. Should I try proving that statement with induction or something...?
  2. jcsd
  3. Jun 12, 2006 #2


    User Avatar
    Homework Helper

    There was a thread about this not too long ago, but I can't find it. I think you'll have to use the explicit expression for the sum 1+2+...+k. Do you know what this is? If not, you can find it by thinking about the following figures:




    Last edited: Jun 12, 2006
  4. Jun 12, 2006 #3
    Oh! Are you suggesting express
    [tex] 1 + 2 + 3 .... k = k(k+1)/2 [/tex]. I'll prove that at the end, but I'll assume that fact is true and use it. (I proved that one earlier, but I'll post a proof of that at the end to make sure it is right also.) . I didn't even think to use that! Well, using that
    [tex](1 +2 + .... k + (k+1))^2 = (1 + 2 + ....k)^2 + (k+1)^3 [/tex]

    goes down to
    [tex] ((k+1)(k+2) /2 )^2 = ((k+1)k/2)^2 + (k+1)^3 [/tex]

    Now, expanding these lovely algebraic nightmares leads me to

    [tex] (1/4) (k^4 + 6k^3 + 13k^2 + 8k + 4) = (1/4) (k^4 + 2k^3 + k^2) + (k+1)^3 [/tex]

    Multiplying through by four, and then subtracting like terms leads me to

    [tex] 4k^3 + 12k^2 + 12k+4 = 4(k+1)^3 [/tex]
    Arithmetic leads me to
    [tex] k^3 +3k^2 + 3k +1 = (k+1)^3 [/tex]
    Which is true! Thank you very much!

    Now, I should prove the statement I used above [tex]\sum_1^k i = k(k+1)/2 [/tex]

    So, I start about by Checking A(1) (True). I assume A(k) is true. And go to show k+1 is true. Adding k+1 to both sides leads to

    [tex] 1 +2 + 3 ... k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2) /2 [/tex]
    Working with the middle and right hand side, I can show those are equal and I will prove it.
    So, Expanding leads to

    [tex](1/2) (k^2 + k) + (k+1) = (k^2 +3k + 2) /2

    k^2 + k + 2(k+1) = k^2 + 3k + 2
    k^2 + 3k + 2 = k^2 + 3k + 2


    Thank you very much for the hint! That made it make complete sense. I didn't think about using an idea I proved earlier. Does it look logical/correct? Thanks!
  5. Jun 12, 2006 #4


    User Avatar
    Homework Helper

    Yes, that looks right. The reason you have to use that result is that when you expand the expression you get after evaluating at k+1 you have:

    [tex]((1+2+...+k) + (k+1))^2 = (1+2+...+k)^2 + 2 (1+2+..+k)(k+1) +(k+1)^2[/tex]

    You can apply the induction to handle the first term, but you can't do anything with the second term unless you know the expression for that sum. This is essentially two problems in one, finding 1+2+...+k and 13+23+...k3.
  6. Jun 12, 2006 #5
    Yeah, I should have realized that the question would require more than a direct attack. I've been using Apostol for problem sets to practice Induction. It can be tricky at times. Glad to know I finally got it though. Thank you once again for helping :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook