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

\psol{7}{October 29, 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 (away from 0, as
      otherwise $\lim_{n\to\infty}\frac{g(n)}{f(n)}$ would be unbounded
      i.e. $g\neq O(f)$), 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{

Observe that a string of length $n$ contains 01 iff 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, or both.  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{

\iffalse
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$. 

\fi

We have a nonhomogeneous linear recurrence, so 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} =   2c 2^{n-3} - c2^{n-4} + 2^{n-2},
\]
so
\[
c2^{n-4} = 2^{n-2},
\]
and therefore $c=4$.  So, ignoring boundary conditions, $c2^{n-2} = 2^n$
will be a particular solution.

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

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) = 2^n - n
-1$.

Suppose a bit string does not contain the string $01$.  Then no occurrence
of a 0 in the string can be followed by a 1, which means that as soon as a
0 occurs, all the remaining bits must be 0's.  So the string must consist
of a sequence of 1's followed by a (possibly empty) sequence of 0's.  The
initial string of 1's can be of any length from 0 to $n$.  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}
