Prove By Mathematical Induction (factorial-to-the-fourth vs power of two)

Question

Prove $(n!)^{4}\le2^{n(n+1)}$ for $n = 0, 1, 2, 3,...$

Base Step: $(0!)^{4} = 1 \le 2^{0(0+1)} = 1$

IH: Assume that $(k!)^{4} \le 2^{k(k+1)}$ for some $k\in\mathbb N$.

Induction Step: Show $(k+1!)^{4} \le 2^{k+1((k+1)+1)}$

Proof: $(k+1!)^{4} = (k+1)^{4}*(k!)^{4}$ By the definition of factorial. $$\begin{align*} (k+1)^{4}*(k!)^{4} &\le (k+1)^{4}*2^{k(k+1)}\\ &\le (k+1)^{4}*2^{(k+1)((k+1)+1)} \end{align*}$$ by the IH.

That is as far as I have been able to get at this point...Please Help! Any suggestions or comments are greatly appreciated.

Answer 1

That last $\leq$ is leading you astray. Here's the last correct step: $$((k+1)!)^4 = (k+1)^4 (k!)^4 \leq (k+1)^4 2^{k(k+1)}.$$ Your goal is to show that $$(k+1)^4 2^{k(k+1)} \leq 2^{(k+1)((k+1)+1)}.$$ Try dividing both sides by a common factor andd see what's left...

Answer 2

You are doing well up to $(k+1)^4*(k!)^4 \le (k+1)^4*2^{k(k+1)}$ That is the proper use of the induction hypothesis. Now you need to argue $(k+1)^4 \le \frac {2^{(k+1)(k+2)}}{2^{k(k+1)}}=2^{(k+1)(k+2)-k(k+1)}=2^{2(k+1)}$

Answer 3

You might have to do a secondary proof by induction to prove this. What you want to show is the following (I hope my LaTeX renders properly): $((n+1)!)^4 \leq 2^{(n+1)(n+2)}$. We know from the inductive hypothesis that $(n!)^4 \le 2^{n(n+1)}$. Multiplying on both sides by $(n+1)^4$, we have $((n+1)!)^4 \leq (n+1)^4 2^{n(n+1)}$. For the proof to be complete, you only need to show that $(n+1)^4 2^{n(n+1)} \leq 2^{(n+1)(n+2)}$. This can be done easily with a secondary proof by induction after doing a little bit of rearranging of terms in the inequality.