\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

\problem 

Zork, Inc. - the makers of the Fritolator on planet Xoros 19 - are in dire
financial straits after discovering that their test Fritolator can never 
rendezvous with Earth.  Therefore, Zork has made a pact with Grzzwk Bush, 
the president of Xoros 19.  Since Mr. Bush foolishly wasted most of his 
military revenue on Fritolators, Zork has offered to recycle the Fritolators
into ships for an intergalactic fleet.  \\
Each day, Zork's recycling plant can yield one destroyer, one battleship, or
one cruiser from 2 Fritolators, or it can yield a scout ship or a transport
ship from one Fritolator. \\
We are concerned with the number of $construction$ $histories$ that can be
created by the Zork plant.  For example, with 2 Fritolators, there are 
seven possible histories:

\[
	{(destroyer),(battleship),(cruiser),}
\]
\[
	{(scout,scout), (scout, transport), (transport, scout), (transport,transport)}
\]

\begin{problemparts}

\problempart Express as a recurrence the number of different possible 
construction histories with $n$ Fritolators.\\

{\bf Solution:} $x_{n} = 2 x_{n-1} + 3 x_{n-2} \quad (x_1 = 2, x_2 = 7)$

\problempart Express this recurrence in closed form.\\

{\bf Solution:}\\
The characteristic equation is $r^2 - 2 r - 3 = 0$.  So the roots are:
\begin{eqnarray*}
r_1 & = & -1 \\
r_2 & = & 3
\end{eqnarray*}
So we guess a solution of the form:
\begin{eqnarray*}
x_n & = & c_1 (-1)^n + c_2 3^n
\end{eqnarray*}
Then, if we substitute in the initial conditions, we get the following two equations:
\begin{eqnarray*}
-c_1 + 3 c_2 & = & 2 \\
c_1 + 9 c_2 & = & 7
\end{eqnarray*}

So we see that the solution is $c_1 = \frac{1}{4}$ and $c_2 = \frac{3}{4}$.
Substituting these into the expression for $x_{n}$ yields:
\begin{eqnarray*}
x_n & = & \frac{1}{4} \cdot (-1)^n + \frac{3}{4} \cdot 3^n
\end{eqnarray*}

\problempart Suppose now that Mr. Bush has a meeting with his chief space
travel consultant, Mr. Inhomogeneous.  Inhomogeneous says that if the Zork
recycling plant agrees to produce only scout ships, then he and his colleagues
will show Zork how to create a superdestroyer, yet another type of ship. 
Mr. Bush, sold on the idea of the superdestroyer, tries to convince the Zork
plant to produce only scout ships. (``Read my lips, no more Earth.'')  \\

However, Zork is unimpressed.  If no Fritolators are required to produce a 
superdestroyer, and the superdestroyer can only be produced {\bf after} all
scout ships have been produced, how many construction histories are possible
with $n$ Fritolators? \\
($Note:$ If Zork produces all scout ships, it has the option to build the
superdestroyer.)\\

{\bf Solution:} $x_{n} = 2 x_{n-1} + 3 x_{n-2} +1 \quad (x_1 = 3, x_2 = 8)$\\

This solution comes about because the superdestroyer applies only to one 
possible history (the one where all scout ships are produced).  Since Zork
can either produce or not produce the superdestroyer, one possible history
is added for any value of $n$.

\problempart Express the recurrence you obtained in part (c) in closed form.\\

{\bf Solution:}\\
Since the recurrence is inhomogeneous, we must obtain homogeneous and 
inhomogeneous solutions and add them.  We know from part (b) that the 
solution to the associated homogeneous recurrence is:
\begin{eqnarray*}
x_n & = & c_1 (-1)^n + c_2 3^n
\end{eqnarray*}

Next, we need to guess a solution to the associated homogeneous recurrence.
Since the inhomogeneous term is constant, we should pick a guess of the form:
\begin{eqnarray*}
x_n & = & an + b
\end{eqnarray*}

Substituting into the recurrence, we get:
\begin{eqnarray*}
an + b & = & 2 (a(n-1) + b) + 3 (a(n-2) + b) + 1 \\
       & = & 2an - 2a + 2b + 3an - 6a + 3b + 1 \\
       & = & 5an - 8a + 5b + 1 \\
0      & = & 4an - 8a + 4b + 1
\end{eqnarray*}

The final equation holds if $a = 0$ and $b = -\frac{1}{4}$.  So we now have a
particular solution for the recurrence:
\begin{eqnarray*}
x_n & = & -\frac{1}{4}
\end{eqnarray*}

So the entire solution to the recurrence is the homogeneous solution plus
the particular solution.
\begin{eqnarray*}
x_n & = & c_1 (-1)^n + c_2 3^n - \frac{1}{4}
\end{eqnarray*}

Finally, we need to find values for $c_1$ and $c_2$.  Plugging in the initial
conditions gets us a system of equations:
\begin{eqnarray*}
-c_1 + 3 c_2 - \frac{1}{4} & = & 3 \\
c_1 + 9 c_2 - \frac{1}{4} & = & 8
\end{eqnarray*}

The solution to this system of equations is $c_1 = -\frac{3}{8}$,   
$c_2 = \frac{23}{24}$.  So the final solution to the inhomogeneous recurrence
is:
\begin{eqnarray*}
x_n & = & -\frac{3}{8} \cdot (-1)^n + \frac{23}{24} \cdot 3^n - \frac{1}{4}
\end{eqnarray*}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}

