Prove that $2^n\geq2n-1$

Question

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!

Answer 1

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$$

Answer 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}$

Answer 3

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$

Answer 4

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$.