\documentstyle[12pt,twoside,amsfonts]{article}
\input{macros-course}
\parskip1.5ex
\parindent0pt


\begin{document}
\handout{notes12}{Notes 12}{October 20, 1995}

\section{Linear Recurrences}

We begin with an example.

{\bf Graduate Student Job Prospects Problem:} 


Let's assume that due to
budgetary constraints, there are at most $N$ faculty positions
available.  Every year, each professor graduates one student
who become a professor upon graduation.  Except, first year
professor are too busy and don't graduate any students.
To make matters worse, everyone lives forever and no one retires.

The question that graduate students ask is:  will there be
any positions when I graduate?  That is, when will all the jobs
be filled.

We also impose the boundary condition that in year 1, there is
one professor.
To solve this problem, we will set up a recurrence.

Let $f(n)$ be the number of professors in year $n$.
The first few values are,

$f(0)=0$

$f(1)=1$  (new hire)

$f(2)=1$  (no students yet)

$f(3)=2$  (one new prof)

$f(4)=3$  (2 old, 1 new)

$f(5)=5$  (3 old, 2 new)

For $n\geq 2$, $f(n)=f(n-1)+f(n-2)$.  The Fibanocci recurrence.

We can now define linear recurrence.

\begin{defin}
A recurrence is {\em linear} if it is of the form
\[
f(n)=a_1 f(n-1) + a_2 f(n-2) + \ldots a_d f(n-d) =\sum_{i=1}^d a_i f(n-i)
\]
for fixed constants $a_1$, $a_2$, $a_3$, $\ldots$, $a_d$, and $d$.
\end{defin}

\begin{defin}
The {\em order} of the recurrence is $d$.
\end{defin}

(e.g., the Fibanocci recurrence has order 2)

\section{Solving the Recurrence}
Let's try the guess and verify method.

{\em Guess:}  $f(n)= \alpha^n$ for constant $\alpha$.

{\em Verify:} 
\begin{eqnarray*}
 & f(n)  =  f(n-1)+f(n-2) \\
\Longrightarrow & \alpha^n = \alpha^{n-1} +\alpha^{n-2} \\
\Longrightarrow & \alpha^2 =  \alpha +1 \\
\Longrightarrow & \alpha^2 -  \alpha -1 =0\\
\Longrightarrow & \alpha = \frac{1\pm \sqrt{5}}{2}
\end{eqnarray*}

So, we have two possible solutions:
$f(n) = \alpha_1^n$ and $f(n)=\alpha_2^n$ where
$\alpha_1,\alpha_2 =\frac{1\pm \sqrt{5}}{2}$.

In fact, any linear combination is a solution.

\begin{theorem}
If $f(n)=\alpha_1^n$ and $f(n)=\alpha_2^n$ are two solutions
to a linear recurrence (without boundary conditions), then 
$f(n) = c_1 \alpha_1^n +c_2 \alpha_2^n$ is also a solution for
any constant $c_1$ and $c_2$.
\end{theorem}

\begin{proof}
\[
\alpha_1^n \mbox{ is a solution } \Longrightarrow
\alpha_1^n = \sum_{i=1}^d a_i \alpha_1^{n-i}
\]

\[
\alpha_2^n \mbox{ is a solution } \Longrightarrow
\alpha_2^n = \sum_{i=1}^d a_i \alpha_2^{n-i}
\]

Thus,
\[
c_1 \alpha_1^n + c_2 \alpha_2^n = \sum_{i=1}^d a_i (c_1 \alpha_1^{n-i}
+ c_2 \alpha_2^{n-i})
\]

So,
\[
f(n) =  \sum_{i=1}^d a_i f(n-i) 
\]
\end{proof}

Thus, we know the solution to the Fibanacci recurrence
is
\[
f(n) = c_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n
+c_2 \left(\frac{1 - \sqrt{5}}{2}\right)^n
\]

To determine the constants, we use the boundary conditions.
\[
f(0)=0 = c_1 +c_2
\]
\[ 
f(1) = 1 = c_1 \left(\frac{1 + \sqrt{5}}{2}\right)
+c_2 \left(\frac{1 - \sqrt{5}}{2}\right)
\]

Thus, $c_1 = 1/\sqrt{5}$ and $c_2 = -1/\sqrt{5}$.
Surprisingly, the above formula gives the Fibanocci numbers, which is
a non-obvious result.  In fact, it isn't even clear the above
number is always an integer.

To answer our original question,
we want the smallest $n$ such that $f(n) \geq N$.
Observe that $\left(\frac{1 - \sqrt{5}}{2}\right) <1$, so
any powers of it are also less than 1.  For large
values of $n$, this term will becomes very close to zero, and thus
the first term converges to the $nth$ Fibanocci number.
Even for small values of $n$, the first term will give us the
answer to within 1.

\[
\frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n \geq N 
\Longrightarrow n\geq \frac{\log (\sqrt{5} N)}{\log\left(\frac{1 + \sqrt{5}}{2}\right)} = \Theta(\log N)
\]

For numerical values of $N$, we can give accurate answers.  For
$N=20,000$, we have $n=21$.  In general, we are most interested in
asymptotics.  In that case, the jobs will be filled in $\Theta(\log N)$
years.

\section{Solving General Recurrences}
For an arbitrary $dth$ order linear recurrence,
\[
f(n)= \sum_{i=1}^d a_i f(n-i) \]

{\em Guess:}  $f(n) = \alpha^n$ for some $\alpha$

{\em Verify:}
\begin{eqnarray*}
 & f(n)  =  \sum_{i=1}^d a_i f(n-i) \\
\Longrightarrow & \alpha^n = \sum_{i=1}^d a_i \alpha^{n-i} \\
\Longrightarrow & \alpha^d = \sum_{i=1}^d a_i \alpha^{d-i} \\
\Longrightarrow & \alpha^d - a_1 \alpha^{d-1}- a_2 \alpha^{d-2} - \ldots
a_d =0  
\end{eqnarray*}

This last equation is called {\em the characteristic equation.}
In general, this equation will have $d$ roots.
If all the roots are distinct, the
solution will be
\[
f(n) = c_1 \alpha_1^n +c_2 \alpha_2^n  +\ldots +c_d \alpha_d^n
\]

We determine the $c_i$ by using the boundary conditions.
We need $d$ equations to find a unique solution.

If the roots are repeated, we need to modify our solutions.
If a root, $\alpha$, is repeated $r$ times, then the solutions look like
\[
\alpha^n, n\alpha^n, n^2\alpha^n, \ldots, n^{r-1}.
\]

We will verify this for the case $r=2$. (i.e. $n\alpha^n$ is a solution)
Note that if $\alpha$ is a double root of the characteristic equation,
then let $g(x) = (x^d - a_1 x^{d-1}- a_2 x^{d-2} - \ldots
a_d)x^{n-d}$, then 
\begin{eqnarray*}
& g(x)= (x-\alpha)^2 h(x) \\
\Longrightarrow & g'(x) = 2(x-\alpha) h(x) + (x-\alpha)^2 h'(x)
\end{eqnarray*}

Thus, $g'(\alpha) =0$.  Therefore,
\begin{eqnarray*}
& n\alpha^{n-1} -\sum_{i=1}^d a_i (n-i) \alpha^{n-i-1} =0\\
\Longrightarrow & n\alpha^n = \sum_{i=1}^d a_i (n-i) \alpha^{n-i}
\end{eqnarray*}
which shows that $n\alpha^n$ is a solution.

Example:
We have a plant that lives forever.  It produces one offspring the first year of
its life and nothing in the future.  If we start with one new plant in year 1, how
many plants will we have in year $n$?

Recurrence:
\[
f(n) = f(n-1) + (f(n-1)+f(n-2)) = 2f(n-1) - f(n-2)
\]

At year $n$, we have the plants from last year plus
the one new plant for each first year plant.

Boundary conditions:
$f(0)=0$, $f(1) = 1$.

Characteristic equation:
$\alpha^2 -2\alpha+1 =0$.

Roots:  $\pm 1$.

Solution: $c_1 + c_2 n$

Using boundary conditions, we get $f(n) = n$.

Recurrences  of the form
\[
f(n)- \sum_{i=1}^d a_i f(n-i) =0\]
are called homogeneous recurrences.
We next study inhomogeneous recurrences.

\section{Inhomogeneous Recurrences}
Inhomogeneous recurrences look like
\[
f(n)- \sum_{i=1}^d a_i f(n-i) = g(n)
\]

The general method is to do the following:
\begin{enumerate}

\item Solve the homogeneous solution by setting $g(n)=0$.

\item Find a particular solution.

\item Add the two together and use the boundary conditions to
determine the coefficients of the constant factors.
\end{enumerate}

For those who have taken 18.03, this is similiar to solving differential
equations.

Example:  $f(n) = 4 f(n-1) + 3^n$; $f(1)=1$

Homogeneous solution:  $f(n) - 4f(n-1) =0$.  $\alpha = 4$.  $f(n)=c 4^n$

Particular solution:  Guess $f(n)=k3^n$
\begin{eqnarray*}
k 3^n & = & 4k3^{n-1} + 3^n \\
3k & = & 4k +3 \\
k& = & -3
\end{eqnarray*}
Particular solution: $f(n)=-3^{n+1}$

Combine solutions:  $f(n)=c 4^n-3^{n+1}$.

Boundary conditions imply $f(n) = \frac{5}{2} 4^n -3^{n+1}$.

Another example: $f(n) = 4f(n-1)-4f(n-2) +n$; $f(0)=4$, $f(1)=7$

Homogeneous solution:  $f(n) - 4f(n-1) +4f(n-2)=0$.  $\alpha = 2,2$ (double root).  
$f(n)=c_1 2^n + c_2 n 2^n$

Particular solution:  Guess $f(n)=an+b$
\begin{eqnarray*}
an+b & = & 4(a(n-1)+b) - 4(a(n-2)+b) +n \\
an+b & = & n+4a \\
\end{eqnarray*}
Thus, $a=1$, $b=4$.

Particular solution: $f(n)=n+4$

Combine solutions:  $f(n)=c_1 2^n + c_2 n 2^n + n+4$.

Boundary conditions imply $f(n) = n 2^n + n+4$.

When guessing a particular  solution, it makes sense
to guess a solution that is the same type as $g(n)$.
If $g(n)$ is an $r$-degree polynomial, guess an
$r$-degree polynomial (i.e., $ax^r+bx^{r-1}+\ldots+d$).
If $g(n)$ is an exponential, guess an exponential(e.g., if $g(n) = k^n$, guess $ck^n$).

\end{document}
