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

  1. Sep 23, 2003 #1

    I have to prove the following by induction for all of n which are elements of N:

    1^3 + 2^3 + ... n^3 = 1/4 * n^2 * (n + 1)^2

    Now, I have never been successful at proofs, much less proofs by induction. And I never have really had any formal instruction on how to construct a proof by induction. So I could use all the help I can get.

    NOTE: I do NOT want someone to give me an answer. I would rather someone guide me to an answer illustrating a formal method of constructing a proof by induction (with anotations on the side if possible). [?]

    BTW, I am using "Schaum's Outlines: Modern Abstract Algebra". And my question is in Chapter 3: Natural Numbers, page 37, 25 c).

    I know this is a tall order, but if anyone cares to spend the time to teach, I will most certainly spend the time to learn.

    Here is my work so far. Note: Although I may have some steps in the proper order, and it may seem like I know what I am doing, I really do not. That is, I don't know the reasoning behind every step that I do and why it is in the format that it is. That being said, onto the proof.


    == state the proposition

    P(n): 1^3 + 2^3 + ... n^3 = 1/4 * n^2 * (n + 1)^2

    for every n which is an element of N (the set of Natural numbers).

    Base Case: P(1)

    == show that the proposition holds for the first element in the set.

    1^3 = 1/4 * 1^2 * (1 + 1)^2
    1 = 1

    So P(1) is true.

    Inductive Case:

    == show that if the proposition holds for an element k, it should hold for it's successor.

    If P(k) is true then P(k+1) must be also true.

    (Here is where I am definitely in the dark on how to proceed).

    Any help is appreciated. BTW, how is the proof so far? Am I interpreting it correctly? And is my format sound?
  2. jcsd
  3. Sep 23, 2003 #2

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Oooh, I love these! :smile:

    Let me start from scratch.

    Proof by Induction
    For some statement P(n) on some integer n, if it is the case that:

    1. P(1) is true and
    2. P(k)-->P(k+1),

    for some integer k, then it is the case the P(n) is true for all n.

    The statement P(n) in your case is that:

    edit: After the summation sign (Σ), the subscript (j=1) gives the lower limit of summation, and the superscript (n) gives the upper limit of summation. Sorry, I can't make it look any prettier than that.


    You've shown that P(1) is true. For the inductive step, write down P(k+1) and try to extract P(k) from it.


    Note that all I did is substitute k+1 for n wherever n appears in P(n). Now, note that I can rewrite the sum above as a sum from 1 to k, plus the (k+1)st term, as follows:


    Now note that the sum from 1 to k is just P(k). Assuming P(k) is true, you can cancel it from the left hand side if you also cancel the right side of P(k) from the right side of P(k+1). You should be left with an identity, which proves that P(k) implies P(k+1).

    edit: just worked it out and it comes out perfect
    Last edited: Sep 23, 2003
  4. Sep 23, 2003 #3
    Ok. I did what you did Tom all the way up to the point where I sub into P(n) k+1 for every n in P(n). But it is the extraction of P(k) which gives me trouble.

    BTW, the phrasing "extract P(K)" was perfect. That was a part I didn't originally understand with respect to induction. But you rectified that.

    I see this part:

    But I can seem to get this part:

    Last edited by a moderator: Sep 23, 2003
  5. Sep 23, 2003 #4

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    OK, note that the part in blue below is just P(k).


    What you need to do is expand the right hand side of both P(k) and of P(k+1). Then, you can subtract Σj=1kj3 from the left side of the above, and you can also subtract (1/4)x2(x+1)2 from the right side of the above (since those two quantities are equal).

    What you will be left with is:




    which is an identity.

    edit: fixed an omission
    Last edited: Sep 23, 2003
  6. Sep 23, 2003 #5
    Geez Tom, I must be the most dense substance on the planet. I can see what you are doing the left side of the equation. But I just can't see what you are doing on the right side. I also understand what you are saying. I just cannot see it.

    :frown: [?]

    I see this and worked out this relation:


    and I see and worked out this part of the next relation on the left side myself:

    [sum]i=1ki3 + (k+1)3

    But I don't see how you arrived at


    on the left side.

    This is what I would have at if I was to do it:


    How did you get a power of three? I can't see that. [?]

    If I was to do it this way:

    { (1/4)(k2)(k+1)2 } + (k+1)3

    I still don't see how I would get


    What the hey??!!?? :frown: [?]

    Am I missing some basic algebraic step? [?]

    At least I understand what you are trying to do. I just don't understand how you arrived at the answer.
  7. Sep 23, 2003 #6

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    OK, here is the solution in all the gory details.


    Expanding the rightmost side, I get:


    Now, look at P(k+1):


    I am going to manipulate both sides of this statement, one at a time:

    Isolate (k+1)st Term On Left Side:

    Expand Right Side:

    So, I have:


    Now, remember P(k)? Assume it is true, and subtract it from P(k+1). It will be handy if you subtract the left side of P(k) from the left side of P(k+1), and do likewise with their right sides. I am going to denote both sides of P(k) with the color blue.

    Then you get:


    And finally,


    which is an identity. Therefore, P(k)-->P(k+1).

    edit: fixed superscript bracket
  8. Sep 23, 2003 #7

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You mean the right side, don't you?

    Ah, see, that's a sophisticated mathematical technique known as a "mistake".

    Sorry, I've fixed the error. It should read as you have it below:

    Yes, that's it. Proceed from there.
  9. Sep 23, 2003 #8
    Alright. I thought I was going insane there for a minute.

    I have been known to make some pretty weird mathematical assumptions. (You know your assumptions are weird when the prof. looks at you with that look, "What the heck are you doing in my class?" It sure shakes one's confidence in one's mathematical abilities).

    Oh, by the way, for future reference, I do not know my right from my left.

    Ok. I will see if I can get the proof without looking at your solution. I don't like copying. I like doing. I just need a little help implementing it.

    Thanks for your help Tom.

    Especially for the comment about extractin P(k). That comment sort of crystalized things for me.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Proof by Induction
  1. Induction Proof (Replies: 4)

  2. Proof by induction (Replies: 4)