1. Limited time only! Sign up for a free 30min personal 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!

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