\problemdata     
{induction-2}           
{induction, proofs, asymptotics}              
{Velleman 6.3.7b and  6.3.7c}              
{S01-PS2} 		
{S01 Karger}        	

\begin{problem} 

An important tool in the analysis of algorithms is to estimate the
growth rate of complex mathematical functions using other, hopefully
simpler, functions. A function central to probability theory is the
\emph{factorial}, defined recursively as
\begin{displaymath}
  n! = \begin{cases}
    n \times (n-1)! & \mbox{if $n > 0$,} \\
    1 & \mbox{otherwise,}
  \end{cases}
\end{displaymath}
for all $n \in \naturals$. Your task in this problem is to prove that
the factorial is sandwiched between $2^{2n}$ and $2^{n^2}$ for large
enough~$n$. More precisely, prove by induction that
\begin{problemparts}
\ppart For all $n \in \naturals$ such that $n \geq 9$, $n! \geq
2^{2n}$.
\solution{

  Let $P(n)$ be the statement ``$n! \geq 2^{2n}$''. $P(9)$~is true since
  $9! = 362880 \geq 2^{18} = 262144$. Now assume that $P(n)$~is true for
  some $n \geq 9$. Then,
  \begin{displaymath}
    2^{2(n+1)} = 4\cdot2^{2n} \leq 4 n! \leq (n+1) n! = (n+1)!
  \end{displaymath}
  where the first inequality follows from the induction hypothesis and
  the second follows since $n \geq 9$.}

\ppart For all $n \in \naturals$, $n! \leq 2^{n^2}$.

 \solution{
   Let $P(n)$ be the statement ``$n! \leq 2^{n^2}$''. $P(0)$~is true since
   \begin{displaymath}
     0! = 1 \leq 2^{0^2} = 2^{0} = 1.
   \end{displaymath}
   Now assume that $P(n)$ is true. Then
   \begin{displaymath}
     2^{(n+1)^2} = 2^{n^2+2n+1} \geq 2^{2n+1}n!.
   \end{displaymath}
   where the inequality follows by the induction hypothesis. In order
   to complete the proof, we must prove that $2^{2n+1} \geq n+1$ for
   all $n \in \naturals$. We do this by induction.
  
   Let $Q(n)$ be the statement ``$2^{2n+1} \geq n+1$''. $Q(0)$~is true
   since $2^{2\times0+1} = 2^1 = 2 \geq 0+1 = 1$. Now assume that
   $Q(n)$~is true for some $n \in \naturals$. Then
   \begin{displaymath}
     2^{2(n+1) + 1} = 2^{2n + 1 + 2} = 4 \cdot 2^{2n+1} \geq 4(n+1) \geq n+2
   \end{displaymath}
   where the first inequality follows from the induction hypothesis and
   the second inequality holds for any~$n \in \naturals$. Thus, $Q(n)$
   implies $Q(n+1)$.

   To wrap things up,
   \begin{displaymath}
     2^{(n+1)^2} = 2^{n^2+2n+1} \geq 2^{2n+1}n! \geq (n+1)n! = (n+1)!
   \end{displaymath}
   thus $P(n)$ implies $P(n+1)$.
 }
\end{problemparts}

\end{problem}
