\documentstyle[12pt,macpsfig,amssymb]{article}
\input{macros-course}
 
\begin{document}

%\newcommand{\solution}[1]{}
%\newcommand{\sol}[1]{}
%\handout{pquiz}{Practice Quiz}{October 27, 1998}

\newcommand{\solution}[1]{\bigskip #1}
\newcommand{\sol}[1]{#1}
\handout{pquizsol}{Practice Quiz Solutions}{October 30, 1998}

\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

%{\bf This practice quiz is the actual exam from Fall 1997.  The quiz
%this term will cover everything in the course up to and including the
%lecture on Tuesday, October 27.  This includes inclusion-exclusion,
%the product rule, tree diagrams, and permutations, which are not
%covered on this practice quiz.  These topics are covered in Fake
%Problem Set $7.5$.}

\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Use induction to prove that
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
 whenever $n$ is a natural number.

\solution{
Use induction to prove our proposition, P(n), 
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]
 whenever $n$ is a natural number.

{\bf Base Case:}  $n = 0 $

The left side is an empty sum, so $0 = \left(\frac{0 \cdot 1}{2}\right)^2 = 0$.

{\bf Inductive Step:}   Show that $P(n)  \rightarrow P(n+1)$.

By the inductive hypothesis, we assume that 
 \[ 1^3 + 2^3 + \ldots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \]

\begin{eqnarray*}
1^3 + 2^3 + \ldots + n^3 + (n+1)^3 \\
&= &\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3\\
&= &\frac{n^2(n+1)^2 + 4(n+1)(n+1)^2}{4}\\
&= &\frac{(n^2+4n+4)(n+1)^2}{4}\\
&= &\left(\frac{(n+1)(n+2)}{2}\right)^2\\
\end{eqnarray*}

And our hypothesis is proved.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 2
\problem 

Why can't you find an integer $x$ for which
\[384\cdot x = 1 \pmod{566}?\]

\solution{
This is equivalent to finding an integer $x$ such that there is some
integer $y$ for which
$384 \cdot x + 566 \cdot y = 1$.
Since 384 and 566 are even, the LHS must be even, so no integers can
give equality to 1.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 3
\problem
Prove the set identity

\begin{math}
((A-B) \cup (B-A))^{c} = (A^{c} \cup B) \cap (A \cup B^{c})
\end{math}

\solution{
Using the definition of set difference, both of De Morgan's Laws,
and the commutativity of union (in that order):

\begin{tabbing}
$((A-B) \cup (B-A))^{c}$ \= $= ((A \cap B^c) \cup (B \cap A^c))^c$ \\
                         \> $= (A \cap B^c)^c \cap (B \cap A^c)^c$ \\
                         \> $= (A^c \cup B) \cap (B^c \cup A)$ \\
                         \> $= (A^c \cup B) \cap (A \cup B^c)$ \\
\end{tabbing}

Alternatively, one can use the definitions of the operations.  We need
to prove $x$ is in the LHS if and only if it is in the RHS.

$x \in
((A-B) \cup (B-A))^c$ means that $x \notin (A-B) \cup (B-A)$.  This
means that 
$x \notin A-B$ and $x \notin B-A$.  

So consider cases.  If $x \in A$, then certainly $x \in A \cup B^c$.
Furthermore, since by assumption $x \notin A-B$, we must have $x \in
B$.  Thus, $x \in B \cup A^c$.  Putting these together shows $x \in (A
\cup B^c) \cap (B \cup ^c)$.  Now consider the other case.  
If $x \notin A$, meaning $x \in A^c$, then certainly $x \in A^c \cup B$.
Also, (since $x \notin B-A$), we must have $x \notin B$.  That is, $x
\in B^c$.  Therefore, $x \in B^c \cup A$.  Thus, $x \in (A^c \cup B)
\cap (B^c \cup A)$.  

This proves one direction; the other is similar (but you have to include it
in the real quiz!).
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 4
\problem 

Use the following tables to describe the properties of the
various functions.  Write yes or no in each box.  Don't
give proofs (it'd be too hard to squeeze them into the boxes).  
{\bf Pay careful attention} to the specified domains and ranges.

\begin{itemize}
\item $f:\naturals \rightarrow \naturals,\
f(x)=5x$.
\item   $g: \reals^+ \rightarrow \naturals,\ g(x)=\lfloor x \rfloor$.
\item $h: \reals \rightarrow \reals^{+},\ h(x)=e^x$.   
\end{itemize}
Give an inverse if one exists (under the given domain and range).

\smallskip
\begin{tabular}{l|c|c|c|c|}
function & injective & surjective & inverse\\
\hline
$f(x)=5x$ &    \sol{yes}    &   \sol{no}      & \sol{none} \\
\hline
$g(x) = \lfloor x \rfloor$ & \sol{no} & \sol{yes} & \sol{none} \\
\hline
$h(x)=e^x$ & \sol{yes} & \sol{yes} & \sol{ln($x$)} \\
\hline
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 5
\problem 

Consider the following algorithm, which takes natural numbers
$a$ and $b$, with $b > 0$, and returns an ordered pair of natural numbers.
\begin{tabbing}
else \= else \= else \= else \=\kill
Algorithm Div$(a,b)$\\
\\
if $(a<b)$\\
\> return $(0,a)$\\
else\\
\> $(q,r) \leftarrow $Div$(a-b,b)$\\
\> return $(q+1,r)$\\
\end{tabbing}

\begin{problemparts}
\problempart Prove Div terminates in at most $a + 1$ steps.

\solution{
We model the algorithm as a state machine with state $(q,r)$.
The initial state is $(a,b)$.  Termination occurs when the termination 
condition $(a<b)$ is reached.  

We define the derived variable $f(q,r) = q$. It is seen that $f$ is 
non-negative.  Furthermore, $f$ is decreasing because then next value
of $q$ at each step is $a-b$, where by ``step'' I mean a recursive call
to Div.
  Therefore, termination occurs in at most
$a$ steps (+1 for the last iteration).
}
%We use strong induction on $a$.  The inductive hypothesis is``if Div$(a',b)$
%terminates for all $a'<a$, then Div$(a,b)$ terminates''.

%Base Case: $a < b$.  Then Div returns immediately (that is, in one step),
%which is certainly no more than $a + 1$ steps, since $ a \geq 0$.

%Inductive step:  $a \geq b$.  Then $0 \leq a - b < a$, since $b > 0$.
%In this case, there is a recursive call Div$(a-b,b)$.  
%By the IH, this recursive call returns in at most $a - b +1$ steps.
%Since $a - b < a$, this is at most $a + 1$ steps.

\problempart
Prove that Div returns the quotient and remainder of $a$ on
division by $b$.

\solution{
Recall that the quotient and remainder of $a$ on division by $b$
are defined to be the unique integers $q$ and $r$ such that
$a = qb + r$ and $0 \leq r < b$.  These integers must exist
by the Division Algorithm.

We use strong induction on $a$.

Base case: $a < b$.  Then Div immediately returns (0, $a$).
Since $a = 0 \cdot b + a$ and $0 \leq a < b$, these are
the quotient and remainder of $a$ on division by $b$.

Inductive step: $a \geq b$.  Then $0 \leq a - b < a$.
In this case, there is a recursive call Div$(a-b,b)$.  
By the IH, this recursive call returns the quotient and remainder
of $a - b$ on division by $b$.  So $a - b = qb + r$ and $0 \leq r < b$.
Then $a = (q + 1)b + r$ and $0 \leq r < b$.
So $q + 1$ and $r$ are the quotient and remainder of $a$ on division by $b$,
and these are returned by Div.
}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 6
\problem 

David is located at position $(1,0)$ on the two-dimensional
$({\Bbb Z} \times {\Bbb Z})$ $x$-$y$ plane.  His house is located at
the origin.  David wants to go home.  But it is windy, and each time David
takes a one-unit step east or west, he also gets blown a one-unit step
north or south (he can pick which).

\begin{tabular}{c|c|c|c|c|c|c|cc} 
\multicolumn{3}{r|}{$y$ }\\
\multicolumn{3}{c|}{ }\\
\cline{2-6}
&&&&&\\
\cline{2-6}
&&&&&\\
\cline{2-6}
$x$&&&&&\\
\cline{1-6}
&&&&&\\
\cline{2-6}
&&&&&\\
\cline{2-6}
&&&&&\\
\cline{2-6}
\multicolumn{3}{c|}{ }\\
\multicolumn{3}{c|}{ }\\
\end{tabular}

\begin{problemparts}
\problempart On the grid above, mark with X's all the points that David
can reach in one step. Mark with O's the points that David can
reach in two steps.  (The axes labeled $x$ and $y$ intersect at David's
house.)

\problempart Give an informal explanation for why David can never get home.

\solution{
David starts off with the sum of his coordinates (1 + 0 = 1) odd.
Every time he moves, the parity of each coordinate changes, so
the sum of his coordinates remains odd.  Since the sum of the coordinates
of his home (0 + 0 = 0) is even, he can never reach it.
}

\problempart Describe a state machine that represents David's motion, and
list its transitions.

\solution{
We introduce state variables $x, y \in {\Bbb Z}$.
We designate exactly one start state:  the one for which $x = 1$ and $y =
0$.

The transitions are $(x,y) \rightarrow (x \pm 1, y\pm1)$.
}

\problempart Prove that David can never get home.

\solution{
We use the following invariant:
$x + y$ is odd for all reachable states.
This is true for the start state (0 + 1 = 1).
For each transition, the sum is modified either by $0$, $-2$,
or $2$.
Thus each transition increases $x + y$ by an even amount 
preserving the invariant.

Since $x + y$ is even for the state corresponding to home,
it is not a reachable state of our state machine.
Thus David can never get home.
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 7
\problem

Consider the following algorithm that takes an array (list) $A[1\ldots n]$ of
numbers such that $A[1]<A[2]<\cdots<A[n]$, and a number $q$, and is
supposed to find $q$ if it is present in the list.

\begin{tabbing}
else \= else\= else\= else \=\kill

Find$(A,n,q)$\\
\\
$i \leftarrow 1$\\
$j \leftarrow n+1$\\
While $(j-i > 1)$\\
\> choose some $k$ with $i<k<j$\\
\> if $A[k] \le q$\\
\>  \> $i \leftarrow k$\\
\> else\\
\>  \> $j \leftarrow k$\\
Return $i$
\end{tabbing}

\begin{problemparts}
\ppart prove this function terminates

\solution{
Define a state machine whose state is $(i,j)$ and the initial state is
$(1,n+1)$. Define the derived variable $f(i,j) = j-i$.
Note that at each step we choose a $k$ such that $i < k < j$, and
either set $j=k$ or $i=k$.  Therefore $f$ is decreasing.
Furthermore $f$ is non-negative since $j>i$.  We conclude that 
the algorithm terminates in at most $n+1-1 = n$ steps.

%We first prove (by induction on $l$) that after the $l$th pass
%through the while loop, $j - i \leq n - l$.

%{\bf Base Case:} $l = 0$.  When we first reach the while loop, $j - i = n$
%because we just set $i$ to 1 and $j$ to $n + 1$.

%{\bf Inductive Step:}  By the IH, $j - i \leq n - l$ after the $l$th pass
%through the while loop.  During the ($l + 1$)st pass, either $i$ or
%$j$ is moved to a value (that of $k$) strictly between their values
%from the end of the $l$th pass.  Thus the ($l + 1$)st pass decreases
%$j - i$ by at least 1.  So after the ($l + 1$)st pass through the
%while loop, $j - i < n - l - 1 = n - (l + 1)$.
}

\end{problemparts}

Now suppose that $q=A[r]$ for some $r$. 

\begin{problemparts}
\ppart State an invariant of the while loop relating
$i,j$, and $r$.  The invariant should be ``obviously provable by
induction'' but you need not prove it.

\solution{
Our invariant is $i \leq r < j$.
}

\ppart Assuming the invariant, prove that Find returns $r$.

\solution{
When the loop terminates, $j - i \leq 1$ (from $j \leq i + 1$).
Also, the invariant still holds.
So $i \leq r < j \leq i + 1$.  Since $i$ and $r$ are integers, $i = r$.
Since $i$ is then returned, Find returns $r$.
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 8
\problem

An infinite sequence of natural numbers $a_1, a_2, a_3$, \ldots is
defined in such a way that $a_1 = 14, a_2 = 35$, and each later
$a_i$, $i \geq 3$, is obtained using one of the following rules:\\

{\bf Rule A} Choose any two preceding elements of the sequence and define $a_i$
to be their sum. \\

{\bf Rule B} Choose any number $k \geq 1$ of preceding elements of the sequence,and define $a_i$ to be their product divided by $7^{k-1}$. \\

Use the well-ordering principle to prove that every element in the
sequence is a  multiple of $7$. 
({\it Hint:  In case you have forgotten, the well-ordering principle says
that every nonempty set of naturals has a smallest element.})

\solution{
\begin{proof}
Let $S =$ \{all elements in the sequence that are not multiples of $7$ \}. \\
Assume that $S$ is nonempty.  Then, by well-ordering, it has a smallest 
element $a_{n}$. \\
If  $a_{n}$ is obtained by rule A,  then $a_{n} = a_{i} +  a_{j}$ 
for some  $a_{i}$ and $a_{j}$ smaller than $a_{n}$. But then  $a_{i}$ and
$a_{j}$ are multiples of $7$ therefore $a_{n}$ has to be a multiple of $7$
also. \\
If  $a_{n}$ is obtained by rule B, then there are $k$ smaller elements
in the sequence ,that are multiples of $7$, so we can write them in the form
$a_{k} = 7n_{k}$. $a_{n}$ is the product of the $a_k$
divided by $7^{k-1}$.  Then we can write \\

\begin{displaymath}
a_{n} = (\prod_{i=1}^{k} (7n_{i}))/7^{k-1} = 7(\prod_{i=1}^{k} n_{i})
\end{displaymath}

Therefore $a_{n}$ is also a multiple of $7$.
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 9
\problem

Prove that among any set of 150 natural numbers, there must be three
numbers, $a$, $b$, and $c$, such that all the pairwise differences,
$a-b, a-c, b-c, b-a, c-a, c-b$, are multiples of 70.

\solution{
\begin{proof}
Use Pigeonhole. \\
{\bf Pigeons} The 150 numbers. \\
{\bf Holes} The natural numbers mod $70$. \\
There is some hole with $ \ceil{\frac{150}{70}} = 3$ pigeons, that is, 
three numbers $a,b,c$ that are equivalent modulo $70$. Then their differences
are equivalent to $0$ modulo $70$, therefore they are divisible by $70$.
\end{proof}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 10
\problem

For each of the following sets, either use diagonalization to prove
that the set is uncountable, or else use dove-tailing or another
technique to show that the set is countable. \\
(If an answer to one part of the question follows from an answer you
have already given to another part, then you need only indicate this
-- you don't need to give a direct proof of the part that follows.) \\

\bparts
\ppart The set $E$ of all the even natural numbers.

\solution{
This set is countable.  The function $f(n) = 2n$ is a bijection from $\naturals$to $E$.
}

\ppart The set of all subsets of $E$.

\solution{
This set is uncountable. Suppose, for the purposes of contradiction,
that it is countable and let $A_1,A_2,\ldots$ be an ordering of the
subsets.  Note that then there is a bijection from $E$ to the set of
subsets of $E$ that sends the natural number $2i$ to the set $A_i$.
Let $S$ be the subset of $E$ defined by
$S = \{2i \in E | 2i \not\in A_i \}$.  Let $n$ be the integer to which
$S$ corresponds under the established bijection.
Note that if $2n$ is in $S$, then  it is not in $E$ which is a contradiction.
If it is not in $S$, then $2n$ should be in $S$ by the definition of $S$, so
we also have a contradiction.  We conclude that the set of subsets of $E$
is uncountable.
}

\ppart The set of all finite subsets of $E$. 

\solution{
Let $S_{i} =$ { The set of all subsets of E with $i$ elements. } 
Each of the $S_{i}$ is countable and the set under question  is the countable 
union of all the $S_{i}$, therefore it is countable. 
}

\ppart The set of all even-size finite subsets of $E$.

\solution{
This set is countable, being a subset of the set in part (c).
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 11
\problem 

Give tight ($\Theta$) bounds for 

$$ \sum_{i=1}^n \frac{1}{\sqrt{i}}$$

You do not need to prove your answer formally, but you should show how you
derived it.

\solution{
We use the integration method for bounding summations.\\
\begin{eqnarray*}
{\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\
{\displaystyle 2x^{\frac{1}{2}}|_1^n} & \leq  {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\
2\sqrt{n} - 2 & \leq {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} & \leq 2\sqrt{n} - 1 \\
%{\displaystyle \lim_{n \rightarrow \infty} \frac{2\sqrt{n} - 2}{\sqrt{n}}} & \%leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1}{\sq%rt{i}}}{\sqrt{n}}} & \leq 1 + {\displaystyle \lim_{n \rightarrow \infty} \frac%{2\sqrt{n} - 1}{\sqrt{n}}} \\
%2 & \leq {\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^n \frac{1%}{\sqrt{i}}}{\sqrt{n}}} & \leq 2 \\
\end{eqnarray*}

That is 
\[ {\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}} = \Theta(\sqrt{n}).\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 12
\problem 

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $O$, $\Omega$, $\Theta$, $o$ or $\omega$, depending
on whether $f(n)= O(g(n))$, $f(n) = \Omega(g(n))$, $f(n) =
\Theta(g(n))$, $f(n) = o(g(n))$ or $f(n) = \omega(g(n))$. If there is
more than one relation between $f(n)$ and $g(n)$, write only the
strongest one (a relation $X$ is stronger than another relation $Y$ if
$X$ implies $Y$ but the converse does not hold). The first line is an
example solution. Note: $\lg n = \log_2 n$.\\ 
\
\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\begin{array}{rcrl}
2n         &=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (n) \\
&&&\\
\lg (n^3)  &=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (\lg n)\\
&&&\\
n!         &=& \stackrel{\sol{\textstyle \omega}}{\blank} & (4^n)\\
&&&\\
2^{\log_3 n} &=& \stackrel{\sol{\textstyle o}}{\blank} & (n^2)\\
&&&\\
\sum_{i=1}^{n}{1/i} &=& \stackrel{\sol{\textstyle \omega}}{\blank} & (1)\\
&&&\\
n^{4.01}   &=& \stackrel{\sol{\textstyle \omega}}{\blank} & (n^4 \lg n)\\
&&&\\
\sum_{i=n}^\infty {1/{i^2}} &=& \stackrel{\sol{\textstyle o}}{\blank} & (1)\\
&&&\\
{n \choose 10}&=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (n^{10}) \\
&&&\\
8^{\lg n}  &=& \stackrel{\sol{\textstyle \Theta}}{\blank} & (n^3)
\end{array}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem 13
\problem
Find asymptotic bounds for the following recurrences. You may assume
that $T(n)= \Theta(1)$ for $n \leq 1$ in each part.

\bparts

\ppart $T(n)= 2T(\floor{n/2})+\Theta(n)$

\solution{
$h(n) = \floor{n/2}-n/2$.
$2(\frac{1}{2})^p = 1 \Rightarrow p = 1$. Hence we have that\\

\begin{displaymath}
T(n) = \Theta(x(1+ \int_{1}^{x} \frac{u\,du}{u^2})) = \Theta(x(1+\ln x)) =
\Theta(x\ln x)
\end{displaymath}
}

\ppart $T(n) = 4T(\floor{n/2+ \sqrt n})+ \Theta(n^2)$

\solution{
$h(n) = \floor{n/2+ \sqrt n} - n/2$.
$4(\frac{1}{2})^p = 1 \Rightarrow p = 2$. Hence we have that\\

\begin{displaymath}
T(n) = \Theta(x^2(1+ \int_{1}^{x} \frac{u^2\,du}{u^3})) = \Theta(x^2(1+\ln x)) =\Theta(x^2\ln x)
\end{displaymath}
}

\ppart $T(n) = T(\lceil n/3 \rceil)+2T(\floor{n/4})+\Theta(n)$\\

\solution{
We rewrite the recurrence as $T(n) = T(n/3 + (\lceil n/3 \rceil - n/3))
+ 2T(n/4 + (\floor{n/4} -n/4)) + \Theta(n)$. By taking logs on both
sides of $(\frac{1}{3})^p + 2(\frac{1}{4})^p = 1$ and simplifying, we
get $p = \frac{\ln 2}{\ln 12} < 1$. Hence we have that\\

\begin{displaymath}
T(n) = \Theta(x^p(1+ \int_{1}^{x} \frac{u\,du}{u^{p+1}})) =
\Theta(x^p(1+x^{1-p})) = \Theta(x)
\end{displaymath}
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 14
\problem

In the following problem there is no direct connection between the two parts.\\

\bparts 

\ppart Suppose that each pair of a genetically engineered species of
rabbits left on an island produces two new pairs of rabbits at the age
of one month and six new pairs of rabbits at the age of two months and
every month afterwards. None of the rabbits ever die or leave the
island.  Find a recurrence relation for the number of {\em pairs} of
rabbits on the island $n$ months after one newborn pair is left on
the island. Do not solve the recurrence relation.

\solution{
Let $N(t)$ be the number of pairs of rabbits after $t$ months. Then
$N(0)=1$, $N(1)=3$, and we have that, for $t \geq 2$:\\
\begin{displaymath}
N(t) = 7N(t-2) + 3(N(t-1)-N(t-2)) = 3N(t-1) + 4N(t-2)
\end{displaymath}
}

\ppart Solve the following inhomogeneous recurrence relation:

\begin{displaymath} 
f(n) = 6f(n-1)-9f(n-2) +2^n, n \geq 2
\end {displaymath}

\solution{
The initial conditions are $f(0) = 5, f(1) = 26$.

The characteristic equation $r^2-6r+9$ has a repeated root $\alpha =
3$. Hence the homogeneous solution has the form $f_h(n) = A3^n+Bn3^n$,
for some constants $A$ and $B$. To find a particular solution, we try
$f_p(n) = K2^n$. Plugging into the difference equation gives:

\begin{math}
K2^n = 6K2^{n-1} -9K2^{n-2}+2^n \Rightarrow K = \frac{6K}{2} - \frac{9K}{4} +1\\\Rightarrow 4K= 12K-9K+4 \Rightarrow K = 4\\
\end{math}

Hence the complete solution has the form $f(n) = A3^n+Bn3^n +2^{n+2}$.
We now use the initial conditions to solve for $A$ and $B$:

\begin{math}
f(0) = 5 = A+4 \Rightarrow A = 1\\
f(1) = 26 = 3 + 3B +8 \Rightarrow B = 5\\
\end{math}

Hence the solution is $f(n) = 3^n + 5n3^n + 4 \cdot 2^n, n \geq 2$.
}
\eparts

\end{problems}
\end{document}
