Proof by mathematical induction that $2^n < (n+2)!$ for all $n\ge 0$

Question

I have been trying to get this.. For hours.

Prove by M.I. that $2^n < (n+2)!$ for $n\ge0$

Here is what I am doing:

Base case checks out at $n=0$

Make assumption for: $n=k$

Want to prove: $2^{k+1} < (k+3)!$

I am guessing that since $k\ge 0$, if I just assume $k = 0$ and the inequality holds, then I am done.

But I'm not sure. If I do that then I get:

PROOF:

$2^k < (k+2)!$ , by assumption

$2^k \times 2 < 2(k+2)!$

$2^{k+1} < (2k+4)!$ but $k\ge 0$, and at Zero

$2< 4!$ done?

Answer 1

You must use $2^n < (n+2)!\Rightarrow 2^{n+1} = 2\cdot 2^n < 2\cdot (n+2)!< (n+3)\cdot (n+2)!=(n+3)!$

Answer 2

Your reasoning is dodgy. You would need to demonstrate that "the property gets more true as $k$ increases, so the worst case is when $k=0$, which we now prove". But if you're starting out, that's not a good line of reasoning to follow, and it can get you into bad habits.

If $2^k < (k+2)!$, how can we transform the inequality to get $2^{k+1}$ on the left-hand side?

Answer 3

Here is a combinatorial argument that $2^n\leq (n+1)!$ for all nonnegative integers $n$. Consider a sequence $\left(a_0,a_1,a_2,\ldots,a_n\right)$ where $\left\{a_0,a_1,a_2,\ldots,a_n\right\}=\{0,1,2,\ldots,n\}$. There are $(n+1)!$ such sequences. If $\mathbf{a}:=\left(a_0,a_1,a_2,\ldots,a_n\right)$ is such a sequence, we say that $\mathbf{a}$ is extraordinary if, for every $i=1,2,\ldots,n$, either $$\left\{a_{k-i},a_{k-i+1},\ldots,a_{k-1}\right\}=\left\{0,1,2,\ldots,i-1\right\}\text{ or }\left\{a_{k+1},a_{k+2},\ldots,a_{k+i}\right\}=\left\{0,1,2,\ldots,i-1\right\}\,,$$ given that $a_k=i$. We shall show that there are $2^n$ extraordinary sequences. This will prove that $2^n\leq (n+1)!$, which then implies that $2^n<(n+2)!$.

Start with a sequence of length $1$ consisting of $0$ alone. For each $i=1,2,\ldots,n$, we can assign $i$ either on the left (L) or on the right (R) of all the previously assigned locations for $0,1,2,\ldots,i-1$. Hence, extraordinary sequences are in a one-to-one correspondence with a string of length $n$ with letters L and R. For examples, if $n=4$, then LLLL corresponds to $(4,3,2,1,0)$, LRLR corresponds to $(3,1,0,2,4)$, and RLRR corresponds to $(2,0,1,3,4)$. This proves that the number of extraordinary sequences is $2^n$.