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!

Solution 1:

We need to prove $2n\leq 2^n$.

1. For $n=1, P(1)$ is $2(1)\leq 2^1$ which is true.

2. Now, Assuming $P(k)$ is true $\implies 2k\leq 2^{k}$.

3. Then, to prove $P(k+1)$ is true,

$$ \begin{align} 2k + 2 &\leq 2 ^ k + 2 && \text{(from assumption of $P(k)$)} \\ 2^k+2 &\leq (2^k+2^k = 2^{k+1})\implies 2(k+1)\leq 2^{k+1} \\ \end{align} $$

4. 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^+$.

Solution 2:

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

Solution 3:

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.

Solution 4:

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.