Sunday, 3 August 2014

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

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...