Using Induction to Prove 2^n >= n+1 for Natural Numbers

[roam]

1. Homework Statement

Prove that for each n \in N (aka natural numbers), 2^n \geq n+1

Homework Equations

3. The Attempt at a Solution

Let the proposition P(n) be "2^n \geq n+1"

Clearly P(n) is true for n=1, 2^1 \geq 1+1.

We suppose P(k) is true, i.e., supposing that 2^k \geq k+1 is true, then,

2^{k+1} \geq (k+1)+1

I think it can then be rewritten as 2.2^{k} \geq 2.(k+1). Does anyone know the next step? I'm not sure what to do from here...

Thanks!

 

[sutupidmath]

well, your induction hypothesis is:

2^k\geq k+1

now

2^{k+1}=2*2^k\geq 2(k+1)=2k+2>(k+1)+1

 

[Mark44]

1. Homework Statement

Prove that for each n \in N (aka natural numbers), 2^n \geq n+1


2. Homework Equations


3. The Attempt at a Solution

Let the proposition P(n) be "2^n \geq n+1"

Clearly P(n) is true for n=1, 2^1 \geq 1+1.

We suppose P(k) is true, i.e., supposing that 2^k \geq k+1 is true, then,

2^{k+1} \geq (k+1)+1

Omit the line above, since that's where you want to end up. Just say:
suppose P(k) is true, i.e., that 2^k \geq k+1
Keep it in the back of your mind where you want to go, but work toward that goal.

I think it can then be rewritten as 2.2^{k} \geq 2.(k+1). Does anyone know the next step? I'm not sure what to do from here...

So you have 2^{k + 1} = 2 * 2^k >= 2 * (k + 1) = 2k + 2

How does that last expression compare with k + 2? (I.e., (k + 1) + 1)

 

[roam]

Omit the line above, since that's where you want to end up. Just say:
suppose P(k) is true, i.e., that 2^k \geq k+1
Keep it in the back of your mind where you want to go, but work toward that goal.

So you have 2^{k + 1} = 2 * 2^k >= 2 * (k + 1) = 2k + 2

How does that last expression compare with k + 2? (I.e., (k + 1) + 1)

So, it is 2^{k+1} = 2.2^k \geq 2.(k+1)

2(k+1) = (k+1)+(k+1) \geq (k+1)+1

I'm a little confused, how should we make the conclusion?
Since (k+1)+1 is supposed to be less than or equal to 2^{k+1} (= 2.2^k), and now we know it is less than or equal to 2.(k+1). Therefore...

 

[HallsofIvy]

So, it is 2^{k+1} = 2.2^k \geq 2.(k+1)

2(k+1) = (k+1)+(k+1) \geq (k+1)+1

No, "(k+1)+(k+1)" is not the point. As Mark44 said before, 2(k+1)= 2k+ 2. Now, since k is a positive integer, it is certainly true that 2k> k (you might want to do another induction to prove that formally) so 2k+ 2> k+ 2= (k+1)+ 1.

I'm a little confused, how should we make the conclusion?
Since (k+1)+1 is supposed to be less than or equal to 2^{k+1} (= 2.2^k), and now we know it is less than or equal to 2.(k+1). Therefore...