4
$\begingroup$

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!

  • 0
    The first statement after Proof: is incorrect.2012-07-12

5 Answers 5

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.

4

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

  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^+$.
  • 0
    No need to mention :)2012-07-12
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.$

2

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.

1

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.

  • 0
    @E.O. Ahh, so it is, thanks!2012-07-12