Proving 2n ≤ 2^n for All Positive Integers n

[The Subject]

Homework Statement

[/B]
Show that the statement holds for all positive integers n

2n ≤ 2^n

Homework Equations

Axiom of induction:
1 ∈ S and
k ∈ S ⇒ k + 1 ∈ S

The Attempt at a Solution

Let S be set of integers
2(1) ≤ 2^1, so S contains 1

k ∈ S,
2k ≤ 2^k

I want to show k + 1 ∈ S,
2k + 2(k+1) ≤ 2^k * 2^(k+1)

The left side seems to make sense since
=2k+2k+2
=4k+2
=2(k+1)

I showed k + 1 ∈ S

The right side i get
=2^(k(k+1))

Does this show k + 1 ∈ S ? To me 2k*2(k+1) makes sense because the next value of k can be calculated ?

 

[SammyS]

Homework Statement

[/B]
Show that the statement holds for all positive integers n

2n ≤ 2^n

Homework Equations

Axiom of induction:
1 ∈ S and
k ∈ S ⇒ k + 1 ∈ S

The Attempt at a Solution

Let S be set of integers
2(1) ≤ 2^1, so S contains 1

k ∈ S,
2k ≤ 2^k

I want to show k + 1 ∈ S,
2k + 2(k+1) ≤ 2^k * 2^(k+1)

The left side seems to make sense since
=2k+2k+2
=4k+2
=2(k+1)

Actually the left side doesn't make sense.

You need the left side to be 2(k+1), but you have 4k + 2, which is 2(2k+1).

To correct that, notice that 2(k+1) = 2k + 2. Then ask yourself, "what needs to be added to 2k to get 2(k+1)?"

I showed k + 1 ∈ S

You did not show this.

The right side i get
=2^(k(k+1))

Does this show k + 1 ∈ S ? To me 2k*2(k+1) makes sense because the next value of k can be calculated ?

I suspect that your statement of the Axiom of Induction is missing some details, particularly as concerns the description of the set S, including the nature of its elements.

 

[Fredrik]

For each n, Let P(n) denote the statement ##2n\leq 2^n##. You want to prove the statement "for all n, P(n)". This is equivalent to proving all of the infinitely many statements P(1), P(2), P(3),... But if you try to prove them one at a time, you will never be finished. So you use induction. The idea is that you can prove all of these statements by proving only the following two statements:

P(1)
For all k, if P(k) then P(k+1)

Let S be set of integers
2(1) ≤ 2^1, so S contains 1

Here you have made it sound like the goal is to prove that 1 is an integer. Your goal at this point should be to prove the statement P(1).

I want to show k + 1 ∈ S,

Your goal here should be to show that for all k, if P(k) then P(k+1).

2k + 2(k+1) ≤ 2^k * 2^(k+1)

I'm not sure what you're doing here. At this point, k is an arbitrary integer, and you're working under the assumption that P(k) holds. You want to prove P(k+1). So you should start by rewriting some part of the statement P(k+1) in a way that makes it easy to use the assumption P(k).

 

[RUber]

1 is in S.
Assume k is in S, i.e.
##2k\leq 2^k ##
Manipulate 2(k+1) and 2^(k+1) to put them in terms of 2k and 2^k.
Use something that looks like
If ##A \leq B## and ##C \leq D ## then ## A+C\leq B+D##
Knowing that k is at least 1 will help you draw your final conclusion.

 

[The Subject]

For each n, Let P(n) denote the statement ##2n\leq 2^n##. You want to prove the statement "for all n, P(n)". This is equivalent to proving all of the infinitely many statements P(1), P(2), P(3),...

This makes it easier to understand using P(n)

P(1) works because 2(1) ≤ 2^(1) so,

for all k, P(k) ⇒ P(k + 1)
2(k) ≤ 2^(k) ⇒ 2(k+1) ≤ 2^(k+1)

I'm stuck at this point, I tried
2(2(k+1)) ≤ 2^(2^(k+1)) ... I'm pretty sure this is incorrect

Manipulate 2(k+1) and 2^(k+1) to put them in terms of 2k and 2^k.
Use something that looks like
If A≤BA \leq B and C≤DC \leq D then A+C≤B+D A+C\leq B+D

wouldn't I get the same results as I did before?
2(k+1)+2k ≤ 2^(k+1) + 2^k

 

[Fredrik]

This makes it easier to understand using P(n)

P(1) works because 2(1) ≤ 2^(1)

That's statement P(1) alright, but you should also explain how you know that it's a true statement. (Yes, it's pretty trivial, but you're doing this problem to practice your proof writing skills).

for all k, P(k) ⇒ P(k + 1)
2(k) ≤ 2^(k) ⇒ 2(k+1) ≤ 2^(k+1)

Right, that's what you want to prove next. So you assume that the inequality on the left holds, and use it to prove that the inequality on the right holds too.

I'm stuck at this point

Is there a way to rewrite ##2(k+1)## so that the symbols 2 and k appear right next to each other? That's all you have to do to be able to use the assumption ##2k\leq 2^k##.

wouldn't I get the same results as I did before?
2(k+1)+2k ≤ 2^(k+1) + 2^k

Did you just add P(k) to P(k+1)? That would be an attempt that uses P(k+1) as an assumption. You can't use the statement that you're trying to prove.

 

[RUber]

P(1) works because 2(1) ≤ 2^(1)≤ so,

for all k, P(k) ⇒ P(k + 1)
2(k) ≤ 2^(k) ⇒ 2(k+1) ≤ 2^(k+1)

I'm stuck at this point, I tried
2(2(k+1)) ≤ 2^(2^(k+1)) ... I'm pretty sure this is incorrect

It seems like perhaps you don't understand the notation.
k doesn't change. Initially it could be 1...since you have already shown this.
##2(1) \leq 2^1 ## is true. Does this imply that k+1=1+1 satisfies the relation?
## 2(2) \leq 2^2##? So far so good. So 2 satisfies the relation, so k might be 2...what about 2+1?
##2(2+1) \leq 2^{2+1}##?
So for any k, you should be able to show that ##2(k+1) \leq 2^{k+1}## using basic algebra and the assumption that ##2k \leq 2^{k}##.

 

[The Subject]

Is there a way to rewrite 2(k+1)2(k+1) so that the symbols 2 and k appear right next to each other? That's all you have to do to be able to use the assumption 2k≤2k2k\leq 2^k.

2k+2 ? Is this all I have to do?

How about the other side of the inequality.
2^k?

 

[RUber]

Think about what you are trying to do...
You are saying "I know that ##2k \leq 2^k##, what can I say about ##2(k+1)## and ##2^{k+1}##?"
All you have to build this proof off of is ##2k \leq 2^k##, k>1, and algebra.
That is all you need.

*hint* ##a^{b+c} = a^b a^c##

 

[The Subject]

So you're saying that
I have work with what i know, 2k ≤ 2^k

do stuff with algebra, when k>1

then it will show that 2(k+1) ≤ 2^(k+1) ?

 

[SammyS]

So you're saying that
I have work with what i know, 2k ≤ 2^k

do stuff with algebra, when k>1

then it will show that 2(k+1) ≤ 2^(k+1) ?

Yes.

 

[Fredrik]

2k+2 ? Is this all I have to do?

Yes, the rewrite ##2(k+1)=2k+2## is a good way to make it extremely easy to use the assumption that ##2k\leq 2^k##. The next step is to actually use that assumption.