Homework Help: Induction Proof

Tags:
1. Oct 8, 2015

The Subject

1. The problem statement, all variables and given/known data

Show that the statement holds for all positive integers n

2n ≤ 2^n

2. Relevant equations

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

3. The attempt at a solution

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

kS,
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 ?

2. Oct 8, 2015

SammyS

Staff Emeritus
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)?"
You did not show this.
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.

3. Oct 8, 2015

Fredrik

Staff Emeritus
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)

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

Your goal here should be to show that for all k, if P(k) then P(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).

4. Oct 8, 2015

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$

5. Oct 8, 2015

The Subject

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

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

Last edited: Oct 8, 2015
6. Oct 8, 2015

Fredrik

Staff Emeritus
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).

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.

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

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.

Last edited: Oct 8, 2015
7. Oct 8, 2015

RUber

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

8. Oct 8, 2015

The Subject

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

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

9. Oct 8, 2015

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$

10. Oct 8, 2015

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

11. Oct 8, 2015

SammyS

Staff Emeritus
Yes.

12. Oct 8, 2015

Fredrik

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