\documentclass[11pt,twoside]{article}
\usepackage{amsmath,graphicx}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}
\begin{document}
\newcommand{\solution}[1]{}
%\renewcommand{\solution}[1]{\smallskip {\bf Solution:}\\ #1}

\newcommand\N{\mathbb{N}}

\pset{7}{October 21, 1999}{start of tutorial, October 28, 1999}
\textbf{Reading} The Rosen test, \S 5.1-2; F97 Lecture Notes 9, 11

{\large
Remember to include a \textbf{collaboration statement} on the front page
of your solutions (see Handout 2, \emph{Course Information}).}

Note: None of these problems requires a lot of writing.  Consider this
when writing up your solutions.

In the following problems, you will see the notation $f(n) =
\Theta(g(n))$, for functions $f$ and $g$. This is defined as follows:
\begin{defin*}
  For functions $f$ and $g$, we will write $f(n) = \Theta(g(n))$ when
  $f(n) = O(g(n))$ and $g(n) = O(f(n))$.
\end{defin*}


\begin{problems}
  \problem \textbf{Asymptotic notation} \\
  For each pair of functions $(f(n), g(n))$ in the table below,
  indicate whether the statement at the top of the column is true
  (e.g., whether $f(n) = O(g(n))$).  Assume $k\geq 1$, $\epsilon > 0$,
  and $c > 1$ are constants. Your answer should be in the form of a
  table with ``yes'' or ``no'' in each box.
  \begin{equation*}
    \begin{array}{|cc|*{3}{c|}}
      \hline
      f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
      \Theta(g(n)) \\\hline\hline
      \log^k n & n^\epsilon &&&\\\hline
      n^k & c^n &&&\\\hline
      \sqrt{n} & n^{\sin n} &&&\\\hline
      2^n & 2^{n/2} &&&\\\hline
      \log(n!) & \log(n^n) &&&\\\hline
    \end{array}
  \end{equation*}

  \solution{
    \newcommand\y{\text{yes}}
    \newcommand\n{\text{no}}
                                %
    \begin{equation*}
      \begin{array}{|cc|*{3}{c|}}
        \hline
        f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
        \Theta(g(n)) \\\hline\hline
        \log^k n & n^\epsilon & \y & \n & \n \\\hline
        n^k & c^n & \y & \n & \n \\\hline
        \sqrt{n} & n^{\sin n} & \n & \n & \n\\\hline
        2^n & 2^{n/2} & \n & \y & \n \\\hline
        \log(n!) & \log(n^n) & \y & \y & \y \\\hline
      \end{array}
    \end{equation*}

    Following are some hints on deriving the table above:\\
    (a) See notes on $O$-notation. (to appear)\\
    (b) Polynomial growth versus exponential growth. (See Theorem 3.6,
    Lecture 9, Fall97.)\\
    (c) When $n$ is a multiple of $\pi$, $n^{\sin n}=1$, so no
    constant times 1 will bound $\sqrt n$ as $n$ ranges over
    multiples of $\pi$. When $n$ is of the form $2k'\pi + \pi/2$,
    for some integer $k'$, then $n^{\sin n}=n$ and $\frac{n}{\sqrt n} =
    \sqrt n$ grows without bound as $k'$ increases.\\
    (d) $\frac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
    grows -- it is not bounded by a constant.\\
    (e) See Rosen \S 1.8 Ex. 61,62\\
    }

  \problem \textbf{Asymptotic notation} \\
  You don't need to give proofs for this problem.

  \begin{problemparts}
    \problempart Find functions $f_1$, $f_2$, $g_1$, and $g_2$, such
    that
    \begin{align*}
      f_1(n) &= \Theta(f_2(n)),\\
      g_1(n) &= \Theta(g_2(n)),\\      
      \neg [f_1(g_1(n)) &= \Theta(f_2(g_2(n)))].\\
    \end{align*}

    \solution{$f_1(n) = f_2(n) = 2^n$, $g_1(n) = n$, $g_2(n) = 2n$.}
    

    \problempart Find functions $f$ and $g$ such that
    \begin{gather*}
      f(n) = O(g(n)), \text{ but } \neg [g(n) = O(f(n))];\\
      f(g(n)) = \Theta(g(f(n))).
    \end{gather*}

    \solution{$f(n) = n^2$, $g(n) = n^3$.}

      
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      f(g(n)) &= O(g(f(n))),  &\text{ but } &&\neg [g(f(n)) &=
      O(f(g(n)))].\\
    \end{alignat*}

    \solution{$f(n) = n^2$, $g(n) = 2^n$.}
    
    
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      g(f(n)) &= O(f(g(n))), &\text{ but } &&\neg [f(g(n)) &= O(g(f(n)))].\\
    \end{alignat*}
    
    \solution{$f(n) = 2^n$, $g(n) = 2^{2 n}$. Then $f(g(n)) = 2^{2^{2
          n}}$, while $g(f(n)) = 2^{2^{n+1}}$.}
  \end{problemparts}

  

  \problem \textbf{Stirling's formula and asymptotic notation} \\
  Let $\lambda$ be a constant, $0 < \lambda < 1$. Suppose we start
  with integers from 1 to $n$, and we would like to pick out a
  fraction $\lambda n$ of them. We will use Stirling's formula to help
  us approximate the number of ways to do this.
  
  First, let's see how many ways there are to make an ordered sequence
  of $\lambda n$ numbers between $1$ and $n$. We will use the product
  rule: There are $n$ possibilities for the first number, $n-1$ for
  the second one, $n-2$ for the third, etc. The total number of
  sequences is
  \begin{equation*}
    n \cdot (n-1) \cdot (n-2) \cdots (n - \lambda n + 1) =
    \frac{n \cdot (n-1) \cdots 2 \cdot 1}{(n-\lambda n) \cdot
      (n-\lambda n-1) \cdots 2 \cdot 1}
    = \frac{n!}{(n-\lambda n)!}.
  \end{equation*}

  Now let us ignore order, i.e., let's count subsets of size $\lambda
  n$ instead of sequences of that size. A set of size $\lambda n$ can
  be ordered in
  \begin{equation*}
    \lambda n \cdot (\lambda n - 1) \cdot (\lambda n - 2) \cdots 2
    \cdot 1 = (\lambda n)!
  \end{equation*}
  ways ($\lambda n$ choices for which element to put first, $\lambda n
  - 1$ for which to put second, etc.). Therefore, the number of
  subsets of size $\lambda n$ is
  \begin{equation*}
    \frac{n \cdot (n-1) \cdot (n-2) \cdots (n - \lambda n +
      1)}{(\lambda n)!} =
    \frac{n!}{(\lambda n)! (n-\lambda n)!}.
  \end{equation*}
  Define
  \begin{equation*}
    f_\lambda(n) = \frac{n!}{(\lambda n)! (n-\lambda n)!}.
  \end{equation*}
  
  In this problem, you will need to estimate $f_\lambda(n)$
  for large values of $n$, while $\lambda$ stays constant.

  \begin{problemparts}
    \problempart
    Show that
    \begin{equation*}
       f_\lambda(n) = \Theta(2^{n H(\lambda)}/\sqrt{n}),
    \end{equation*}
    where
    \begin{equation*}
      H(\lambda) = - \lambda \log_2 \lambda - (1-\lambda)
      \log_2(1-\lambda).
    \end{equation*}
    Remember that you have to prove both an upper and a lower bound.

    \solution{
      First, let's show the upper bound, i.e., that $f_\lambda(n) =
      O(2^{n H(\lambda)}/\sqrt{n})$.
      \begin{align*}
        \frac{n!}{(\lambda n)! (n - \lambda n)!} &=
        O\left(\frac{n^{1/2} (n/e)^n}{n \sqrt{\lambda (1-\lambda)} (\lambda
          n/e)^{\lambda n} ((1-\lambda) n/e)^{(1-\lambda) n}}\right)
        \\&= O\left(\frac{(n/e)^n}{n^{1/2} (n/e)^n \lambda^{\lambda n}
          (1-\lambda)^{(1-\lambda) n}}\right)
        \\&= O\left(\frac{1}{n^{1/2} (\lambda^\lambda
          (1-\lambda)^{1-\lambda})^n}\right)
        \\&= O\left(\frac{2^{n H(\lambda)}}{n^{1/2}}\right).
      \end{align*}
      Note that we used Stirling's formula to both put an upper bound
      on $n!$ and a lower bound on $(\lambda n)! (n - \lambda n)!$.
      
      We can similarly show the lower bound, i.e., that $2^{n
        H(\lambda)}/\sqrt{n} = O(f_\lambda(n))$. We would use
      Stirling's formula to get a lower bound on $n!$ and an upper
      bound on $(\lambda n)! (n - \lambda n)!$.
      }
    
    
    \problempart (optional) Let $n = 100$ and $\lambda = 0.3$. Compute $\log_2
    f_\lambda(n)$. Also, compute the logarithm base $2$ of the
    approximation of $f_\lambda(n)$ that you proved in part~(a). Note
    that the first task would most likely require a computer program,
    while the second can be done with a regular pocket calculator.

    \solution{
      \begin{align*}
        \log_2 f_{0.3}(100) &= 84.6027,\\
        \log_2 (2^{100\cdot H(0.3)}/\sqrt{100}) &= 84.8072.
      \end{align*}
      }
    

    \problempart (optional) If we have a number $x$ and an approximation $x'$, we
    say that the \emph{relative error} of the approximation is
    $\left|\frac{x' - x}{x}\right|$. Compute the relative error of the
    approximation you obtained in part~(b).

    \solution{
      The relative error is
      \begin{equation*}
        \frac{84.8072 - 84.6027}{84.8072} = 0.00241135.
      \end{equation*}
      }

    
    \problempart Prove the following statement: If $f$ and $g$ are
    positive-valued functions such that $f(n) = \Theta(g(n))$, and
    $\lim_{n\to\infty} g(n) = \infty$, then $\log f(n) \sim \log g(n)$
    (the base of the logarithm is arbitrary).
    
    \solution{     
      We have,
      \begin{equation*}
        \frac{\log f(n)}{\log g(n)} =
        \frac{\log g(n) -\log g(n) + \log f(n)}{\log g(n)}
	= \frac{\log g(n) + \log \frac{f(n)}{g(n)}}{\log g(n)}
        = 1 + \frac{\log \frac{f(n)}{g(n)}}{\log g(n)}
      \end{equation*}
      We are given that $f(n)=\Theta(g(n))$, therefore
      $\lim_{n\to\infty}\frac{f(n)}{g(n)}$ is bounded, and moreover,
      $\lim_{n\to\infty}\log\frac{f(n)}{g(n)}$ is bounded. We are also
      given that $\lim_{n\to\infty} g(n) = \infty$, therefore
      $\lim_{n\to\infty} \log g(n) = \infty$. Thus, 
      \begin{equation*}
        \lim_{n\to\infty} \frac{\log f(n)}{\log g(n)} =
        \lim_{n\to\infty} (1 + \frac{\log \frac{f(n)}{g(n)}}{\log g(n)})
        = 1 + \frac{\lim_{n\to\infty}\log
      \frac{f(n)}{g(n)}}{\lim_{n\to\infty} \log g(n)}
        = 1.
      \end{equation*}
      i.e. $\log f(n) \sim \log g(n)$.


%      It is easy to show, given $f(n) = \Theta(g(n))$, that there
%      exist constants $c_1$ and $c_2$, with $0 < c_1 \leq c_2$, and an
%      integer $n_0$, such that
%      \begin{equation*}
%        \frac{f(n)}{g(n)} \in [c_1, c_2]
%      \end{equation*}
%      for all $n > n_0$.
%      
%      Let $h(n) = \log g(n)$. Since $\lim_{n\to\infty} g(n) = \infty$,
%      we must have $\lim_{n\to\infty} h(n) = \infty$. Consequently,
%      \begin{equation*}
%        \lim_{n\to\infty} \frac{1}{h(n)} = 0.
%      \end{equation*}

%      We have
%      \begin{equation*}
%        \frac{\log f(n)}{\log g(n)} =
%        \frac{\log g(n) + \log \frac{f(n)}{g(n)}}{\log g(n)}
%        = 1 + \frac{\log \frac{f(n)}{g(n)}}{h(n)}
%        = 1 + \ell(n),
%      \end{equation*}
%      where $\ell(n) = \frac{\log \frac{f(n)}{g(n)}}{h(n)}$.

%      For all $n>n_0$, we have
%      \begin{equation*}
%        \ell(n) =
%        \frac{\log \frac{f(n)}{g(n)}}{h(n)}
%       \in \left[\frac{\log c_1}{h(n)}, \frac{\log c_2}{h(n)}\right].
%      \end{equation*}
%      Clearly, $\log c_i$ is a constant for each $i\in \{1, 2\}$ (note
%      that $c_i > 0$). Therefore,
%      \begin{equation*}
%        \lim_{n\to\infty} \frac{\log c_i}{h(n)} =
%        \log c_i \times \lim_{n\to\infty} \frac{1}{h(n)}
%        = 0.
%      \end{equation*}

%      It follows that
%      \begin{equation*}
%        \lim_{n\to\infty} \ell(n) = 0.
%      \end{equation*}
%      Consequently,
%      \begin{equation*}
%        \lim_{n\to\infty} \frac{\log f(n)}{\log g(n)} =
%        \lim_{n\to\infty} (1 + \ell(n))
%        = 1 + \lim_{n\to\infty} \ell(n)
%        = 1.
%      \end{equation*}
%      Thus $\log f(n) \sim \log g(n)$.
      }
  \end{problemparts}

  \problem \textbf{Linear recurrences} \\
  \begin{problemparts}
    \problempart Find a recurrence relation for the number $a_n$ of
    bit strings of length $n\geq 0$ that contain the string $01$ at
    least once.  \emph{Hint:} you might find inclusion-exclusion
    useful.
    
    \solution{
      Suppose $n\geq 2$. Consider a bit string $x_1 x_2
      \cdots x_n$ of length $n$ that contains the string $01$. We have
      two cases.
      \begin{enumerate}
      \item $x_1 = 1$

        In this case, $01$ must be contained in the substring $x_2 x_3
        \cdots x_n$. The substring $x_2 \cdots x_n$ has length $n-1$,
        and it contains $01$, so it can be chosen in $a_{n-1}$ ways.
        Thus, this case leads to $a_{n-1}$ possibilities.
      \item $x_1 = 0$
        
        In this case we either have $x_2 = 1$ (in which case $x_1 x_2
        = 01$), or $01$ is contained in the substring $x_2 x_3 \cdots
        x_n$, or both. We thus need to count the number of ways to
        choose a bit string of length $n-1$ such that it either starts
        with $1$, or contains the string $01$, or both.

        There are $2^{n-2}$ bit strings of length $n-1$ that start
        with $1$ (since there are $n-2$ bits besides the first one,
        and they can be chosen arbitrarily).

        There are $a_{n-1}$ ways to choose a bit string of length
        $n-1$ that contains the string $01$.

        Now let's see how many bit strings of length $n-1$ there are
        that start with $1$ \emph{AND} contain $01$. The string $01$
        would have to be contained in the last $n-2$ bits, so the
        answer is $a_{n-2}$.

        Now we use inclusion-exclusion to obtain that the number of
        choices for $x_2 x_3 \cdots x_n$ in the case $x_1 = 0$ is
        \begin{equation*}
          2^{n-2} + a_{n-1} - a_{n-2}.
        \end{equation*}
      \end{enumerate}

      Combining the two cases, we obtain
      \begin{equation*}
        a_n =
        a_{n-1} + 2^{n-2} + a_{n-1} - a_{n-2}
        = 2 a_{n-1} - a_{n-2} + 2^{n-2}.
      \end{equation*}

% albert's solutions

Another way to obtain a recurrence for the number, $a_n$, of strings of
length $n$ that contain 01 is to observe that a string of length $n$
contains 01 iff it starts it has a 01 starting at its first bit---that is,
it begins with 01---or it contains a 01 starting at the second or later
bit.  To count these we use inclusion-exclusion, namely $a_n$ will equal
the sum of the number of strings that begin with 01 and the number of
strings that contain 01 beginning at the second or later bit, minus the
strings that both begin with 01 and also contain 01 later on.

There are $2^{n-2}$ strings of length $n$ that start with 01.  The strings
of length $n$ that contain 01 starting at the second or later bit can
start with 0 or 1 followed by a string of length $n-1$ that contains a 01,
so there are $2 a_{n-1}$ of these length $n$ strings.  Finally, if a
string starts with 01 \emph{and also} has 01 later, then the second 01 can
only start at the third bit or later, so the number of such strings is
precisely $a_{n-2}$.  Thus, we have
\[
a_n = 2^{n-2} + 2 a_{n-1} - a_{n-2}.
\]

There is also a simple way to derive a recurrence without need for
inclusion-exclusion.  Count both the number, $w_n$, of length $n$ strings
that start with a 1 and contain a 01, and also the number, $z_n$, of
length $n$ strings that start with a 0 and contain a 01.  Then the number
of length $n$ srings that contain a 01 is simply $w_n+z_n$.

Now a length $n \geq 2$ string that starts with 0 can contain 01 because
the next bit is 1; there are $2^{n-2}$ such strings.  Alternatively, it
can start with 0 followed by a string of length $n-1$ that starts with 0
and contains 01; there are $z_{n-1}$ such strings, so
\[
z_n = 2^{n-2} + z_{n-1}.
\]
Now it's easy to see that $z_n = \sum_{i=0}^{n-2} 2^i = 2^{n-1} - 1$.

Next, a length $n \geq 2$ string that starts with 1 can contain 01 only if
the initial 1 is followed by a length $n-1$ string that contains 01; we
know there are $w_{n-1} + z_{n-1}$ such length $n-1$ strings, so
\[
w_n = w_{n-1} + z_{n-1} = w_{n-1} +  2^{n-2} - 1.
\]
Now it's easy to see that
\[
w_n = \sum_{i=0}^{n-2} (2^i -1) = 2^{n-1} - 1 - (n - 1) = 2^{n-1} - n,
\] 
and so finally the number length $n$ strings containing 01 is $z_n + w_n = 
(2^{n-1} - 1) + (2^{n-1}- n) = 2^n - (n+1)$.
      }
    
    
    \problempart What are the initial conditions?

    \solution{$a_0 = a_1 = 0$.}

    
    \problempart Solve the recurrence.
    
    \solution{This is a linear nonhomogeneous recurrence relation with
    constant coefficients. The characteristic equation of the associated
    linear homogeneous recurrence relation is
    \begin{equation*}
      r^2 - 2 r + 1 = 0,
    \end{equation*}
    and it has solution $r = 1$ of multiplicity $2$. 
%From Rosen
%    theorem~5.2.6, we see that there is a particular solution of
%    form
%    \begin{equation*}
%      a_n = c \cdot 2^n
%    \end{equation*}
%    for some $c$. Substituting this into the recurrence relation shows
%    that $c = 1$. 
% albert's addition
We have to find a particular solution to the nonhomogeneous recurrence.
Following the "guessing" strategy suggested in Lecture Notes 11, we'll
guess that a solution is a constant multiple of the nonhomogeneous term,
that is, it is of the form $c2^{n-2}$.  To find $c$ and verify the guess,
we substitute the guess into the recurrence: \[ c2^{n-2} = c2^{n-3} +
c2^{n-4} + c2^{n-3} - c2^{n-4} \] which we see is an identity for
\emph{any} constant $c$.  So, ignoring boundary conditions, $c2^{n-2}$ will
be a particular solution for any $c$.  To keep the solution simple
looking, let's choose $c=4$, so we have $2^n$ as a particular solution.
% end albert's addition
    We now see from Rosen theorems~5.2.4 and~5.2.5 that
    a sequence $\{a_n\}$ is a solution if and only if
    \begin{equation*}
      a_n =
      c_1 \cdot 1^n + c_2 n \cdot 1^n + 2^n
      = c_1 + c_2 n + 2^n
    \end{equation*}
    for some $c_1$ and $c_2$.

    Substituting this into the initial conditions shows that $c_1 =
    c_2 = -1$. Thus the solution is
    \begin{equation*}
      a_n = 2^n - n - 1.
    \end{equation*}
    }

  
    \problempart Having seen in part~(c) the formula for $a_n$, think
    of a way to derive and prove that formula without the use of
    recurrences.

    \solution{
      There are $2^n$ bit strings of length $n$. Let's show that there
      are exactly $n+1$ bit strings of length $n$ that \emph{do not}
      contain the string $01$, and then it will follow that $a_n = 2^n
      - n - 1$.

      Suppose a bit string $x_1 x_2 \cdots x_n$ does not contain the
      string $01$. There are two cases.
      \begin{enumerate}
      \item $x_1 = x_2 = \cdots = x_n = 1$.

        This case has exactly one choice (i.e., the string of $n$
        $1$'s).
      \item $x_i = 0$ for some $i$ with $1\leq i\leq n$.
        
        Let $S = \{i\in \N : 1\leq i\leq n \wedge x_i = 0\}$. Clearly,
        $S$ is nonempty. Therefore, by the well-ordering principle, it
        has a least element. Let $k = \min S$. By definition of $k$
        and $S$, we must have $x_i = 1$ for all $i$ with $1\leq i \leq
        k-1$.
        
        Now let's show that $x_i = 0$ for all $i$ with $k\leq i\leq
        n$. We will prove it by induction on $i$. For the base case
        $i=k$, we have $x_i = x_k = 0$ by definition of $k$. Suppose
        $x_i = 0$ for some $i$ with $k\leq i < n$, but $x_{i+1} \ne
        0$. Then $x_i x_{i+1} = 01$, and so the string $x_1 x_2 \cdots
        x_n$ contains $01$. Contradiction. It follows that $x_i = 0$
        for all $i$ with $k\leq i\leq n$.
        
        We thus see that that $x_1 x_2 \cdots x_n$ consists of $k-1$
        $1$'s followed by $n-k+1$ $0$'s, for some $k$ with $1\leq
        k\leq n$.  Conversely, for any $k$ with $1\leq k\leq n$, the
        string of $k-1$ $1$'s followed by $n-k+1$ $0$'s does not
        contain $01$.  There are $n$ possible values for $k$.  We thus
        see that the case $x_i = 0$ leads to $n$ choices.
      \end{enumerate}

      We conclude that there are $n+1$ bit strings of length $n$ that
      do not contain $01$.
      }
  \end{problemparts}

  
  \problem \textbf{Linear recurrences} \\
  \begin{problemparts}
    \problempart Let $a_n$ be the number of ways to tile a $1\times n$
    board using $1\times 1$ and $2\times 1$ blocks. An example of such
    a tiling for $n=10$ is shown in fig.~\ref{fig:exa}. Write a linear
    recurrence for $a_n$ and justify its correctness.  Give a solution
    to the recurrence. (Do not use the results of parts~(b) and~(c).)
    Compute $a_{10}$.
    \begin{figure}[htbp]
      \begin{center}
        \includegraphics[width=2.5in]{H40-ps7-fig3}
        \caption{Illustration for problem~5(b).}
        \label{fig:exa}
      \end{center}
    \end{figure}

    \solution{
      If the leftmost block is $1\times 1$, then the rest is a
      $1\times (n-1)$ board, which can be tiled in $a_{n-1}$ ways. If
      the leftmost block is $2\times 1$, then the rest is a $1\times
      (n-2)$ board, which can be tiled in $a_{n-2}$ ways. Thus
      \begin{equation*}
        a_n = a_{n-1} + a_{n-2}.
      \end{equation*}
      The initial conditions are $a_1 = 1$ (the only covering is to
      use one $1\times 1$ block) and $a_2 = 2$ (either one $2\times
      1$, or two $1\times 1$'s). Clearly, the solution is 
      \begin{equation*}
        a_n =
        f_{n+1}
        = \frac{1}{\sqrt{5}} \left(\frac{1 +
            \sqrt{5}}{2}\right)^{n+1} - \frac{1}{\sqrt{5}}
            \left(\frac{1 - \sqrt{5}}{2}\right)^{n+1},
      \end{equation*}
      i.e., the Fibonacci numbers shifted by one.

      We have
      \begin{equation*}
        a_{10} = f_{11} = \frac{1}{\sqrt{5}} \left(\frac{1 +
            \sqrt{5}}{2}\right)^{11} - \frac{1}{\sqrt{5}}
        \left(\frac{1 - \sqrt{5}}{2}\right)^{11} = 89.
      \end{equation*}
      }

    
    \problempart Let $b_n$ be the number of ways to tile a $2\times n$
    board using solely $2\times 1$ blocks. An example of such a tiling
    for $n=10$ is shown in fig.~\ref{fig:exb}. Write a linear
    recurrence for $b_n$ and justify its correctness.  Give a solution
    to the recurrence. (Do not use the results of parts~(a) and~(c).)
    \begin{figure}[htbp]
      \begin{center}
        \includegraphics[width=2.5in]{H40-ps7-fig2}
        \caption{Illustration for problem~5(b).}
        \label{fig:exb}
      \end{center}
    \end{figure}

    \solution{
      If the upper left square is covered by a vertical $2\times 1$
      block, then the rest is a $2\times (n-1)$ board, and so there
      are $b_{n-1}$ tilings.

      If the upper left square is covered by a horizontal $2\times 1$
      block, then the lower left square also has to be covered by a
      horizontal $2\times 1$ block. Then the rest is a $2\times (n-2)$
      board, and so there are $b_{n-2}$ tilings.

      We obtain $b_n = b_n + b_{n-1}$. The initial conditions are $b_1
      = 1$ (one vertical $2\times 1$ block) and $b_2 = 2$ (two blocks,
      either horizontally or vertically).

      The solution is as in part~(a):
      \begin{equation*}
        b_n =
        f_{n+1}
        = \frac{1}{\sqrt{5}} \left(\frac{1 +
            \sqrt{5}}{2}\right)^{n+1} - \frac{1}{\sqrt{5}}
            \left(\frac{1 - \sqrt{5}}{2}\right)^{n+1}.
      \end{equation*}
      }
    

    \problempart Show a bijection from the tilings in part~(a) to the
    tilings in part~(b). You do not need to give a proof.

    \solution{
      We will use a coordinate system with the origin at the lower
      left, with $x$ increasing to the right and $y$ increasing
      upward.

      Given a tiling of a $1\times n$ board, we will tile a $2\times
      n$ board as follows: For a $1\times 1$ block at square $(x, 1)$,
      make a vertical $2\times 1$ block with lower end at square $(x,
      1)$. For every $2\times 1$ block with left end at square $(x,
      1)$, make two horizontal $2\times 1$ blocks with left ends at
      $(x, 1)$ and $(x, 2)$ respectively.

      See fig.~\ref{fig:bij}.
      \begin{figure}[htbp]
        \begin{center}
          \includegraphics[width=2.5in]{H40-ps7-fig1}
          \caption{Illustration for solution~5(c).}
          \label{fig:bij}
        \end{center}
      \end{figure}
      }
  \end{problemparts}
  
  
  

  \problem \textbf{Multiple linear recurrences} \\
  On a certain far away island, all men are either blond or
  brown-haired. Studies show that each man has four sons. Every blond
  father has exactly three blond sons, while every brown-haired man
  has exactly two brown-haired sons.
  
  \begin{problemparts}
    \problempart Let $a_n$ and $b_n$ denote the number of blond and
    brown-haired men, respectively, in the $n$th generation. Write a
    system of recurrences for $a_n$ and $b_n$.

    \solution{
      \begin{equation*}
        \begin{split}
          a_n &= 3 a_{n-1} + 2 b_{n-1},\\
          b_n &= a_{n-1} + 2 b_{n-1}.
        \end{split}
      \end{equation*}
      }
    
    \problempart For which values of $c\ne 0$ and $d$ will we have a
    solution of the form $a_n = c^n$, $b_n = d c^n$?
    
    \solution{ Assume $a_n = c^n$ and $b_n = d c^n$ for some $c\ne 0$
      and $d$. Let's substitute this into the system of recurrences.
      We will obtain the equations
      \begin{align*}
        c^n &= 3 c^{n-1} + 2 d c^{n-1},\\
        d c^n &= c^{n-1} + 2 d c^{n-1}.
      \end{align*}
      Dividing out $c^{n-1}$ (which is allowed, since $c\ne 0$), we
      obtain
      \begin{equation}
        \label{eq:cd}
        \begin{split}
          c &= 3 + 2 d,\\
          d c &= 1 + 2 d.
        \end{split}
      \end{equation}
      Multiplying both sides of the first equation by $d$ and
      subtracting the second equation, we obtain
      \begin{equation*}
        0 = 3 d + 2 d^2 - 1 - 2d = 2 d^2 + d - 1.
      \end{equation*}
      Solving the quadratic equation, we obtain $d \in \{-1,
      \frac{1}{2}\}$. Substituting into~\eqref{eq:cd}, we obtain the
      solutions
      \begin{alignat*}{2}
        c &= 1, \quad &d &= -1;\\
        c &= 4, \quad &d &= \frac{1}{2}.
      \end{alignat*}
      }

    
    \problempart Show that there exist values for $c_1$, $c_2$, $d_1$,
    and $d_2$ such that
    \begin{equation*}
      \begin{split}
        a_n &= x c_1^n + y c_2^n,\\
        b_n &= x d_1 c_1^n + y d_2 c_2^n,
      \end{split}
    \end{equation*}
    is a solution for all $x$ and $y$.
    
    \solution{ Let $c_1 = 1$, $d_1 = -1$, $c_2 = 4$, $d_2 =
      \frac{1}{2}$ (i.e., the two pairs of $c$ and $d$ that were
      obtained in part~(a)).  From part~(a) we know that $a_n =
      c_i^n$, $b_n = d_i c_i^n$ is a solution to the recurrences, for
      each $i\in \{1, 2\}$. It is easy to verify that a constant
      multiple of a solution is a solution, and that a sum of two
      solutions is a solution.  }

%     \problempart Let $c_1$, $c_2$, $d_1$, and $d_2$ be the values you
%     obtained in part~(b). Show that every solution to the system of
%     recurrences~\eqref{eq:sys} can be written in the form
%     of~\eqref{eq:sol} for some $x$ and $y$.
%
%     \solution{Show that $x$ and $y$ can be found for any initial
%       conditions. Then use induction to show that two solutions with the
%       same initial conditions are equal everywhere.}
    
  
    \problempart Suppose in the first generation there were ten blond
    and twenty brown-haired men on the island. How many of each
    group will there be in the $n$th generation?
    
    \solution{We have $a_1 = 10$, $b_1 = 20$. Let's find $x$ and $y$
    such that a solution in the form of part~(d) would satisfy these
    initial conditions. We have
    \begin{align*}
      10 &= x \cdot 1^1 + y \cdot 4^1,\\
      20 &= x \cdot (-1) \cdot 1^1 + y \cdot \frac{1}{2} \cdot 4^1,
    \end{align*}
    which can be rewritten as
    \begin{align*}
      10 &= x + 4 y,\\
      20 &= -x + 2 y.
    \end{align*}
    This gives $x = -10$ and $y = 5$.

    Thus the solution is
    \begin{align*}
      a_n &= -10 + 5 \cdot 4^n,\\
      b_n &= 10 + \frac{5}{2} \cdot 4^n.
    \end{align*}
    }
  \end{problemparts}
\end{problems}

\newpage

\section*{Topics for Week of October 25th, 1999}



\subsection*{Estimates and Asymptotic Notation\\
(Reading Source: F97 Lecture Notes 9)}

\begin{itemize}
\item 
Estimating $n\hbox{!}$ using Stirling's Formula --- upper and lower bounds
\item
Asymptotic notation for bounding function growth and algorithm running times
\begin{itemize}
\item
$O$ notation 
\item
$\Theta$ notation 
\end{itemize}
\end{itemize}

\subsection*{Linear Recurrence Relations\\
(Reading Source: Rosen 5.1-2, F97 Lecture Notes 11)}
\begin{itemize}
\item
Modeling problems with recurrence relations --- setting up recurrences and boundary conditions
\item 
Solving linear homogeneous recurrence relations with constant coefficients
\item
Solving linear inhomogeneous recurrence relations with constant coefficients 
\item
Example: Fibonacci Numbers 
\end{itemize}


\end{document}
