Prove that 2n ≤ 2^n by induction.

[-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?

[spamiam]

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?


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?

[-Dragoon-]

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?

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

[Mentallic]

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

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.

[-Dragoon-]

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.

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

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

[spamiam]

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

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.

[Mentallic]

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

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

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

[-Dragoon-]

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.

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?

[-Dragoon-]

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

[spamiam]

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?

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.

[Mentallic]

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.

Yep that's right :smile: 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.

[Dickfore]

You need to use the fact that:

k \ge 1


k + k \ge k + 1


2 k \ge k + 1

[HallsofIvy]

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

Now to see if k ϵ S:
2 (k) ≤ 2^k
But, k ϵ S implies k + 1 ϵ S:
If S is as I said, no it doesn't. That's what you want to prove!

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?
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]

[flyingpig]

Why can't you use calculus to prove this

[Mentallic]

Why can't you use calculus to prove this

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.