Prove it

  • Thread starter Arden1528
  • Start date

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.
 
334
1
Induction sounds good.
 
1,570
1
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.
 
Last edited:

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
 
62
0
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)
 
62
0
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
 

Related Threads for: Prove it

Replies
4
Views
3K
Replies
4
Views
3K
Replies
1
Views
2K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
1
Views
2K
  • Posted
Replies
2
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top