Question

Prove that 2n+1 <= 2^n for n >= 3
By induction:
Proved P(3) is true
Inductive step: P(n+1）: 2n+3 <= 2^(n+1)
0 <= 2(2^n) - 2n + 3
I'm stuck trying to prove this part, help?

Answer 1

Its actually 0 <= 2(2^n) - 2n - 3

Answer 2

In the inductive step, you can use the fact that \(2n+1 \le 2^n\).
\(2n+3=(2n+1)+2\le 2^n+2\).
if by any chance \(2^n+2<2^{n+1}\) (for n>=3) then you are done.

Answer 3

Assume for some \(n\) we have \(P(n)\colon 2n+1\le 2^n\). Now observe:$$2n+1\le 2^n\\2n+1+2\le 2^n+2\\2(n+1)+1\le 2^n+2\le 2^{n+1}$$

Answer 4

\(2^n+2<2^{n+1}\) trivially... think of binary :-p

Answer 5

I'm confused as to how it absolutely proves that 2^n+1 is actually greater for all n