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 for all integers n >= 3

__Proof__: Let P(n) be the predicate:

__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!

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

Quote:

Originally Posted by

**yoman360** by the inductive hypothesis:

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

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

Quote:

Originally Posted by

**yoman360** 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

for all integers n >= 3

__Proof__: Let P(n) be the predicate:

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

Quote:

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.

Quote:

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.

Quote:

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.

Quote:

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

Quote:

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.

Quote:

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.