Prove 2^n < (n+2)!; \forall n \ge 0 by Induction

[jonroberts74]

Homework Statement

prove by induction

2^n &lt; (n+2)!; \forall n \ge 0

P(0)

2^0 &lt; (0+2)! [easy]

P(k)

2^k&lt;(k+2)!
= 2^k &lt; (k+2)(k+1)k!

P(k+1)

2^{k+1} &lt; (k+1+2)!
= 2^k \cdot 2 &lt; (k+3)(k+2)(k+1)k!

its pretty clear that

2 &lt; k+3

how do I show that though

 

[micromass]

its pretty clear that

2 &lt; k+3

how do I show that though

I would personally just say it's obvious. But if you want, you can prove it by induction. It all depends on how you defined $<$ and what your axioms are.

 

[HallsofIvy]

I see you recognize that you cannot just write "2^{k+1}&lt;((k+1)+ 2)!" since that is what you want to find- you wrote it only to remind yourself what you want to arrive at.

Your "induction hypothesis" is that 2^k&lt; (k+ 2)!. Now write 2^{k+1}= 2(2^k)&lt; 2(k+2)!.

Now, use your "2< k+ 3" to get 2^{k+1}&lt; 2(k+2)!&lt; (k+2)!(k+ 3)= (k+3)!= (k+1+2)!.

To prove that 2< k+ 3, start from the fact that, since 0\le k, -1&lt; k and add 3 to both sides.

 

[jonroberts74]

I see you recognize that you cannot just write "2^{k+1}&lt;((k+1)+ 2)!" since that is what you want to find- you wrote it only to remind yourself what you want to arrive at.

Your "induction hypothesis" is that 2^k&lt; (k+ 2)!. Now write 2^{k+1}= 2(2^k)&lt; 2(k+2)!.

Now, use your "2< k+ 3" to get 2^{k+1}&lt; 2(k+2)!&lt; (k+2)!(k+ 3)= (k+3)!= (k+1+2)!.

To prove that 2< k+ 3, start from the fact that, since 0\le k, -1&lt; k and add 3 to both sides.

I am taking this

2^{k+1}= 2(2^k)&lt; 2(k+2)!

by hypothesis, adding the multiple 2 to each side doesn't change the inequality

then prove 2<k+3

and do this from the fact

0 \le k so -1<k ---> -1+3<k+3 = 2< K+3

then I can say 2(2^k)&lt; 2(k+2)! &lt; (k+2)!(k+3).