Page 1 of 2 12 LastLast
Results 1 to 15 of 19
Like Tree1Thanks

Math Help - Proving inequality through induction

  1. #1
    Member
    Joined
    May 2009
    Posts
    109

    Proving inequality through induction

    2^k > 4k

    2^k > 4k = 2^k - 4k < 0

    2^{k+1}-4(k+1) = 2 x 2^k -4(k+1)
    > 2 x 4k - 4(k+1), using 2^k > 4^k,
    =8k -4k - 4 = 4k -4

    I don't understand what has happened in the second to last step here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,548
    Thanks
    1418

    Re: Proving inequality through induction

    It's not true. Try k = 2, we have \displaystyle \begin{align*} 2^2 = 4 \end{align*} and \displaystyle \begin{align*} 4 \cdot 2 = 8 \end{align*}, so the inequality does not hold...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    The text says "This expression is greater than 0 for K > 1. So Proof by mathematical induction works, except we cannon start at n = 1."

    I just don't follow the working.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,548
    Thanks
    1418

    Re: Proving inequality through induction

    I have just proved to you that the inequality is not true. Arguing that it is will not change that. Either state that \displaystyle \begin{align*}  k \geq 5 \end{align*} or stop trying.
    Last edited by Prove It; May 21st 2012 at 06:18 AM.
    Thanks from Reckoner
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    Yes sorry I should have stated that k has to be equal to or larger than 5. I didn't mean to try to argue with you. It's just that I'm trying to understand what is happening in the second to last step in the working. I can't see how the expression on the left is converted into an equality and then what it means to have an equality there.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1

    Re: Proving inequality through induction

    Quote Originally Posted by alyosha2 View Post
    Yes sorry I should have stated that k has to be equal to or larger than 5.
    Because 2^5>4\cdot 5, the base case it true.

    Suppose that N>5 and 2^N>4\cdot N.
     \begin{align*}2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N)\\&= (4\cdot N)+ (4\cdot N)\\&\ge  4(N+1)\end{align*}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    Quote Originally Posted by Plato View Post
    Because 2^5>4\cdot 5, the base case it true.

    Suppose that N>5 and 2^N>4\cdot N.
     \begin{align*}2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N)\\&= (4\cdot N)+ (4\cdot N)\\&\ge  4(N+1)\end{align*}
    I'm sorry I don't understand


    how does 2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N) How does an integer equal an equality?

    how do you get from this line to the last?

    How does this relate to the original working I posted?

    I'm trying to understand how we go from an integer expression to an equality and then back again and how I am supposed to understand the meaning of this equality. To put it simply one equals a number and the other is true or false so how can they be equal?


    Thanks.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1

    Re: Proving inequality through induction

    Quote Originally Posted by alyosha2 View Post
    I'm sorry I don't understand
    how does 2^{N+1}=2\cdot 2^N&\ge 2(4\cdot N) How does an integer equal an equality?
    One step at a time.
    1) Do you understand 2^{N+1}=2\cdot 2^N&~?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    Quote Originally Posted by Plato View Post
    One step at a time.
    1) Do you understand 2^{N+1}=2\cdot 2^N&~?
    yes.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1

    Re: Proving inequality through induction

    Quote Originally Posted by alyosha2 View Post
    yes.
    OK then:
    2) the inductive step says if N>5 then 2^N>4\cdot N.
    Therefore 2\cdot 2^N>2(4\cdot N). Do you see that?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    yes.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1

    Re: Proving inequality through induction

    Quote Originally Posted by alyosha2 View Post
    yes.
    Good. 3)
    2(4\cdot N)=4\cdot N+4\cdot N

    But 4\cdot N>4

    So 4\cdot N+4\cdot N>4\cdot N+4=4(N+1)
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    I'm sorry I don't see how we go from an equality on the left to an number on the right.

    Also, what is the significance of 4N being larger than 4?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1

    Re: Proving inequality through induction

    Quote Originally Posted by alyosha2 View Post
    I'm sorry I don't see how we go from an equality on the left to an number on the right.
    Also, what is the significance of 4N being larger than 4?
    Well think about it.

    I don't think you are ready to do this question.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    May 2009
    Posts
    109

    Re: Proving inequality through induction

    Well an equality has a Boolean value that is either true of false. So the left hand side of the equation must be equal to one of two values. True of False. The expression on the right hand side is a number. How can you equate them?

    You obviously can because that is what you are doing I just don't understand how you are doing it.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Induction: an inequality
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: June 16th 2011, 06:42 PM
  2. Induction Inequality
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 17th 2011, 01:47 PM
  3. Replies: 3
    Last Post: December 12th 2010, 01:16 PM
  4. Induction for an inequality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 5th 2010, 10:51 PM
  5. induction inequality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2010, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum