# Induction prove $\begin{equation} 2^{n^2} \geq n! \end{equation}$ for a nonnegative integer

Hi I submitted this as a graded assignment and received a poor grade. Could someone help me see what was wrong with my proof.

Let n be a nonnegative integer. Show that $\begin{equation}2^{n^2} \geq n!\end{equation}$

Proof

(i) Base Case

For n = 0 We have $\begin{equation}2^{0^2} \geq 0! \end{equation}$ Which Yields, $\begin{equation}1 \geq 1 \end{equation}$ Thus the base case holds.

(ii) Inductive Hypothesis:

Assume for some $\begin{equation} k\in\mathbb{Z}, k\geq 0 \text{ that }, 2^{k^2} \geq k!\end{equation}$ then look at $\begin{equation} k+1 \end{equation}$

\begin{align*} 2^{(k+1)^2} &= 2^{k^2 +2k+1}\\ &= 2^{k^2} \cdot 2^{2k} \cdot 2\\ &\geq k! \cdot 2^{2k} \cdot 2 \text{ via inductive hypothesis}\\ \end{align*}

We now take $\begin{equation} k!\cdot 2^{2k} \cdot 2 \end{equation}$ and relate it to $\begin{equation} (k + 1)! \end{equation}$

\begin{align*} k! \cdot 2^{2k} \cdot 2&\geq (k+1)!\\ k! \cdot 2^{2k} \cdot 2&\geq (k+1) \cdot k!\\ 2^{2k+1}&\geq (k+1)\\ \end{align*}

Thus the statement holds for $k+1$ Therefore by the generalized principle of mathematical induction,

$\begin{equation}2^{n^2} \geq n!\end{equation}$ for $\begin{equation} n\in\mathbb{Z}, n \geq 0 \end{equation}$

• Where did you show that $2^{2k+1} \geq k+1$? Oct 21 '17 at 4:15
• If the main point of your question is asking about correctness of your proof and possible ways to improve it (as opposed to asking for any proof of this claim) you should make this clear by using (proof-verification) tag. Oct 21 '17 at 4:26
• Alternative approach to the problem: $2^{n^2}=(2^n)^n\geq n^n\geq n!$. Oct 21 '17 at 4:56

You need to prove that $2^{2k+1}\geq k+1$ and you did not do it.
For example: $$2^{2k+1}=(1+1)^{2k+1}\geq1+(2k+1)\cdot1>k+1$$
• @Jordan Nesbitt Because you need to use the induction. If you still did not prove that $2^{2k+1}> k+1$ is true then you can not do it. Oct 21 '17 at 4:26
• The reason I'm confused is that when I look at the statement $\begin{equation} 2^{2k+1} \geq k+1 \end{equation}$ it seems clear that this must be the case and while what you have done does provide even more evidence that his must be the case, I don't understand why it is needed. So i guess my question now is why is it not clear that $\begin{equation} 2^{2k+1} \geq k+1 \end{equation}$ is true? Oct 21 '17 at 4:33
• @Jordan Nesbitt It's clear and easy, but you need to prove it because from here you'll get $2^{(k+1)^2}>(k+1)!$ and you'll can end the proof. Oct 21 '17 at 4:42