Proof Using Mathematical Induction that $2^n \geq n + 1$

Question

$2^n \geq n + 1$, for all $n \geq 1$

So I know that first I should use 1, which I did to make sure step 1 holds. $$2 ^ 1 \geq 1 + 1\\2 \geq 2\\ \mathsf{TRUE}$$

After I figure this out, I know I am then supposed to assume it true for $k$, so I get $2 ^ k \geq k + 1$, but its the whole $k+1$ step that completely looses me. Where would I do from here? I am assuming that I have to get $2 ^ k \geq k + 1$ to equal $2 ^{k+1} \geq k+1 + 1$, but am not sure how to get there.

Answer 1

You want to show that $2^{k+1}\geq(k+1)+1$ using the induction hypothesis. This hypothesis concerns $2^k$, so you will want to make this term appear from $2^{k+1}$. Just remark that $2^{k+1}=2\cdot2^{k}$. Hence, using the induction hypothesis, you can infer $$ 2^{k+1}=2\cdot2^{k}\geq2\cdot(k+1)=2k+2\geq k+2=(k+1)+1 $$ which is what you wanted.

Answer 2

$2^{k+1}=2^k\cdot 2=2^k+2^k\ge(k+1)+1=k+2$ by using induction hypothesis $2^k\ge k+1$ and $2^k\ge 1$

Answer 3

You are off to a great start.

So, assuming that $2^k\geq k+1$ then: $$\begin{align}&\quad 2^{k+1} \\[1ex]&= 2(2^k) \\[1ex]&\geq 2(k+1) \tag 1 \\[1ex]&= (k+1)+(k+1)\\[1ex]&\geq (k+1)+1 \tag 2\end{align}$$

Can you justify these steps?

Then you have that $\forall k\geq 1: \Big(\big(2^k\geq k+1\big) ~\implies~\big(2^{k+1}\geq (k+1)+1\big)\Big)$ and $2^1\geq 1+1$ so...

Answer 4

By AM-GM inequality $\frac{2^n+(n-1)}{n}=\frac{2^n+1+1+...+1}{n}\ge \sqrt[n]{2^n}=2\implies 2^n \ge 2n-(n-1)=n+1$