\documentclass{article}
\usepackage{ch1/techexpl}
\input{ch1/control}

\begin{document}

\thispagestyle{empty}

\begin{center}
\vspace{1.0in}
\Large\bf
Data Structures and Algorithms ---   CSCI 230 \\
Chapter 1 --- Review Solutions
\end{center}

\begin{enumerate}
\item Give an inductive proof showing that for all integers $n \geq 5$,
$4 n + 4 < n^2$.

\textbf{SOLUTION:} \\
  {\bf Basis Case:} When $n=5$, $4 n + 4 = 24$ and $n^2 = 25$.
  Since $24 < 25$, the basis case is proved.

  {\bf Induction Step:}  For $n > 5$, if $4 k + 4 < k^2$ for $5 \leq k
  <n$ then
  \begin{eqnarray*}
   4 n + 4 &=& [ 4(n-1) + 4 ] + 4 \\
   &<& (n-1)^2 + 4 \qquad \ldots \mbox{ by the Inductive Hypothesis } \\
   &=& n^2 - 2 n + 5 \\
   &<& n^2  \qquad \ldots \mbox{since $-2n + 5 < 0$ if $n>5$} \;
  \end{eqnarray*}
\bigskip

\item  Give an inductive proof showing that for
all positive integers $n$,
\[
\sum_{i=1}^n \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}.
\]
\textbf{SOLUTION:} \\

{\bf Basis Case:} $n=1$

The left hand side is
\[ \sum_{i=1}^1 \frac{1}{(2i-1)(2i+1)} = \frac{1}{1 \cdot 3} =
  \frac{1}{3}. \]
The right hand side is
 \[ \frac{1}{2\cdot 1+1} = \frac{1}{3}. \]
Since these are equal, the basis case is established.

\bigskip

{\bf Induction Step:} For $n>2$, if  $\sum_{i=1}^k
  \frac{1}{(2i-1)(2i+1)} = \frac{k}{2k+1}$ for $1\leq k<n$ then
\begin{eqnarray*}
 \sum_{i=1}^{n} \frac{1}{(2i-1)(2i+1)} &=&
  \sum_{i=1}^{n-1} \frac{1}{(2i-1)(2i+1)} + \frac{1}{(2n-1)(2n+1)} \\
&=&   \frac{(n-1)}{2n-1} + \frac{1}{(2n-1)(2n+1)}
      \qquad \ldots \; \mbox{by the inductive hypothesis} \\
&=& \frac{1}{2n-1} \left[ \frac{(n-1) (2n+1)}{2n+1} + \frac{1}{2n+1}
                   \right] \\
&=& \frac{1}{2n-1} \; \frac{ 2n^2 -n }{2n +1} \\
&=& \frac{1}{2n-1} \; \frac{ (2n-1) n }{ 2n+1} \\
&=& \frac{n}{2n+1}. \;
\end{eqnarray*}
\bigskip


\item Give an inductive proof showing that for
all $n \geq 1$,
\[
\sum_{i=1}^n i(i!) = (n+1)! - 1
\]

\textbf{SOLUTION:} \\
\textbf{Basis Case:}  When $n=1$, $\sum_{i=1}^n i(i!) = 1(1!) = 1$.
Substituting $n=1$ in $(n+1)! - 1$ yields $2!-1=1$.  Since these are
equal the basis case is proved.

\textbf{Induction Step:} For $n\geq 2$, if $\sum_{i=1}^k i(i!) =
(k+1)! - 1$, for $1 \leq k < n$, then
\begin{eqnarray*}
\sum_{i=1}^n i(i!) &=& \sum_{i=1}^{n-1} i(i!) + n(n!) \\
        &=& ( (n-1)+1 )! - 1 +  n(n!) 
                \qquad \text{by hypothesis, with $k=n-1$} \\
        &=& n! - 1 + n (n!) \\
        &=& (1+n) (n!) - 1 \\
        &=& (n+1)! - 1
\end{eqnarray*}
\bigskip

\item Evaluate the following summations.

\begin{enumerate}
  \item $\displaystyle \sum_{i=0}^{100} (-1)^i$

\textbf{SOLUTION:}\\
Writing this out explicitly yields:
\begin{eqnarray*}
\sum_{i=0}^{100} (-1)^i &=& (-1)^0 + (-1)^1 + (-1)^2 + (-1)^3 + \ldots + (-1)^{100} \\
 &=& 1 +  (-1) + 1 + (-1) + \ldots + 1 + (-1) + 1 \\
 &=& (1 + (-1) + (1 + (-1)) + \ldots + (1 + (-1)) + 1 \\
 &=& 1
\end{eqnarray*}
\bigskip

  \item $\displaystyle \sum_{i=5}^{2n} i$

\textbf{SOLUTION:}\\
\begin{eqnarray*}
\sum_{i=5}^{2n} i &=& \sum_{i=1}^{2n} i \;-\; \sum_{i=1}^{4} i \\
 &=& \frac{(2n)(2n+1)}{2} - 10 \qquad
\text{stopping here is fine} \\
 &=& 2n^2 + n -10
\end{eqnarray*}
\bigskip

  \item $\displaystyle \sum_{i=0}^n ( a^i - 2 i + n ) $

\textbf{SOLUTION:}\\
\begin{eqnarray*}
\sum_{i=0}^n ( a^i - 2 i + n )
&=& \sum_{i=0}^n a^i - 2 \sum_{i=0}^n i +  \sum_{i=0}^n n \\
&=& \frac{a^{n+1} - 1}{a-1} - (n+1)n + (n+1)n \\
&=& \frac{a^{n+1} - 1}{a-1}
\end{eqnarray*}
\bigskip

  \item $\displaystyle \sum_{i=0}^{n-1}\bigl( c + \sum_{j=0}^{i-1}
        (j+2) \bigr)$

\textbf{SOLUTION:}\\
This one's pretty involved and is a bit too much to do on a quiz...
\begin{eqnarray*}
\sum_{i=0}^{n-1}\bigl( c + \sum_{j=0}^{i-1}
        (j+2) \bigr) 
&=& c \cdot n + \sum_{i=0}^{n-1} \frac{i(i-1)}{2} + \sum_{i=0}^{n-1} 2i \\
&=& c \cdot n + \sum_{i=0}^{n-1}\frac{i^2}{2} 
  - \sum_{i=0}^{n-1}\frac{i}{2} + \frac{2(n-1)n}{2} \\
&=& c \cdot n + \frac{(n-1)n(2n-1)}{12} -
  \frac{(n-1)n}{4} + (n-1)n \\
&=& c \cdot n + \frac{(n-1)n}{12}
 \bigl[ (2n-1) - 3 + 12 \bigr] \\
&=& c \cdot n + \frac{(n-1)n(n+4)}{12}
\end{eqnarray*}
\bigskip

\end{enumerate}
  
\item Prove using mathematical induction that $f_n >
(3/2)^n$, for $n \geq 5$.  Here, $f_n$ is the $n$th Fibonacci
number. Use the definition of the Fibonacci numbers given in the text.
Study the example inductive proof on page~6 carefully.

\textbf{SOLUTION:}\\
\begin{description}
\item[Basis case:] Two basis cases are needed. (This is important!)
For $n=5$, $f_5= 8$ and $(3/2)^5 < 7.594$.  For $n=6$, $f_6 = 13$ and
$(3/2)^6 < 11.391$.  In each of these cases, $f_n > (3/2)^n$.

\item[Induction hypothesis:]  For all $k, 5 \leq k < n$, $f_k < (3/2)^k$.

\item[Induction step:] For $n \geq 7$, 
\begin{eqnarray*}
f_n &=& f_{n-1} + f_{n-2} \\
    &>& (3/2)^{n-1} + (3/2)^{n-2} \qquad \text{Induction Hypothesis} \\
    &=& \frac{ (3/2)^n }{ 3/2 } + \frac{ (3/2)^n }{ (3/2)^2 } \\
    &=& \frac{2}{3} (3/2)^n + \frac{4}{9} (3/2)^n \\
    &=& \bigl( \frac{2}{3} + \frac{4}{9} \bigr) (3/2)^n \\
    &=& \frac{10}{9} (3/2)^n \\
    &>& (3/2)^n
\end{eqnarray*}
Hence, $f_n > (3/2)^n$.
\end{description}
\bigskip


\item Write the code necessary to accomplish the merging step in
\verb$MergeSort$.  This code should follow the comments in the main
\verb$MergeSort$ function.

\textbf{SOLUTION:} \\
The following is probably more terse than what you came up with on
your own.  Be sure you understand what it is doing.  It could be made
more efficient, mostly by eliminating the need for allocating
\verb$temp$. 
\begin{verbatim}
        T* temp = new T[high-low+1];  // scratch array for merging
        int i=low, j=mid+1, loc=0;

        //  while neither the left nor the right half is exhausted, 
        //  take the next smallest value into the temp array
        while ( i<=mid && j<=high ) {
          if ( pts[i] < pts[j] ) temp[loc++] = pts[i++];
          else                   temp[loc++] = pts[j++];
        }

        //  copy the remaining values --- only one of these will iterate
        for ( ; i<=mid; i++, loc++ ) temp[loc] = pts[i];
        for ( ; j<=high; j++, loc++ ) temp[loc] = pts[j];

        //  copy back from the temp array
        for ( loc=0, i=low; i<=high; loc++, i++ ) pts[i]=temp[loc];
        delete [] temp;
\end{verbatim}


\end{enumerate}



\end{document}