Results 1 to 5 of 5

Math Help - Induction: Look correct?

  1. #1
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307

    Induction: Look correct?

    5.2 Prove by induction on  m that  m^{3} \leq 2^{m} for  m \geq 10 .
    Proof: We use induction on  m. Base case: For  n = 10,  m^{3} = 1000 and  2^{10} = 1024 and so  m^{3} \leq 2^{m}. Inductive step: Suppose now as inductive hypothesis that  k^{3} \leq 2^{k} for some  k \geq 10. Then  2^{k+1} = 2 \times 2^{k} \geq 2k^{3} (by induction hypothesis). So we will have proved that  2^{k+1} \geq (k+1)^{3} if we can prove that  2k^{3} \geq (k+1)^{3}. But  2k^{3} \geq (k+1)^{3} \Leftrightarrow 2k^{3} \geq k^{3} + 3k^{2} + 3k + 1 \Leftrightarrow k^{3} \geq 3k^{2} + 3k + 1, and since  k \geq 10,  k^{3} \geq 10k^{2} \geq 3k^{2} + 3k + 2 \geq 3k^{2} + 3k + 1 so that  k^{3} \geq 3k^{2} +3k+1. Hence  2k^{3} \geq (k+1)^{3} and so we have deduced that  (k+1)^{3} \leq 2^{k+1} as required to complete the inductive step. Conclusion: Hence, by induction,  m^{3} \leq 2^{m} for all  m \geq 10.  \square
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tukeywilliams View Post
     m^{3} \leq 2^{m}.
    You wish to show this for m\geq 10.

    Say it is true for m=k, i.e. k^3 \leq 2^k.

    Then, multiply both sides by 2,
    2k^3 \leq 2 \cdot 2^m = 2^{m+1}
    Now if you can show that,
    (k+1)^3 \leq 2k^3
    Then your proof is complete.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    didnt I do that. And is that correct?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by tukeywilliams View Post
    didnt I do that. And is that correct?
    Yes it is correct.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by tukeywilliams View Post
    5.2 Prove by induction on  m that  m^{3} \leq 2^{m} for  m \geq 10 .
    Proof: We use induction on  m. Base case: For  n = 10,  m^{3} = 1000 and  2^{10} = 1024 and so  m^{3} \leq 2^{m}. Inductive step: Suppose now as inductive hypothesis that  k^{3} \leq 2^{k} for some  k \geq 10. Then  2^{k+1} = 2 \times 2^{k} \geq 2k^{3} (by induction hypothesis). So we will have proved that  2^{k+1} \geq (k+1)^{3} if we can prove that  2k^{3} \geq (k+1)^{3}. But  2k^{3} \geq (k+1)^{3} \Leftrightarrow 2k^{3} \geq k^{3} + 3k^{2} + 3k + 1 \Leftrightarrow k^{3} \geq 3k^{2} + 3k + 1, and since  k \geq 10,  k^{3} \geq 10k^{2} \geq 3k^{2} + 3k + 2 \geq 3k^{2} + 3k + 1 so that  k^{3} \geq 3k^{2} +3k+1. Hence  2k^{3} \geq (k+1)^{3} and so we have deduced that  (k+1)^{3} \leq 2^{k+1} as required to complete the inductive step. Conclusion: Hence, by induction,  m^{3} \leq 2^{m} for all  m \geq 10.  \square
    Yes, you are correct. It's just that as written, your proof is kind of hard to read. Try formatting it better so that the reader does not get lost in the sea of words and inequalities. I believe that's why TPH's first post was like that. He probably read through your post once and realized that he had to read it again to really get what you were saying--but thought it easier to just tell you what to do than to read through it again. Your second comment kind of forced him to read through it carefully to see that you did, in fact, do what he suggested in the first place.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: July 29th 2011, 02:39 AM
  2. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Is this correct?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 28th 2010, 09:27 PM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM

Search Tags


/mathhelpforum @mathhelpforum