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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Arden1528
- Start date

- #1

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

Lonewolf

- 337

- 1

Induction sounds good.

- #3

phoenixthoth

- 1,605

- 2

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.

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:

- #4

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

- #5

synergy

- 62

- 0

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

- #6

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)

- #7

synergy

- 62

- 0

Aaron

Share:

- Last Post

- Replies
- 11

- Views
- 610

- Last Post

- Replies
- 1

- Views
- 88

- Last Post

- Replies
- 1

- Views
- 264

- Last Post

- Replies
- 14

- Views
- 449

MHB
Prove for all Z+

- Last Post

- Replies
- 6

- Views
- 570

- Last Post

- Replies
- 6

- Views
- 317

- Last Post

- Replies
- 2

- Views
- 738

- Replies
- 5

- Views
- 901

- Last Post

- Replies
- 10

- Views
- 1K

- Last Post

- Replies
- 5

- Views
- 980