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: Prove using induction

  1. Apr 25, 2010 #1
    1. The problem statement, all variables and given/known data
    Prove using induction


    1.) 1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2

    2.) 1^3 + 2^3 + ... + (n-1)^3 < (n^4)/4 < 1^3 + 2^3 + ... + n^2



    2. Relevant equations



    3. The attempt at a solution

    I dont have a clue about how to start to do the problems can anyone help me ?

    Thanks.
     
  2. jcsd
  3. Apr 25, 2010 #2
    When you don't know what to do, start by writing down what you know.

    How to prove a theorem by induction.

    1) Prove a case (usually n=1 or something).
    2) Prove that if your theorem is true for some value of n, it is true for n+1.

    So start by proving the statements for n=1, or maybe n=3 since the second statement involves n-1.

    Then prove that IF it's true for n, it's true for n+1.
     
  4. Apr 25, 2010 #3

    lanedance

    User Avatar
    Homework Helper

    do you understand the inductive process?

    First show its true for a particular n, usually n=1
    Then asumes it true for n, see if you can show it is then true for n+1 based on that fact

    Then it is true for all n greater than 1 (or whatever value you started at)
     
  5. Apr 25, 2010 #4
    I've done the first question before, it isn't that easy (unless you look it up what I'm going to post below).
    It's related to these numbers (n^3) : (cubic numbers)
    1^2 = 1
    2^3 = 8 = 3 + 5
    3^3 = 7 + 8 + 9
    4^3 = 11 + 13 + 15 + 17
    .. et c
    generalize and these results and prove the generalization, then you may use it for 1^3 + ... + n^3 = (1+2+..+n)^2.

    this may help you: 1 + 3 + ... + 2(n) - 1 = n^2
    good luck
     
  6. Apr 26, 2010 #5

    lanedance

    User Avatar
    Homework Helper

    as i think wisvuze is implying you may need to use a few inductions (rather than just the single inductive step) to get the result - have a try & we'll step through it
     
  7. Apr 26, 2010 #6
    Im familiar with having a single inductive step however the ones that use more step are more complicated.

    I couldnt find a generalization for
    1^2 = 1
    2^3 = 8 = 3 + 5
    3^3 = 7 + 8 + 9
    4^3 = 11 + 13 + 15 + 17

    There is no generalization I could find for 1, 8, 24, and 56. what can I do about it?


    In problem one

    1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2

    would then be

    1^3 + 2^3 + 3^3 + ... + (n+1)^3 = (1 + 2 + 3 + ... + n+1)^2

    but I cant go further from that . because I cant take just n+1 as one single variable in order to make sense I need the other sum of real numbers of the equation.
     
  8. Apr 26, 2010 #7

    lanedance

    User Avatar
    Homework Helper

    ok so examining n+1 case gives (note i've just added tex tags around you formula - try clicking on equation to see what i mean):
    [tex] 1^3 + 2^3 + 3^3 + ... + n^3 + (n+1)^3 = (1 + 2 + 3 + ... +n+ (n+1))^2 [/tex]

    exapanding some of the square
    [tex] (1^3 + 2^3 + 3^3 + ... + n^3) + (n+1)^3
    = ((1 + 2 + 3 + ... +n) +(n+1))^2 [/tex]
    [tex] (1^3 + 2^3 + 3^3 + ... + n^3) + (n+1)^3
    = (1 + 2 + 3 + ... +n)^2 +2(n+1)(1 + 2 + 3 + ... +n) + (n+1)^2[/tex]

    now if we assume the orginal hypothesis is true for n, it reduces to:
    [tex] (n+1)^3 = 2(n+1)(1 + 2 + 3 + ... +n) + (n+1)^2[/tex]

    removing a factor of (n+1)
    [tex] (n+1)^2 = 2(1 + 2 + 3 + ... +n) + (n+1)[/tex]

    if you can prove the above relation you're pretty much there - so you could try induction again (i haven't done it, but looks like a reasonable way to attempt the problem)
     
    Last edited: Apr 27, 2010
  9. Apr 26, 2010 #8
    This last relation follows directly from the formula for summing the first n integers.
     
  10. Apr 27, 2010 #9

    lanedance

    User Avatar
    Homework Helper

    cool, then induction should work for that if you can't just assume it & then you just need to show the hypthesis is true for some starting n value
     
  11. May 15, 2010 #10
    Sorry I have been very busy all this time it has been quite hard to find a way to solve this problem.

    You told me to prove
    [tex] (n+1)^2 = 2(1 + 2 + 3 + ... +n) + (n+1)[/tex]
    but im not sure about how to do that.

    I tried [tex] (n+2)^2 = 2(1 + 2 + 3 + ... +n+1) + (n+2)[/tex]
    then [tex] n^2 +4n +4 = 2 (1+2+3+... +n+1) + (n+2)[/tex]

    But im totally lost here I would appreciate some help.
     
  12. May 15, 2010 #11
    Start by finding a closed formula for:

    [tex] \sum_{k=1}^n k = (1 + 2 + 3 + ... + (n-1) + n) [/tex]
     
  13. May 15, 2010 #12
    What do you mean by a closed formula?
     
  14. May 15, 2010 #13
    Something that's only in terms of n, and doesn't involve a summation.
     
  15. May 15, 2010 #14
    Notice: 1^2 = 1, 2^3 = 3 + 5 .. et c nth term is the sum of n odd numbers, starting from where n-1's odd terms left off

    This question was presented this way in Donald Knuth's popular book "The Art of Computer Programming".
     
  16. May 16, 2010 #15
    [tex] n(n+1)/2 [/tex]

    What use I can give to that in order to prove the original equation?
     
  17. May 16, 2010 #16
    In post #10, you wrote:
    Now you have an expression you can fill in on the right side of that equation, right?
     
  18. May 17, 2010 #17
    ok [tex] (n+1)^2 = n(n+1) + (n+1) [/tex]
    that is [tex] n^2+2n+1 = n^2+2n+1 [/tex]


    How can I start with the second problem?

    2.) [tex] 1^3 + 2^3 + ... + (n-1)^3 < (n^4)/4 [/tex]
     
  19. May 17, 2010 #18
    Now use the result you just proved to substitute in to the left and right sides of the second inequality.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook