Results 1 to 8 of 8

Math Help - Simple Induction Problem

  1. #1
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1

    Simple Induction Problem

    Prove by induction that, for all n \in N:

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

    Prove for n=1:

    LHS, 1^3 = 1
    RHS, 1^2(2-1)=1

    True for n=1, now assume for n=k,

    1^3 + 3^3 + 5^3 + ... + (2k - 1)^3 = k^2(2k^2 - 1)

    Now the sequence above is for add numbers, assuming that k is odd, then instead of using n=k+1 use n=k+2.

    We then have:

    1^3 + 3^3 + 5^3 + ... + (2(k+2) - 1)^2

    1^3 + 3^3 + 5^3 + ... + (2k+4 - 1)^2

    1^3 + 3^3 + 5^3 + ... + (2k+3)^2.

    Not sure where to go from here? Any help would be great.

    Thank you
    Last edited by craig; November 23rd 2009 at 12:10 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by craig View Post
    Prove by induction that, for all n \subset N:

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

    Prove for n=1:

    LHS, 1^3 = 1
    RHS, 1^2(2-1)=1

    True for n=1, now assume for n=k,

    1^3 + 3^3 + 5^3 + ... + (2k - 1)^3 = k^2(2k^2 - 1)

    Now the sequence above is for add numbers, assuming that k is odd, then instead of using n=k+1 use n=k+2.

    We then have:

    1^3 + 3^3 + 5^3 + ... + (2(k+2) - 1)^2

    1^3 + 3^3 + 5^3 + ... + (2k+4 - 1)^2

    1^3 + 3^3 + 5^3 + ... + (2k+3)^2.

    Not sure where to go from here? Any help would be great.

    Thank you
    I think the error is in your reasoning for this step:
    Now the sequence above is for add numbers, assuming that is odd, then instead of using use .


    even for n=k+1 you will get an odd number. 2k-1 is always odd

    else i think the problem should be trivial (i hvn't tried it, but doesn't look too tough)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    even for n=k+1 you will get an odd number. 2k-1 is always odd

    else i think the problem should be trivial (i hvn't tried it, but doesn't look too tough)
    I wouldn't for n=k+1, but I see what you mean by using 2k-1, I'll let you know how it goes

    Thanks for the reply
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Have no idea how to do this, it can't be this hard can it haha?

    Using n=2k-1

    1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 + (2(2k-1)-1)^3

    1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 + (4k-2-1)^3

    1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 + (4k-3)^3

    Any pointers would be appreciated
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Could you write again carefully your induction hypothesis and what you need to prove? I recommend using k (or n) for the IH, like you did in the first post. Then replace k with k+1 to get what you need to prove.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Quote Originally Posted by emakarov View Post
    Could you write again carefully your induction hypothesis and what you need to prove? I recommend using k (or n) for the IH, like you did in the first post. Then replace k with k+1 to get what you need to prove.
    I proved the result was true for n=1

    Quote Originally Posted by craig View Post
    Prove for n=1:

    LHS, 1^3 = 1
    RHS, 1^2(2-1)=1
    Inductive hypothesis, assume true for n=k

    Quote Originally Posted by craig View Post
    True for n=1, now assume for n=k,

    1^3 + 3^3 + 5^3 + ... + (2k - 1)^3 = k^2(2k^2 - 1)
    The question only involves odd numbers, so wouldn't using n=k+1 result in an add number?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    It does not really matter if you noticed or not that it's the sum of cubes of odd numbers. This problem is solved in a completely general way. The problem asks to prove "For all n\in\mathbb{N}, P(n)", where P(n) is a property of n; in this case an equality that contains n. The base case is to show P(1), which you have already done. For the induction step, the induction hypothesis is P(k). What you need to show is P(k+1). It makes things much clearer if P(k) and P(k+1) are written explicitly. Note that P(k+1) is obtained from P(k) by replacing k with k+1.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member craig's Avatar
    Joined
    Apr 2008
    Posts
    748
    Thanks
    1
    Awards
    1
    Thankyou!

    Using n=k+1, this gives us:

    (1^3 + 3^3 + ... + (2k-1)^3) + (2(k+1)-1)^3

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

    Expanding out the brackets gives us the following quartic:

    2k^4+8k^3+11k^2+6k+1

    Which factorises to give:

    (k+1)^2(2(k+1)^2-1)

    Therefore proof holds for k+1 if true for k.

    Thanks for all the help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with simple induction
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 7th 2011, 03:53 PM
  2. Simple Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2011, 11:54 PM
  3. Replies: 2
    Last Post: April 24th 2010, 08:44 AM
  4. Simple Induction Problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:50 PM
  5. Simple induction help
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: September 29th 2008, 06:29 AM

Search Tags


/mathhelpforum @mathhelpforum