Results 1 to 3 of 3

Math Help - Inequality Induction Proof 2n+1 < 2^n for all integers n>= 3

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    253

    Inequality Induction Proof 2n+1 < 2^n for all integers n>= 3

    So I have an exam tomorrow for my discrete math class and I was doing the suggested practice problems for the exam. So far I understand and know how to do all the types of induction problems except the inequality proofs.

    I know how to start off the inequality proof, but I don't how to finish it.

    Prove 2n+1 < 2^n for all integers n >= 3

    Proof: Let P(n) be the predicate: 2n+1 < 2^n

    Basis Step: P(3) says:

    2(3) + 1 < 2^3
    7 < 8 <== this is true!

    Inductive Step: Assume P(n) is true, prove P(n+1)

    P(n+1) ==> 2(n+1)+1 < 2^(n+1)
    2n+2+1 < 2^(n+1)
    (2n+1)+2 < 2^(n+1)

    by the inductive hypothesis:
    (2n+1)+2 < (2^n) + 2 < 2^(n+1)

    so I think I have to show that: 2^n + 2 < 2^(n+1)

    2^n + 2 < 2^(n+1)
    2^n + 2 < (2^n)(2)
    2^n + 2 < 2^n + 2^n
    subtract both sides by 2^n we get

    2 < 2^n , which is true for all integers n >= 2

    I'm not to sure if I did that last part correctly. My professor can't teach very well and the book doesn't really make sense either. Any help would be appreciated. Thanks!
    Last edited by yoman360; November 8th 2011 at 08:39 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Inequality Induction Proof 2n+1 < 2^n for all integers n>= 3

    Quote Originally Posted by yoman360 View Post
    by the inductive hypothesis:
    (2n+1)+2 \color{blue}< (2^n) + 2 < 2^{(n+1)}
    I'm not to sure if I did that last part correctly.
    The part in blue is correct, but I think you need to show why.

    Because 2^n+2<2^n+2^n=2\cdot 2^n=2^{n+1}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,325
    Thanks
    700

    Re: Inequality Induction Proof 2n+1 < 2^n for all integers n>= 3

    Quote Originally Posted by yoman360 View Post
    So I have an exam tomorrow for my discrete math class and I was doing the suggested practice problems for the exam. So far I understand and know how to do all the types of induction problems except the inequality proofs.

    I know how to start off the inequality proof, but I don't how to finish it.

    Prove 2n+1 < 2^n for all integers n >= 3

    Proof: Let P(n) be the predicate: 2n+1 < 2^n

    Basis Step: P(3) says:

    2(3) + 1 < 2^3
    7 < 8 <== this is true!

    Inductive Step: Assume P(n) is true, prove P(n+1)

    P(n+1) ==> 2(n+1)+1 < 2^(n+1)
    as a general rule, it is easier to read inductive proofs if you don't put what you want to prove ahead of the proof.
    2n+2+1 < 2^(n+1)
    (2n+1)+2 < 2^(n+1)
    there's nothing wrong, here...but it makes for a better flow, if these algebraic manipulations come later in the proof.

    by the inductive hypothesis:
    (2n+1)+2 < (2^n) + 2 < 2^(n+1)
    only the FIRST inequality is true by the induction hypothesis. the second one is what you are trying to PROVE. you want the cart after the horse.

    so I think I have to show that: 2^n + 2 < 2^(n+1)
    yes, so you shouldn't state it or use it, before you prove it. all of this should come much earlier in your proof, and most of what has come before, shouldn't be there yet.



    2^n + 2 < 2^(n+1)
    2^n + 2 < (2^n)(2)
    2^n + 2 < 2^n + 2^n
    this is exactly backwards. this may have been how you reasoned out the answer, but in proof-writing, you go from known-->consequences, not: what i want to prove--->things i already know
    subtract both sides by 2^n we get

    2 < 2^n , which is true for all integers n >= 2
    nope. you only know it is true for integers from 3 up to n, so far. i mean, yes, you're essentially done at this point, but you're not sure WHY. the induction hypothesis assumes this is true, and you have shown that P(n+1) is a consequence of P(n), so NOW, your base case kicks in and proves 4,5,6,7,8,9,......and so on.

    I'm not to sure if I did that last part correctly. My professor can't teach very well and the book doesn't really make sense either. Any help would be appreciated. Thanks!
    a better proof:

    P(3) is true: 2(3) + 1 = 7 < 8 = 2^3.

    assume that P(n) is true: 2n+1 < 2^n, for n ≥ 3.

    then:

    2n + 1 + 2 < 2^n + 2 (by our induction hypothesis)
    2^n + 2 < 2^n + 2^n (since n ≥ 3 > 1)
    2^n + 2^n = 2(2^n) = 2^(n+1) (distributive law, and rules of exponents)

    therefore:

    2(n+1) + 1 < 2^(n+1) (transitivity of <)

    since we have derived P(n+1) from P(n), we conclude P is true for all n ≥ 3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction proof concerning a finite sum inequality
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 11th 2011, 08:44 AM
  2. Proof of mathematical induction inequality
    Posted in the Algebra Forum
    Replies: 5
    Last Post: March 15th 2010, 03:34 PM
  3. Proof of inequality by transfinite induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 10th 2010, 10:17 AM
  4. Induction Proof (Inequality) SIMPLE!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 3rd 2010, 02:58 AM
  5. Integers and induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 10th 2009, 12:44 PM

Search Tags


/mathhelpforum @mathhelpforum