Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
You can do this easily without induction: Compute derivatives! –  fpqc Jul 12 '12 at 10:54
    
The first statement after Proof: is incorrect. –  i. m. soloveichik Jul 12 '12 at 13:23
add comment

5 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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