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!
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.
there's nothing wrong, here...but it makes for a better flow, if these algebraic manipulations come later in the proof.2n+2+1 < 2^(n+1)
(2n+1)+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.by the inductive hypothesis:
(2n+1)+2 < (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.so I think I have to show that: 2^n + 2 < 2^(n+1)
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 know2^n + 2 < 2^(n+1)
2^n + 2 < (2^n)(2)
2^n + 2 < 2^n + 2^n
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.subtract both sides by 2^n we get
2 < 2^n , which is true for all integers n >= 2
a better proof: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!
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.