Proving $(n+1)!>2^{n+3}$ for all $n\geq 5$ by induction

Question

I am stuck writing the body a PMI I have been working on for quite some time.

Theorem: $∀n∈N ≥ X$, $(n+1)!>2^{n+3}$

I will first verify that the hypothesis is true for at least one value of $n∈N$.

Consider $n=3$: (not valid) $$(3+1)!>2^{3+3} \implies 4!>2^{6} \implies 24>64$$

Consider $n=4$: (not valid) $$(4+1)!>2^{4+3} \implies 5!>2^{7} \implies 120>128$$

Consider $n=5$: (valid) $$(5+1)!>2^{5+3} \implies 6!>2^{8} \implies 720>256$$

Consider $n=6$: (valid) $$(6+1)!>2^{6+3} \implies 7!>2^{9} \implies 5040>512$$

So clearly $X$ is $5$.

For the inductive assumption, we will assume the hypothesis holes from $n=5$ up to some arbitrary values $k$: $(k+1)!>2^{k+3}$

This is where I am lost. Originally I had written:

Now I will prove true for $k+1$ showing that: $(k+2)!>2^{k+4}$. Consider the $k+1$ term:

$$(k+2)(k+1)k! = (k+2)(k+1)2^k = (k+2)(k+1)2^k = (2)(2)(2^k) = (4)(2^k) = 2^{k+4}$$ by the inductive assumption since $k>5$ so $k+1>2$ and $k+2>2$ but I know this isn't correct.

I know the proof should look something like this, but I have no idea why:

$$(k+2)(k+1)!>(k+2)(2^{k+3})>2(2^{k+3})=2^{k+4}$$

Answer 1

For $n\geq 5$, let $S(n)$ denote the statement $$ S(n) : (n+1)! > 2^{n+3}. $$

Base step $(n=5)$: $S(5)$ says $6!>2^8$, and this is true since $720>256$.

Inductive step: Fix some $k\geq 5$ and suppose that $$ S(k) : (k+1)!>2^{k+3} $$ is true. We must now prove that $S(k+1)$ follows where $$ S(k+1) : (k+2)! > 2^{k+4}. $$ Starting with the left-hand side of $S(k+1)$, \begin{align} (k+2)! &= (k+1)!\cdot(k+2)\tag{by definition}\\[0.5em] &> 2^{k+3}(k+2)\tag{by $S(k)$}\\[0.5em] &\geq 2^{k+3}\cdot 7\tag{since $k\geq 5$}\\[0.5em] &> 2^{k+3}\cdot 2\\[0.5em] &= 2^{k+4}, \end{align} we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k)\to S(k+1)$, completing the inductive step.

Thus, by mathematical induction, for all $n\geq 5$, the statement $S(n)$ is true. $\blacksquare$

Answer 2

I'm not sure when you say "I have no idea why" what it is you are unsure about. That is precisely the right proof. The first inequality holds by the inductive hypothesis. The second holds because for $k\ge 5$ certainly $k+2>2$.

Answer 3

Your first two steps are correct. You have established that:$$(n+1)!\gt2^{n+3}$$is first true when $n=5$. You then correctly assumed that it holds for some $n=k\ge5$, giving you:$$(k+1)!\gt2^{k+3}\tag{1}$$And, finally you also proceeded in the right direction by then saying that you now need to prove that this implies it is also true for $n=k+1$. If we look at $n=k+1$ we get:$$(k+2)!=(k+2)(k+1)!$$Now use the result from (1) to deduce that:$$(k+2)!\gt(k+2)2^{k+3}$$You can then show that:$$(k+2)2^{k+3}=k.2^{k+3}+2.2^{k+3}=k.2^{k+3}+2^{k+4}\gt2^{k+4}$$

Answer 4

First, show that this is true for $n=5$:

$(5+1)!>2^{5+3}$

Second, assume that this is true for $n$:

$(n+1)!>2^{n+3}$

Third, prove that this is true for $n+1$:

$(n+2)!=\color{red}{(n+1)!}\cdot\color{blue}{(n+2)}>\color{red}{2^{n+3}}\cdot\color{blue}{(n+2)}>\color{red}{2^{n+3}}\cdot\color{blue}{2}=2^{n+4}$

---

Please note that the assumption is used only in the part marked red.

Answer 5

Hint $\,\ \dfrac{(n\!+\!1)!}{2^{n+3}}\, =\, \dfrac{n\!+\!1}2\ \dfrac{n}2\,\cdots\, \dfrac{7}2\ \dfrac{6!}{2^8}\ $ is a product of terms $> 1$ so, by induction, is $> 1$

Remark $\ $ The proof essentially uses telescopy to rewrite the expression as a product. As above, where we reduced the induction to the trivial induction that a product of terms $> 1$ stays $> 1$, telescopy often greatly simplifies such inductive proofs. See here for many further examples.