Is Induction or Contradiction Better for Proving 2n+1 < 2^n When n > 3?

[Arden1528]

[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.

 

[Lonewolf]

Induction sounds good.

 

[phoenixthoth]

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(3)=7<8=g(3).

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.

 

[rolandmath]

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

 

[synergy]

2(n+1)+1=
2(n+1)+1 = (2n+1)=2 < (2^n)+2 < (2^n)+(2^n) = 2^(n+1)
so,
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
Aaron

 

[rolandmath]

well it was my fault i thought it was obvious that

2^n*2=2^n+2^n
and
2*2^n=2^(n+1)
and
2<2^n
for all n=>1 but in this case its 3 so were still safe.

so again

(2n+1)+2<2*2^n=2^(n+1)

 

[synergy]

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.
Aaron