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!