# Homework Help: Prove that 2n ≤ 2^n by induction.

1. Jun 24, 2011

### -Dragoon-

1. The problem statement, all variables and given/known data
Prove and show that 2n ≤ 2^n holds for all positive integers n.

2. Relevant equations
n = 1
n = k
n = k + 1

3. The attempt at a solution
First the basis step (n = 1):
2 (1) ≤ 2^(1) => 2 = 2.
Ergo, 1 ϵ S.

Now to see if k ϵ S:
2 (k) ≤ 2^k
But, k ϵ S implies k + 1 ϵ S:
2(k + 1) ≤ 2^(k + 1)
2k + 2 ≤ 2^k · 2^1

Now, where do I go from here to prove this formally and that k + 1 ϵ S, thus proving that 2n ≤ 2^n holds for all positive integers n?

2. Jun 24, 2011

### spamiam

Your wording puzzles me. In the induction step, you assume the result for n = k (i.e., assume $2k \leq 2^k$), and try to show that this implies the result for n = k+1. So you need to show $2(k+1) \leq 2^{k+1}$, using the assumption that $2k \leq 2^k$.

I think the key is rewriting $2^{k+1} = 2^k \cdot 2$ using addition. Can you see how to use the inductive assumption with this?

3. Jun 24, 2011

### -Dragoon-

That is exactly what I am struggling with. How would I apply the inductive process at this stage?

4. Jun 24, 2011

### Mentallic

So you have $$2(k+1)\leq 2\cdot 2^k$$

Divide through by 2 now and notice that if a<c and if you want to show that b<c, then all you need to do is show b<a.

5. Jun 24, 2011

### -Dragoon-

So, that leaves us with $$k + 1\leq 2^{k}$$

So, now I would have to prove $$k + 1\leq 2(k + 1)$$ correct?

6. Jun 24, 2011

### spamiam

I would rewrite $2^k \cdot 2$ as $2^k + 2^k$. So now you're trying to show
$$2k +2 \leq 2^k + 2^k$$

which should follow from the inductive assumption without too much trouble.

7. Jun 24, 2011

### Mentallic

Not quite.

We have to show $$k+1\leq 2^k$$ and we know that $$2k\leq 2^k$$ by our assumption. Take the assumption as being $$a<c$$ and what we have to show is true as being $$b<c$$ and now show that $$b<a$$ therefore, $$b<a<c$$ thus $$b<c$$ so we have proven it true.

You might even find spamiam's method to be simpler.

p.s. I don't like that tex now makes new lines every time. I liked it the way it was before...

8. Jun 25, 2011

### -Dragoon-

But, this is exactly what was done in my book:
From that step, that is, rewriting $$2^k \cdot 2$$ as $2^k + 2^k$, they infer that $$k \geq 1$$ and write "this places k + 1 in S" and then proceed to rewrite it back as $$2\cdot 2^k$$ and then $$2^{k+1}$$. But, if they came back to where they began then how did they formally prove it to begin with?

9. Jun 25, 2011

### -Dragoon-

So:
$$k+1\leq 2k$$ and therefore $$k+1\leq 2k \leq 2^{k}$$ thus $$k+1\leq 2^{k}$$

So now it has been formally proven that k + 1 holds for all positive integers n? I actually prefer to learn both methods, as the more ways I have to approach a problem, the better. I agree about the LaTeX.

10. Jun 25, 2011

### spamiam

They're just leaving out some steps. Since $k \geq 1$, then $2 \leq 2^k$. By the inductive assumption, $2k \leq 2^k$. Putting these two facts together, what can you say about $2k+2$ and $2^k + 2^k$?

And Mentallic, try using itex rather than tex if you want to make in-line math environment.

11. Jun 25, 2011

### Mentallic

Yep that's right You may want to throw one more line of working in, to show without a doubt that $k+1\leq 2k$ just by algebraic manipulation and referring back to the "for all positive integers n" in the question.

Your book is saying that since $2k\leq 2^k$ then $2k+2\leq 2k+2k\leq 2^k+2^k$ by our inductive hypothesis. They just turn it back into what was needed to be proved, $2(k+1)\leq 2^{k+1}$

By the way, thanks for that spamiam. I thought itex was lost since I tried it at one point and it wasn't working.

12. Jun 25, 2011

### Dickfore

You need to use the fact that:
$$k \ge 1$$
$$k + k \ge k + 1$$
$$2 k \ge k + 1$$

13. Jun 25, 2011

### HallsofIvy

Do you realize that you haven't defined "S"?
I take it you mean S to be the set of all positive integers, n, such that $2n\le 2^n$ but you need to say that.

If S is as I said, no it doesn't. That's what you want to prove!

Which is why you can say, above, that kϵ implies k+1ϵ S.

$$2(k+1)= 2k+ 2\le 2^k+ 2$$.

What I would do is a separate induction, as a lemma, to prove that [itex]2^n+1\le 2^{n+1}[/tex]

14. Jun 25, 2011

### flyingpig

Why can't you use calculus to prove this

15. Jun 25, 2011

### Mentallic

You could, but a proof by induction is simpler and also it is somewhat implied which technique you should be using by the part "holds for all positive integers n". It was also posted in the precalculus section.