Principle of Induction

  • Thread starter roam
  • Start date
  • #1
1,266
11
1. Homework Statement

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



Homework Equations




3. The Attempt at a Solution

Let the proposition P(n) be "[tex]2^n \geq n+1[/tex]"

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

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

[tex]2^{k+1} \geq (k+1)+1[/tex]

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

Thanks!
 

Answers and Replies

  • #2
1,631
4
well, your induction hypothesis is:

[tex]2^k\geq k+1[/tex]

now

[tex]2^{k+1}=2*2^k\geq 2(k+1)=2k+2>(k+1)+1[/tex]
 
  • #3
33,712
5,412
1. Homework Statement

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


2. Homework Equations


3. The Attempt at a Solution

Let the proposition P(n) be "[tex]2^n \geq n+1[/tex]"

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

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

[tex]2^{k+1} \geq (k+1)+1[/tex]
Omit the line above, since that's where you want to end up. Just say:
suppose P(k) is true, i.e., that [tex]2^k \geq k+1[/tex]
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 [tex]2.2^{k} \geq 2.(k+1)[/tex]. 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)
 
  • #4
1,266
11
Omit the line above, since that's where you want to end up. Just say:
suppose P(k) is true, i.e., that [tex]2^k \geq k+1[/tex]
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 [tex]2^{k+1} = 2.2^k \geq 2.(k+1)[/tex]

[tex]2(k+1) = (k+1)+(k+1) \geq (k+1)+1[/tex]

I'm a little confused, how should we make the conclusion?
Since (k+1)+1 is supposed to be less than or equal to [tex]2^{k+1} (= 2.2^k)[/tex], and now we know it is less than or equal to 2.(k+1). Therefore...
 
Last edited:
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,833
956
So, it is [tex]2^{k+1} = 2.2^k \geq 2.(k+1)[/tex]

[tex]2(k+1) = (k+1)+(k+1) \geq (k+1)+1[/tex]
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 [tex]2^{k+1} (= 2.2^k)[/tex], and now we know it is less than or equal to 2.(k+1). Therefore...
 

Related Threads on Principle of Induction

  • Last Post
Replies
5
Views
4K
Replies
2
Views
2K
Replies
16
Views
3K
Replies
51
Views
4K
  • Last Post
Replies
13
Views
994
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
4K
Top