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!

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

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.

$\endgroup$
  • $\begingroup$ I think $2(n+1)=2n+2$ $\endgroup$ – E.O. Jul 12 '12 at 12:02
  • $\begingroup$ @E.O. Ahh, so it is, thanks! $\endgroup$ – Thomas Russell Jul 12 '12 at 12:06
4
$\begingroup$

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^+$.
$\endgroup$
  • $\begingroup$ thanks for your answer sir now i'm not confused anymore!! $\endgroup$ – John Lemuel Jul 12 '12 at 10:53
  • $\begingroup$ No need to mention :) $\endgroup$ – Aang Jul 12 '12 at 11:23
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.