\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}
\begin{document}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

%\newcommand{\solution}[1]{}
%\pset{6}{October 15, 1998}{Start of class on October 20, 1998}

\newcommand{\solution}[1]{\bigskip #1}
\psol{6}{October 23, 1998}

%\centerline{\bf Read sections 5.1 and 5.2 in Rosen.}

\begin{problems}

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

\problem Find closed-form solutions to the following homogenous linear
recurrences.

\begin{problemparts}
\problempart $x_{n} = 5 x_{n-1} - 6 x_{n-2} \quad (x_0 = 0, x_1 = 1)$

\solution{ The characteristic equation is $r^2 - 5 r + 6 = 0$.  The
roots can be found with the quadratic formula:

\begin{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 3
\end{eqnarray*}

This implies a solution of the form

\begin{eqnarray*}
x_n & = & A 2^n + B 3^n.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations:

\begin{eqnarray*}
0 & = & A + B \\
1 & = & 2 A + 3 B
\end{eqnarray*}

The solution to this system is $A = -1$ and $B = 1$.  Therefore, the
final solution to the recurrence is

\begin{eqnarray*}
x_n & = & 3^n - 2^n.
\end{eqnarray*}
}

\problempart $x_{n} = 5 x_{n-1} - 8 x_{n-2} + 4 x_{n-3} \quad
	(x_0 = 1, x_1 = 2, x_2 = 3)$

\solution{ The characteristic equation is $r^3 - 5 r^2 + 8 r - 4 = 0$.
Solving a cubic equation can be messy process, but in this case the
roots are easy to find:

\begin{eqnarray*}
r_1 & = & 2 \\
r_2 & = & 2 \\
r_3 & = & 1
\end{eqnarray*}

The general form of the solution is therefore

\begin{eqnarray*}
x_n & = & A 2^n + B n 2^n + C.
\end{eqnarray*}

Substituting the initial conditions into this general form gives a
system of linear equations.

\begin{eqnarray*}
1 & = & A + C \\
2 & = & 2 A + 2 B + C \\
3 & = & 4 A + 8 B + C
\end{eqnarray*}

The solution to this linear system is $A = 2$, $B = -\frac{1}{2}$, and
$C = -1$.  The complete solution to the recurrence is therefore

\begin{eqnarray*}
x_n & = & 2^{n+1} - n 2^{n-1} - 1.
\end{eqnarray*}
}

\end{problemparts}

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

\problem Find closed-form solutions to the following inhomogenous
linear recurrences.

\begin{problemparts}

\problempart (Fibonacci Plus) $x_{n} = x_{n-1} + x_{n-2} + 1 \quad
(x_0 = 0, x_1 = 1)$

\solution{ First, we find the general solution to the homogenous
recurrence.  The characteristic equation is $r^2 - r - 1 = 0$.  The
roots of this equation are:

\begin{eqnarray*}
r_1	& = &	\frac{1 + \sqrt{5}}{2} \\
r_2	& = &	\frac{1 - \sqrt{5}}{2}
\end{eqnarray*}

Therefore, the solution to the homogenous recurrence is of the form

\begin{eqnarray*}
x_n	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n.
\end{eqnarray*}

Next, we need a particular solution to the inhomogenous recurrence.
Since the inhomogenous term is constant, we guess a linear solution.

\begin{eqnarray*}
an + b	& = &	a(n-1) + b + a(n - 2) + b + 1 \\
	& = &	2an - 3a + 2b + 1 \\
0	& = &	an - 3a + b + 1
\end{eqnarray*}

This equation holds if we set $a = 0$ and $b = -1$.  Therefore, the
inhomogeous recurrence has the simple particular solution $x_n = -1$.
The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1
\end{eqnarray*}

All that remains is to find the constants $A$ and $B$.  Substituting
the initial conditions gives a system of linear equations.

\begin{eqnarray*}
0	& = &	A + B - 1 \\
1	& = &	A \left( \frac{1 + \sqrt{5}}{2} \right) +
		B \left( \frac{1 - \sqrt{5}}{2} \right) - 1
\end{eqnarray*}

The solution to this linear system is:

\begin{eqnarray*}
A	& = &	\frac{5 + 3 \sqrt{5}}{10} \\
B	& = &	\frac{5 - 3 \sqrt{5}}{10}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
x_n	& = &	\left( \frac{5 + 3 \sqrt{5}}{10} \right) \cdot
			 \left( \frac{1 + \sqrt{5}}{2} \right)^n +
		\left( \frac{5 - 3 \sqrt{5}}{10} \right) \cdot
			B \left( \frac{1 - \sqrt{5}}{2} \right)^n - 1.
\end{eqnarray*}
}

\problempart $x_{n} = 3x_{n-1} - 2 x_{n-2} + n \quad (x_0 = 0, x_1 = 1)$

\solution{
First, we find the general solution to the homogenous recurrence.  The
characteristic equation is $r^2 - 3r + 2 = 0$.  The roots of this
equation are $r_1 = 1$ and $r_2 = 2$.  Therefore, the general solution
to the homogenous recurrence is

\begin{eqnarray*}
x_n & = & A + B 2^n.
\end{eqnarray*}

Now we must find a particular solution to the recurrence, ignoring the
boundary conditions.  Since the inhomogenous term is linear, we guess
a solution that is quadratic:

\begin{eqnarray*}
an^2+bn+c	& = &	3(a(n-1)^2+b(n-1)+c) - 2(a(n-2)^2+b(n-2)+c) + n \\
		& = &	an^2+2an-5a+bn+b+c+n \\
0		& = &	2an - 5a + b + n
\end{eqnarray*}

This equation is solved by setting $a = -\frac{1}{2}$ and $b =
-\frac{5}{2}$.  Apparently, any value of $c$ gives a valid particular
solution; for simplicity, we choose $c = 0$.  Therefore, the
particular solution is:

\begin{eqnarray*}
x_n	& = &	-\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

The complete solution to the recurrence is the homogenous solution
plus the particular solution:

\begin{eqnarray*}
x_n	& = &	A + B 2^n -\frac{1}{2}n^2 - \frac{5}{2} n
\end{eqnarray*}

Substituting the initial conditions gives a system of linear
equations:

\begin{eqnarray*}
0	& = &	A + B \\
1	& = &	A + 2 B - 3
\end{eqnarray*}

The solution to this linear system is $A = -4$ and $B = 4$.
Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
x_n	& = &	2^{n+2} -\frac{1}{2}n^2 - \frac{5}{2} n - 4.
\end{eqnarray*}
}

\end{problemparts}

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

\problem The 6.042 staff recently received the following email.

\begin{verbatim}
From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: Pset 5 issue

Thank you for contributing the MergeSortX19 algorithm to our
``intellectually challenged'' society.  My, my-- we feel mentally
bloated by this sudden infusion of technological wizardry!

As a token of thanks, we launched a Doritofier missile on a straight
line toward Earth.  Suppose that p(t) denotes the distance between
Xoros 19 and the Doritofier after t days of flight.  At the moment of
launch, the Doritofier was here on Xoros 19, and so p(0) = 0.  After a
single day, the Doritofier had already traveled 100 units toward
Earth, so p(1) = 100.  In general, the position of the missle is given
by the following recurrence:

       p(t+1) = 1.99 * p(t) - p(t-1)

Earth happens to be 1010 units from Xoros 19.  Gotta run!  Seeya!

/Grzzwk
\end{verbatim}

\begin{problemparts}

\problempart Find a closed-form solution to the recurrence for the
distance between Xoros 19 and the Doritofier after $t$ days of flight.

\solution{ Let $c = 1.99$.  The characteristic equation of Grzzwk's
recurrence is then $r^2 - c r +1 = 0$.  The roots of this equation
are:

\begin{eqnarray*}
r_1	& = &	\frac{c + \sqrt{c^2 - 4}}{2} \\
r_2	& = &	\frac{c - \sqrt{c^2 - 4}}{2} \\
\end{eqnarray*}

Therefore, the general solution to the recurrence is:

\begin{eqnarray*}
p(t)	& = &	A \left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t +
		B \left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t
\end{eqnarray*}

Subtituting the initial conditions into this general form gives a
system of linear equations.

\begin{eqnarray*}
0	& = &	A + B \\
100	& = &	A \left( \frac{c + \sqrt{c^2 - 4}}{2} \right) +
		B \left( \frac{c - \sqrt{c^2 - 4}}{2} \right)
\end{eqnarray*}

The solution to this linear system is

\begin{eqnarray*}
A	& = &	\frac{100}{\sqrt{c^2 - 4}} \\
B	& = &	- \frac{100}{\sqrt{c^2 - 4}}
\end{eqnarray*}

Therefore, the complete solution to the recurrence is

\begin{eqnarray*}
p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
		\left(	\left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t -
		\left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t \right)
\end{eqnarray*}

where $c = 1.99$.  Note that $\sqrt{c^2 - 4}$ is imaginary.
}

\problempart The characteristic equation approach gives a solution to
this recurrence involving complex numbers.  This makes evalutation
awkward.  Give a closed-form solution that does not involve complex
numbers.  DeMoivre's Identity may be helpful:

\begin{eqnarray*}
(\cos \theta + i \sin \theta)^n & = & \cos n \theta + i \sin n \theta
\end{eqnarray*}

\solution{
We start with the solution obtained previously.

\begin{eqnarray*}
p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
		\left(	\left( \frac{c + \sqrt{c^2 - 4}}{2} \right)^t -
		\left( \frac{c - \sqrt{c^2 - 4}}{2} \right)^t \right)
\end{eqnarray*}

Note that

\begin{eqnarray*}
\frac{c + \sqrt{c^2 - 4}}{2}
	& = &	\frac{c}{2} + i \cdot 
			\sqrt{1 - \left(\frac{c}{2}\right)^2} \\
	& = &	\cos \theta + i \sin \theta
\end{eqnarray*}

where $\theta = \arccos \frac{c}{2}$.  With this substitution, we can
eliminate complex numbers from the solution.

\begin{eqnarray*}
p(t)	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot \left(
		\left(\cos \theta + i \sin \theta \right)^t -
		\left(\cos \theta - i \sin \theta \right)^t
		\right) \\
	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot \left(
		\left(\cos t \theta + i \sin t \theta \right) -
		\left(\cos t \theta - i \sin t \theta \right)
		\right) \\
	& = &	\frac{100}{\sqrt{c^2 - 4}} \cdot
		\left( 2 i \sin t \theta \right) \\
	& = &	\frac{100}{\sqrt{1 - \left(\frac{c}{2}\right)^2}} \cdot
		\left( \sin t \theta \right) \\
	& = &	\frac{100 \sin t \theta}{\sin \theta}
\end{eqnarray*}

The final solution is

\begin{eqnarray*}
p(t)	& = &	\frac{100 \sin t \theta}{\sin \theta}
\end{eqnarray*}

where $\theta = \arccos(\frac{1.99}{2})$.
}

\problempart Does the Doritofier missle hit earth?

\solution{

The solution indicates that the path of the Doritofier is a sine wave
with amplitude

\begin{eqnarray*}
\frac{100}{\sin \theta}
	& = &	\frac{100}{\sin \arccos\left(\frac{c}{2}\right)} \\
	& = &	\frac{100}{\sqrt{1 - \left(\frac{c}{2}\right)^2}} \\
	& = &	\frac{100}{\sqrt{1 - \left(\frac{1.99}{2}\right)^2}} \\
	& = &	1001.253\ldots
\end{eqnarray*}

Since Earth is 1010 units from Xoros 19, we're safe.

\bigskip

On the other hand, since the path of the missle is a sine wave, it
{\em will} be returning to Xorox 19 presently...}

\end{problemparts}


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

\end{problems}
\end{document}

