1
$\begingroup$

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}$

$\endgroup$
3
  • 1
    $\begingroup$ Where did you show that $2^{2k+1} \geq k+1$? $\endgroup$
    – Clement C.
    Oct 21 '17 at 4:15
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 21 '17 at 4:26
  • 1
    $\begingroup$ Alternative approach to the problem: $2^{n^2}=(2^n)^n\geq n^n\geq n!$. $\endgroup$
    – Arthur
    Oct 21 '17 at 4:56
1
$\begingroup$

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$$

$\endgroup$
6
  • $\begingroup$ I'm confused as to why it can not be taken as a given that this is the case though? $\endgroup$ Oct 21 '17 at 4:20
  • $\begingroup$ @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. $\endgroup$ Oct 21 '17 at 4:26
  • $\begingroup$ 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? $\endgroup$ Oct 21 '17 at 4:33
  • $\begingroup$ @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. $\endgroup$ Oct 21 '17 at 4:42
  • $\begingroup$ Alright, so it is just a matter of proving that and then I can say the inductive step is true or am I missing some intermediate step? $\endgroup$ Oct 21 '17 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.