# Prove by mathematical induction that $2n ≤ 2^n$, for all integer $n≥1$?

I need to prove $2n \leq 2^n$, for all integer $n≥1$ by mathematical induction?

This is how I prove this:

Prove:$2n ≤ 2^n$, for all integer $n≥1$

Proof: $2+4+6+...+2n=2^n$

$i.)$ Let $P(n)=1 P(1): 2(1)=2^1\implies 2=2$. Hence, $P(1)$ is true.

$ii.)$ Assume that $P(n)$ is true for $n=k$, i.e, $2+4+6+...+2k=2^k$, and prove that $P(n)$ is also true for $n=k+1$, i.e, $2+4+6...+2(k+1)=2^{(k+1)}$

from the assumption add $2(k+1)$ on both sides so we have $2+4+6...2k+2(k+1)=2^k+2(k+1)$

I'm confused with $2^k+2(k+1)$, I don't know how to make $2^k$ be equivalent to $2^{k+1}$. I feel i'm doing something wrong.

Any help would be appreciated!

-
You can do this easily without induction: Compute derivatives! – user38268 Jul 12 '12 at 10:54
The first statement after Proof: is incorrect. – i. m. soloveichik Jul 12 '12 at 13:23

## 5 Answers

Begin with the basis case:

$$P(1): 2(1)\leq2^{1}\implies P(1) \text{ is true}$$

Next let's look at the inductive step:

$$P(n)\implies P(n+1): 2(n+1)=2n+2, 2^{n+1}=2\cdot2^{n}$$

Through our inductive hypothesis we assume that $2n\leq2^{n}$, and as $\forall n\in\mathbb{N}$, $2^{n}>1$, doubling this must be greater than or equal to adding 2 to the other side. Therefore we can see that if $P(n)$ is true, then it implies $P(n+1)$ must also be true.

To conclude, as we have shown that $P(1)$ is true, and that if $P(n)$ is true, then $P(n+1)$ is also true. Therefore, $P(n)$ must hold for all $n\in\mathbb{N}$. Q.E.D.

-
I think $2(n+1)=2n+2$ – E.O. Jul 12 '12 at 12:02
@E.O. Ahh, so it is, thanks! – Shaktal Jul 12 '12 at 12:06

we need to prove $2n\leq 2^n$. For $n=1, P(1)$ is $2(1)\leq 2^1$ which is true. Now, Assuming $P(k)$ is true $\implies 2k\leq 2^{k}$. Then, to prove $P(k+1)$ is true, $2(k+1)=2k+2\leq2^k+2$(from assumption of $P(k)$) and $2^k+2\leq (2^k+2^k=2^{k+1})\implies 2(k+1)\leq 2^{k+1}$. Hence $P(k+1)$ is true whenever $P(k)$ and since $P(1)$ is true $\implies 2n\leq 2^n \forall n\in \Bbb Z^+$.

-
thanks for your answer sir now i'm not confused anymore!! – John Lemuel Jul 12 '12 at 10:53
No need to mention :) – Aang Jul 12 '12 at 11:23

Hint $\$ By telescopy it reduces to the trivial induction that a product of terms $\ge 1$ is $\ge 1$, viz.

$$\rm f(n)\, =\, \frac{2^n}{2n}\, =\ f(1)\, \prod_{k\:=1}^{n-1}\,\frac{f(k+1)}{f(k)}\ =\ \prod_{k\:=1}^{n-1}\,\frac{2k}{k+1}\ =\ \frac{1\cdot 2}{\color{#C00}{\rlap{-}2}}\ \frac{2\cdot \color{#C00}{\rlap{-}2}}{\color{#0A0}{\rlap{-}3}}\ \frac{2\cdot\color{#0A0}{\rlap{-}3}}{\color{blue}{\rlap{-}4}}\ \frac{2\cdot\color{blue}{\rlap{-}4}}{\color{brown}{\rlap{-}5}}\ \cdots\ \frac{2\,{\rlap{---}{(n\!-\!1)}}}n\ \ge\ 1$$

Notice that the product has each term $\rm\: 2k/(k+1) \ge 1\:$ since $\rm\:2k \ge k+1\iff k\ge 1.\$

In a similar way one may exploit telescopy to simplify many inductive proofs to trivial inductions, e.g. the additive analog of the above: a sum is $\ge 0\,$ if each summand is $\ge 0.$

-

Ok so the base case is true since $2^1 = 2 \geq 2$.

Now we try the inductive step. Suppose that for some $k\geq 1$ we have that $2^k \geq 2k$. We have to use this "fact" to somehow prove that $2^{k+1} \geq 2(k+1) = 2k+2$.

Well $2^{k+1} = 2(2^k)$. By our assumption we must have that:

$2(2^k) \geq 2(2k)=4k$

But for $k\geq 1$ we know that $4k \geq 2k+2$ (check this). Thus $2^{k+1} \geq 2k+2$ is true under our assumption.

So by induction we have proved the statement.

-

Recall that, by induction, $$2^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1} + \binom{n}{n}.$$ All the terms are positive; observe that $$\binom{n}{1} = n, \quad \binom{n}{n-1} = n.$$ Therefore, $$2^n \geq n+n=2n.$$

Remark: I suggest this proof since the plain inductive proof of your statement has been given in many answers. I also believe that an inductive proof of the binomial expansion is an instructive exercise, probably more instructive than the one you are trying to solve.

-