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

[jonroberts74]

Homework Statement

prove by induction

$$2^n < (n+2)!; \forall n \ge 0$$

P(0)

$$2^0 < (0+2)!$$ [easy]

P(k)

$$2^k<(k+2)!$$
$$= 2^k < (k+2)(k+1)k!$$

P(k+1)

$$2^{k+1} < (k+1+2)!$$
$$= 2^k \cdot 2 < (k+3)(k+2)(k+1)k!$$

its pretty clear that

$$2 < k+3$$

how do I show that though

 

[micromass]

its pretty clear that

$$2 < 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}<((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< (k+ 2)!$. Now write $2^{k+1}= 2(2^k)< 2(k+2)!$.

Now, use your "2< k+ 3" to get $2^{k+1}< 2(k+2)!< (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< k$ and add 3 to both sides.

 

[jonroberts74]

I see you recognize that you cannot just write "$2^{k+1}<((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< (k+ 2)!$. Now write $2^{k+1}= 2(2^k)< 2(k+2)!$.

Now, use your "2< k+ 3" to get $$2^{k+1}< 2(k+2)!< (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< k$ and add 3 to both sides.

I am taking this

$2^{k+1}= 2(2^k)< 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)< 2(k+2)! < (k+2)!(k+3)$.