# Prove that $2^n\geq2n-1$

Let $n\geq2$ with $n\in\Bbb N$. Prove that

$$2^n\geq2n-1$$

I need to prove this using mathematical induction. This is what I've tried:

P(2): 2^2\geq2n-1 \\ P(k)\Rightarrow P(k+1) \\ P(k+1): 2^{k+1}\geq2k+1 \\ \begin{align} 2\cdot2^k & \geq2k -1+2 \\ 2^k & \geq2k-1 \end{align}

I am not sure if what I've done will finally lead to something or if it's already enough, but please, tell me how can I handle this type of exercises in general! Thank you!

• It is ok. For precision, explain that the last inequality is from inductive hypothesis, and (obviously) $2^k\geq 2$, hence $2\cdot 2^k \geq 2k-1+2$. Nov 13, 2014 at 19:19

It is much better writing first your assumption and then write your deductions. That is: first write $P(k)$: $$2^k\ge2k-1$$ Now try to do something to get $P(k+1)$. In this case, add $2^k$: $$2^k+2^k\ge2k-1+2^k$$ which is$$2^{k+1}\ge 2k-1+2^k$$ Now use the fact $2^k>2$: $$2^{k+1}\ge2k-1+2^k>2k-1+2=2(k+1)-1$$ and you are done.

Alternatively, you can try to write $2^{k+1}$ and make a chain of inequalities that ends in $2k+1$, using in this process that $P(k)$ which you have assumed:

$$2^{k+1}=2\cdot2^k\stackrel{P(k)\text{ used here}}\ge2(2k-1)=(2k-1)+(2k-1)\ge(2k-1)+2$$

$\displaylines{ k = 1 \Rightarrow 2 \ge 1\quad true \cr if\quad 1 < k:2^k \ge 2k - 1 \cr \Rightarrow 2 \times 2^k \ge 2 \times \left( {2k - 1} \right) \cr \Rightarrow 2^{k + 1} \ge 4k - 2 \ge 2k + 1 \cr \cr if:4k - 2 < 2k + 1 \Leftrightarrow 2k - 3 < 0 \cr \Leftrightarrow k < \frac{3}{2} \Rightarrow k = 1\quad or\;k = 0 \cr}$

• This answer contains a good proof, but I feel that it's badly presented. For example, the use of the word "if" and the implication arrows is confusing. Could you edit your answer so that the reasoning comes in the form of sentences so that the logic is more clear? Nov 13, 2014 at 19:34

we have to prove that $2^{n+1}\geq 2(n+1)-1$ if $2^n\geq 2n-1$ is hold, multiplying the last inequality by $2$ we get $2^{n+1}\geq 2(2n-1)=4n-2\geq 2n+1$

What you did is almost correct, the one nitpick is that you want to prove that $P(k)\implies P(k+1)$ and then you start with the fact that $P(k+1)\implies2^{k+1}\ge 2k+1$ and arrive at $P(k+1)\implies 2^k\ge 2k-1$ which is the same as $P(k+1)\implies P(k)$. However the thing you're trying to prove is $P(k)\implies P(k+1)$ so you need to start with $2^k\ge 2k-1$.