# Prove that 2n ≤ 2^n by induction.

• -Dragoon-
In summary, the homework statement states that 2n ≤ 2^n holds for all positive integers n. However, to prove this formally, the author needs to show that k+1 holds for all positive integers n.
-Dragoon-

## Homework Statement

Prove and show that 2n ≤ 2^n holds for all positive integers n.

n = 1
n = k
n = k + 1

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

Retribution said:
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?

spamiam said:
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?

Retribution said:
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.

Mentallic said:
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?

Retribution said:
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.

Retribution said:
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...

spamiam said:
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?

Mentallic said:
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.

Retribution said:
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.

Retribution said:
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 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.

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

Retribution said:

## Homework Statement

Prove and show that 2n ≤ 2^n holds for all positive integers n.

n = 1
n = k
n = k + 1

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

Why can't you use calculus to prove this

flyingpig said:
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.

## What is the purpose of using induction to prove this statement?

The purpose of using induction is to show that a statement is true for all natural numbers by proving it for a base case and then showing that if it holds for a particular value, it also holds for the next value. This allows us to extend the truth of the statement to all natural numbers.

## What is the base case for this proof?

The base case for this proof is n = 1. When n = 1, 2n = 2 and 2^n = 2, so the statement 2n ≤ 2^n is true for n = 1.

## What is the inductive hypothesis for this proof?

The inductive hypothesis for this proof is assuming that the statement is true for a particular value of n, we need to prove that it is also true for the next value, n+1.

## What is the inductive step for this proof?

The inductive step for this proof involves showing that if the statement is true for n, it is also true for n+1. This can be done by substituting n+1 into the statement and using the inductive hypothesis to simplify the expression.

## What is the conclusion of this proof?

The conclusion of this proof is that the statement 2n ≤ 2^n is true for all natural numbers n. This is because we have shown that it is true for the base case and that if it is true for a particular value of n, it is also true for the next value, n+1. Therefore, by induction, the statement is true for all natural numbers.

• Precalculus Mathematics Homework Help
Replies
10
Views
512
• Precalculus Mathematics Homework Help
Replies
4
Views
126
• Precalculus Mathematics Homework Help
Replies
11
Views
349
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
19
Views
566
• Precalculus Mathematics Homework Help
Replies
9
Views
403
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
11
Views
534
• Precalculus Mathematics Homework Help
Replies
10
Views
964
• Precalculus Mathematics Homework Help
Replies
1
Views
1K