# Principle of Induction

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!

## Answers and Replies

Related Precalculus Mathematics Homework Help News on Phys.org
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
Mentor
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 2k + 1 = 2 * 2k >= 2 * (k + 1) = 2k + 2

How does that last expression compare with k + 2? (I.e., (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.

So you have 2k + 1 = 2 * 2k >= 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...

Last edited:
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$$
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...