Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove it

  1. Sep 30, 2003 #1
    [SOLVED] Prove it

    We are starting to do some proofs in my class. I am having a problem starting the problem:
    n>3 then 2n+1<2^n
    Can I start the proof by using contradicition or should I try to apply induction? Any help would be cool, thanks.
  2. jcsd
  3. Sep 30, 2003 #2
    Induction sounds good.
  4. Oct 2, 2003 #3
    that is if you're assuming n is a natural number.

    if n were real...

    let f(n) = 2n+1 and g(n) = 2^n.


    f'(n) = 2 and g'(n) = (2^n)*log(2).

    f'(3)=2 < g'(3) = 8 * log(2) and clearly, g'(n) is monotonically increasing, being an exponential function. (or g''(n) = (2^n) * (log(2))^2, which is positive, implying g' is increasing.)

    therefore, f'(n) < g'(n) for n >= 3.

    therefore, f(n) < g(n) for all n >=3, and not just the natural ones.
    Last edited: Oct 2, 2003
  5. Oct 15, 2003 #4
    n>3 then 2n+1<2^n

    for n=4
    2(4)+1=9<2^4=16 true.
    assume true for some n(obviously n=>4) then then for n+1
    we have
    2(n+1)+1<2^(n+1) ====>
    (2n+1)+2<2^n*2 qed
  6. Oct 17, 2003 #5
    2(n+1)+1 = (2n+1)=2 < (2^n)+2 < (2^n)+(2^n) = 2^(n+1)
    2(n+1)+1 < 2^(n+1)

    and this is the proper way to go about it
    the other way worked on both sides at once and kept the
    <, which is assuming what you were trying to prove.

    Sorry rolandmath, nothing personal
  7. Oct 17, 2003 #6
    well it was my fault i thought it was obvious that

    for all n=>1 but in this case its 3 so were still safe.

    so again

  8. Oct 20, 2003 #7
    Sorry, i should take time to read it better. (oops) You're right of course, sometimes I'm just too picky and I really should lighten up about things being done only one certain way. It's a perfectly good proof. Sorry again.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook