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

Homework Help: Is My Proof by Induction Correct?

  1. Jun 21, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove the formula by induction:

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


    2. Relevant equations

    [tex]1 + ... + n = n(n+1)/2[/tex]


    3. The attempt at a solution

    I started by showing that the formula holds for 1, since:

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

    Then I set about trying to prove that, if [tex]n[/tex] is true then [tex]n+1[/tex] is true as well, since this would prove the formula since we have our first validation of [tex]n[/tex] in the correct formula for [tex]1^3[/tex]. Here goes:

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

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

    Now I'll work with [tex](1 + ... + n)^2 + (n + 1)^3[/tex], since that is equivalent to [tex] 1^3 + ... + n^3 + (n + 1)^3[/tex].

    I'm trying to prove, then, that [tex](1 + ... + n)^2 + (n + 1)^3 = (1 + ... + n + n + 1)^2[/tex].

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

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

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

    Next I used the relevant equation:

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

    Now it's just basic algebra:

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

    [tex](n + 1)(n+1)(n+1) = (n+1)(n^2 + n) + (n^2 + 2n + 1)[/tex]

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

    [tex] n^3 + 3n^2 + 3n + 1 = n^3 + 3n^2 + 3n + 1[/tex]

    Therefore:

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

    Therefore:

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

    So what is true for [tex]n[/tex] is true for [tex]n + 1[/tex] and the proof by induction seems to be complete. I just learned this method of proof, so critiques appreciated. Sorry for how long it is! I have a feeling it could be cleaned up more than a little bit.

    Thanks.
     
  2. jcsd
  3. Jun 21, 2010 #2

    Mark44

    Staff: Mentor

    Something like "... if the statement is true for n, then it will be true for n + 1" is what you want to say. n is a number, not something that is true or false.

    What you have is a sequence of statements P(1), P(2), ..., P(n), P(n + 1), ... You show that P(1) or some other base-case statement is true, then show that if P(n) is true, it necessarily follows that P(n + 1) is true as well.
    OK, this is P(n).
    And this is P(n + 1).
    Don't start off assuming what you want to show. Start with 1^3 + 2^3 + ... + n^3 + (n + 1)^on the left side and work with it until you reach (1 + 2 + ... + n + (n + 1))^2.

    BTW, you can cut probably half or more of what you have below.
    Above, you have reached a statement that is identically true. If you can convince yourself and me that all of your steps are reversible operations, then you can conclude that the original equation must also be true.

    A better way to do things, IMO, is to start with
    [tex](1 + ... + n)^2 + (n + 1)^3 [/tex]

    and work with it to reach
    [tex] (1 + ... + n + n + 1)^2[/tex]

    [tex]1^3 + 2^3 ... + n^3 + (n + 1)^3 = (1 + 2 + ... + n)^2 + (n + 1)^3 \text{By induction hypothesis}[/tex]
    [tex]= (\frac{n(n + 1)}{2})^2 + (n + 1)^3[/tex]
    [tex]= \frac{n^2(n + 1)^2}{4} + \frac{4(n + 1)^3}{4}[/tex]
    [tex]= \frac{(n + 1)^2(n^2 + 4n + 4)}{4} = \frac{(n + 1)^2(n + 2)^2}{4}[/tex]
    [tex]= (1 + 2 + ... + n + (n + 1))^2[/tex]
    Therefore (you should use this only once)
    [tex]1^3 + 2^3 ... + n^3 + (n + 1)^3 = (1 + 2 + ... + n + (n + 1))^2[/tex]
     
  4. Jun 21, 2010 #3
    This was an error of expression on my part. I meant what you said (that " the statement is true for n".)

    Again this is an error of expression on my part. By writing that, I was really trying to say something along the lines of "can we prove that this expression is true?" However, I will keep your point in mind in future problems, since I can see how what I wrote is actually wrong.

    Ah, I can see how your way accomplishes the same result in a much shorter time (and so, I guess, is a better proof). I suppose my long-winded proof is the way it is because I didn't stop to clean it up any (the proof is the thought process I went through).
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook