\documentclass[11pt,twoside]{article}

\usepackage{macros-course-lectures}
\usepackage{graphicx}

\newenvironment{verify}{\par{\noindent\emph{Verification.}\setlength{\parindent}{3ex}}}{\qed}

\newtheorem{guess}[theorem]{Guess}
\newtheorem*{guess*}{Guess}

\begin{document}

\lecture{notes12}{Linear Recurrences}{20 March 2001}



\section{Graduate Student Job Prospects}

In a certain new academic field (say computer science), there are only
so many faculty positions available in all the universities of the
world.  Initially, there were not enough qualified candidates, and
many positions were unfilled.  But, over time, new graduates are
filling the positions, making job prospects for later computer science
students even more bleak.  Worse, the increasing number of professors
are able to train an increasing number of graduate students, causing
positions to fill even more rapidly.  Eventually, the universities
will be saturated; new computer science graduates will have no chance
at an academic career.  Our problem is to determine when the
universities will stop hiring new computer science faculty and, in
particular, to answer the question, ``Are the 6.042 TAs doomed?''
Here are the details of the problem.
\begin{itemize}
\item There are a total of $N$ faculty positions available worldwide.
  This number never changes due to budgetary constraints.
\item Congress has passed a law forbidding forced retirement, and no
  one will retire voluntarily.  (This is true and a problem!)  In our
  analysis, therefore, once a faculty position is filled, it never
  opens up again.
\item Each year, every professor trains exactly 1 student who will go
  on to become a professor the following year.  The only exception is
  that first year professors do not train students; they are too busy
  publishing, teaching, getting grants, and serving on committees.
\item In year 0, there are no computer science professors in the
  world.  In year 1, the first professor is hired.
\end{itemize}

\subsection{Finding a Recurrence}

Ideally, we could find a formula for the number of professors in the
world in a given year.  Then we could determine the year in which all
$N$ faculty positions are filled.  Let $f(n)$ be the number of
professors during year $n$.  To develop some intuition about the
problem, we can compute values of this function for small $n$ by hand.
\begin{eqnarray*}
f(0)=0 &\quad& \mbox{No CS professors; the dark ages.} \\
f(1)=1 &\quad& \mbox{1 new professor; too busy to train a student.} \\
f(2)=1 &\quad& \mbox{1 old professor; now training a student.} \\
f(3)=2 &\quad& \mbox{1 new prof, 1 old prof; new prof too busy, old prof training.} \\
f(4)=3 &\quad& \mbox{1 new prof, 2 old profs; new prof too busy, both old profs training} \\
f(5)=5 &\quad& \mbox{2 new profs, 3 old profs} \\ 
f(6)=8 &\quad& \mbox{3 new profs, 5 old profs} \\ 
\end{eqnarray*}
In general, the number of professors in year $n$ is equal to the
number of professors last year plus the number of new hires.  The
number of professors last year is $f(n-1)$.  The number of new hires
is equal to the number of professors two years ago, $f(n-2)$, since
each of these professors trained a student last year.  These
observations give the following recurrence equation for the number of
professors:
\begin{eqnarray*}
f(n) & = & f(n-1) + f(n-2) \quad \quad (n \geq 2)
\end{eqnarray*}
This is the familiar Fibonacci recurrence.  Looking back, the values
of $f(n)$ that we computed by hand are indeed the first few Fibonacci
numbers.  Fibonacci numbers arise in all sorts of applications.  So
how big is $f(n)$ anyway?  Of course, we could compute as many
Fibonacci numbers as we like using the recurrence, but it would be
much nicer to find a closed form.

{\bf Note:} When Fibonacci introduced this recurrence, the academic
environment was a little bit different.  So he used rabbits instead.
A pair of rabbits takes one year to mature, then starts producing one
pair of rabbits as offspring forever.

\subsection{Solving the Recurrence}

Solving the Fibonacci recurrence is easy because the recurrence is
linear.  (Well, ``easy'' in the sense that you can learn the technique
in one lecture; discovering it actually took six centuries.)
\begin{defin*}
A recurrence is \emph{linear} if it is of the form
\begin{eqnarray*}
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)
\end{eqnarray*}
where $a_1, a_2, \ldots a_d$ are constants.  The \emph{order} of the
recurrence is $d$.
\end{defin*}
For example, the Fibonacci recurrence is order 2 and has $a_1 = a_2 =
1$.

For now, let's try to solve just the Fibonacci recurrence; we'll see
how to solve general linear recurrences later in the lecture.  Our
rule of thumb is that Guess and Verify is the first method to apply to
a recurrence.  It turns out that for a linear recurrence, an
exponential solution is a good guess.  However, since we know nothing
beyond this, our initial Guess and Verify attempt will really only be
a ``dry run''; that is, we will not make an exact guess and will not
verify it with a complete proof.  Rather, the goal of this first
attempt is only to clarify the form of the solution.

\paragraph{Guess:} $f(n) = c \alpha^n$

Here $c$ and $\alpha$ are parameters introduced to improve our odds of
having a correct guess; in the verification step, we can pick values
that make the proof work.  To further improve our odds, for now let's
neglect the boundary conditions, $f(0) = 0$ and $f(1) = 1$.

\begin{verify} \emph{(dry run)}
Plugging our guess into the recurrence $f(n) = f(n-1) + f(n-2)$ gives:
\begin{eqnarray*}
c \alpha^n & = & c \alpha^{n-1} + c \alpha^{n-2} \\
\alpha^2 & = & \alpha  + 1 \\
\alpha^2 - \alpha  - 1 & = & 0\\
\alpha & = & \frac{1 \pm \sqrt{5}}{2}
\end{eqnarray*}
In the first step, both sides of the equation are divided by $c
\alpha^{n-2}$.  The second step only involves rearranging terms.  In
the final step, we can compute $\alpha$ by solving the quadratic
equation.

This calculation suggests that $c$ can be anything, but that $\alpha$
must be $(1 \pm \sqrt{5})/2$.  Evidently, there are two solutions to
the recurrence:
\[
f(n) = c \left( \frac{1 + \sqrt{5}}{2} \right)^n
\quad \quad \mbox{or} \quad \quad
f(n) = c \left( \frac{1 - \sqrt{5}}{2} \right)^n
\]
\end{verify}

There are actually more solutions than suggested by our ``dry run'' of
Guess and Verify; in fact, any linear combination of the above two
solutions is also a solution.  The following theorem states that this
is true in general for linear recurrences.
\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
a_1^n + c_2 a_2^n$ is also a solution for all constants $c_1$ and
$c_2$.
\end{theorem}
\begin{proof}
Every linear recurrence has the following form:
\[
f(n) = \sum_{i=1}^d a_i f(n-i)
\]
We must prove that $f(n) = c_1 \alpha_1^n + c_2 \alpha_2^n$ is a
solution; that is, we must prove:
\[
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})
\]
Substituting the two solutions $f(n) = \alpha_1^n$ and $f(n) =
\alpha_2^n$ into the recurrence gives the following two equations:
\begin{eqnarray*}
\alpha_1^n = \sum_{i=1}^d a_i \alpha_1^{n-i} \\
\alpha_2^n = \sum_{i=1}^d a_i \alpha_2^{n-i} \\
\end{eqnarray*}
Multiplying the first equation by $c_1$, multiplying the second
equation by $c_2$, and adding the two gives the desired result.
\end{proof}
The theorem implies that for all $c_1$ and $c_2$, the following is a
solution to the Fibonacci recurrence without boundary conditions:
\[
f(n) = c_1 \left( \frac{1 + \sqrt{5}}{2} \right)^n +
       c_2 \left( \frac{1 - \sqrt{5}}{2} \right)^n
\]
All that remains is to find a solution that satisfies the boundary
conditions $f(0) = 0$ and $f(1) = 1$.  The first boundary condition
requires that:
\begin{eqnarray*}
& & f(0) = c_1 \left( \frac{1 + \sqrt{5}}{2} \right)^0 +
       c_2 \left( \frac{1 - \sqrt{5}}{2} \right)^0 = 0 \\
& \Rightarrow & c_1 + c_2 = 0
\end{eqnarray*}
Similarly, the second boundary condition requires that:
\begin{eqnarray*}
& & f(1) = c_1 \left( \frac{1 + \sqrt{5}}{2} \right)^1 +
       c_2 \left( \frac{1 - \sqrt{5}}{2} \right)^1 = 1 \\
& \Rightarrow & c_1 \left( \frac{1 + \sqrt{5}}{2} \right) +
       c_2 \left( \frac{1 - \sqrt{5}}{2} \right) = 1
\end{eqnarray*}
We now have two linear equations in two unknowns!  The system of
equations is not degenerate, so there is a unique solution: $c_1 =
1/\sqrt{5}$ and $c_2 = -1/\sqrt{5}$.  We now have a complete solution to
the Fibonacci recurrence \emph{with} boundary conditions:
\[
f(n) = \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n -
       \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^n
\]
This looks completely wrong!  All Fibonacci numbers are integers, but
this expression is full of square roots of five!  Amazingly, however,
the square roots always cancel out.  This expression really does give
the Fibonacci numbers if we plug in $n = 0, 1, 2, \ldots$.  If one
were required to guess the solution to the Fibonacci recurrence, then
it is easy to imagine taking at least six centuries to come up with
this!

\subsection{Job Prospects}

Let's return to the original question: how long until all $N$ faculty
positions are taken?

To answer this question, we must find the smallest $n$ such that $f(n)
\geq N$.  This will imply that in year $n$, there are as many professors
as university positions.  Therefore, graduates after year $n$ will
have to find other employment, e.g. shuffling golden disks in an
obscure monastic community for the next $10^{19}$ years.

Because $f(n)$ has such a complicated form, it is hard to compute the
right value of $n$ exactly.  However, we can make a good
approximation.  Notice that $f(n)$ is the sum of two terms.  The key
observation is that the second term tends to zero as $n$ grows large,
since $|\frac{1 - \sqrt{5}}{2}| = 0.618\ldots < 1$.  This means that we can
rewrite $f(n)$ with asymptotic notation as follows:
\[
f(n) = \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n + o(1)
\]
Using this approximation for $f(n)$, we can determine the approximate
year in which all faculty positions will be taken as follows:
\begin{eqnarray*}
& & f(n) \geq N \\
& \Leftrightarrow & \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^n + o(1) \geq N \\
& \Leftrightarrow & n \ge \frac{\log(\sqrt{5} \ N + o(1))}{\log(\frac{1 + \sqrt{5}}{2})}
\end{eqnarray*}
This implies that all the faculty jobs will be filled in $\Theta(\log
N)$ years.  This makes sense, since the number of professors is
increasing exponentially.  For example, if there are $N = 10000$ jobs,
then all will be taken in $n = 20.8$ years.  Now, as to the fate of
the TAs, there are fewer than ten thousand faculty jobs in computer
science and hiring started about 20 years ago\ldots

The solution to the Fibonacci recurrence has an interesting corollary:
for large $n$, $\frac{1}{\sqrt{5}} \left(\frac{1 +
\sqrt{5}}{2} \right)^n$ is very close to an integer---namely, the
$n$-th Fibonacci number.
\begin{table}
  \begin{center}
    \caption{For large~$n$, $\frac{1}{\sqrt{5}} \left(\frac{1 +
          \sqrt{5}}{2} \right)^n$ is very close to the $n$-th
      Fibonacci number.}
    \medskip
    \begin{tabular}{rr|rr|rr}
      $n$ & $\frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2} \right)^n$ &
      $n$ & $\frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2} \right)^n$ &
      $n$ & $\frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2} \right)^n$ \\
      \hline
      0 &  0.44721360 & 10 &   55.00363612 & 20 &   6765.00002956 \\
      1 &  0.72360680 & 11 &   88.99775275 & 21 &  10945.99998173 \\
      2 &  1.17082039 & 12 &  144.00138888 & 22 &  17711.00001130 \\
      3 &  1.89442719 & 13 &  232.99914163 & 23 &  28656.99999302 \\
      4 &  3.06524758 & 14 &  377.00053050 & 24 &  46368.00000431 \\
      5 &  4.95967478 & 15 &  609.99967213 & 25 &  75024.99999733 \\
      6 &  8.02492236 & 16 &  987.00020263 & 26 & 121393.00000165 \\
      7 & 12.98459713 & 17 & 1596.99987477 & 27 & 196417.99999898 \\
      8 & 21.00951949 & 18 & 2584.00007740 & 28 & 317811.00000063 \\
      9 & 33.99411664 & 19 & 4180.99995216 & 29 & 514228.99999961
    \end{tabular}
    \label{tab:fibonacci-asymptotic}
  \end{center}
\end{table}
This expression is the first term in the
closed form for the $n$-th Fibonacci number.  Since the other term of
the closed form goes to zero exponentially fast and Fibonacci numbers
are always integers, the first term must be very close to an integer!
This is one of many strange facts about the ``Golden Ratio'', $\frac{1
+ \sqrt{5}}{2} = 1.61803\ldots$.

\section{General Linear Recurrences}

The method we used to solve the Fibonacci recurrence can be used to
solve any linear recurrence!  Recall that every linear recurrence has
the following form:
\[
f(n) = \sum_{i=1}^d a_i f(n-i)
\]
Substituting the guess $f(n) = \alpha^n$ into the recurrence gives:
\begin{eqnarray*}
\alpha^n & = & a_1 \alpha^{n-1} + a_2 \alpha^{n-2} + \ldots + a_d \alpha^{n-d} \\
\alpha^d & = & a_1 \alpha^{d-1} + a_2 \alpha^{d-2} + \ldots + a_{d-1} \alpha + a_d \\
\alpha^d - a_1 \alpha^{d-1} - a_2 \alpha^{d-2} - \ldots - a_{d-1} \alpha - a_d & = & 0\\
\end{eqnarray*}
The equation is divided by $\alpha^{n-d}$ in the first step, and terms
are rearranged in the second step.  The last equation is called the
\emph{characteristic equation} of the recurrence.  The characteristic
equation of a recurrence can be read of very quickly; the coefficients
of the equation are the same as the coefficients of the recurrence.
In general, the characteristic equation will have $d$ roots, where $d$
is the order of the recurrence.  The solution to the recurrence
depends on whether all roots of the characteristic equation are
distinct.

\subsection{Simple Case:  Distinct Roots}

If the characteristic equation has $d$ distinct roots $r_1, r_2,
\ldots, r_d$, then the solution to the recurrence has the form:
\[
f(n) = c_1 r_1^n + c_2 r_2^n + \ldots + c_d r_d^n
\]
Note that the roots of the characteristic equation need not even be
real!  In the end, imaginary parts will cancel just as the
$\sqrt{5}$'s canceled in the solution to the Fibonacci recurrence.

The constants $c_1, c_2, \ldots, c_d$ depend on the boundary
conditions.  Each boundary condition generates a linear equation in
these constants.  For example, the boundary conditions $f(0) = b_0$,
$f(1) = b_1$, $\ldots$, $f(d-1) = b_{d-1}$ generate the linear
equations:
\begin{eqnarray*}
b_0 & = & c_1 + c_2 + \ldots + c_d \\
b_1 & = & c_1 r_1 + c_2 r_2 + \ldots + c_d r_d \\
\ldots & \ldots & \ldots \\
b_{d-1} & = & c_1 r_1^{d-1} + c_2 r_2^{d-1} + \ldots + c_d r_d^{d-1}
\end{eqnarray*}
If there are $d$ boundary conditions, then we obtain $d$ linear
equations in $d$ unknowns.  A neat linear algebra fact is that a
system of equations of this particular type is never degenerate.  This
means that for every set of constants $b_0, b_1, \ldots b_{d-1}$ in
the boundary conditions, we can find a unique set of constants $c_0,
c_1, \ldots c_{d-1}$ that give a solution to the recurrence and
satisfy the boundary conditions.

\subsection{Tricky Case:  Repeated Roots}

If the characteristic equation of a recurrence has a repeated root,
then the solution is slightly more complicated.  The main tool is the
following theorem, which we will not prove.
\begin{theorem}
If $r$ is a root of the characteristic equation of a recurrence with
multiplicity $m$, then all of $r^n, n r^n, n^2 r^n, \ldots n^{m-1}
r^n$ are solutions to the recurrence.
\end{theorem}
For example, if the characteristic equation of a recurrence has root
$r_1$ with multiplicity 2, root $r_2$ with multiplicity 1, and root
$r_3$ with multiplicity 3, then the solution to the recurrence has the
form:
\[
f(n) = c_1 r_1^n + c_2 n r_1^n +
       c_3 r_2^n +
       c_4 r_3^n + c_5 n r_3^n + c_6 n^2 r_3^n
\]
As before, the constants depend on the boundary conditions.  Each
boundary condition generates a linear equation, and the constants are
computed by solving the resulting system of linear equations.  In this
respect, solving linear recurrences is very similar to solving linear
differential equations.

\subsection{An Example of the Tricky Case}

To understand recurrences of this tricky type, let's work an example.
Nowadays, professor's lives are different.  They start fast, training
a graduate student in their first year.  But after that, the get busy
with a startup company and stop training any more students.  Notice
that this is just the reverse of the graduate student job problem---now
faculty ``reproduce'' only in the first year.

Let $f(n)$ be the number of professors in year $n$.  As boundary
conditions, define $f(0) = 0$ and $f(1) = 1$.  The faculty population
in year $n$ is equal to the population from the year before plus the
number of new faculty.  The population from the year before is
$f(n-1)$.  The number of new faculty this year is equal to the number
of new faculty last year or $f(n-1) - f(n-2)$.  We can now form a
recurrence equation for the faculty population:
\begin{eqnarray*}
f(n) & = & f(n-1) + (f(n-1) - f(n-2)) \\
     & = & 2 f(n-1) - f(n-2) \\
f(n) - 2 f(n-1) + f(n-2) & = & 0
\end{eqnarray*}
The characteristic equation is $\alpha^2 - 2 \alpha + 1 = 0$, which
has the single root $\alpha = 1$ with multiplicity 2.  Therefore, the
solution to the recurrence has the form:
\begin{eqnarray*}
f(n) & = & c_1 (1)^n + c_2 n (1)^n \\
     & = & c_1 + c_2 n
\end{eqnarray*}
The boundary conditions, $f(0) = 0$ and $f(1) = 1$, generate the
following linear equations:
\begin{eqnarray*}
0 & = & c_1 + c_2 (0) \\
1 & = & c_1 + c_2 (1)
\end{eqnarray*}
The solution to the linear system is $c_1 = 0$ and $c_2 = 1$.
Therefore, the solution to the recurrence is:
\begin{eqnarray*}
f(n) & = & c_1 + c_2 n \\
     & = & 0 + (1) n \\
     & = & n
\end{eqnarray*}
The answer turns out to be very simple!  In year $n$, there are
exactly $n$ faculty.  Of course, we probably could have solved this
problem more easily with Guess and Verify, but for many other
examples, guessing is not so easy.

\section{Inhomogeneous Recurrences}

We can now solve all recurrences of the form:
\[
f(n) - a_1 f(n-1) - \ldots - a_d f(n-d) = 0
\]
Strictly speaking, this is the family of linear \emph{homogeneous}
recurrences.  These recurrences are called homogeneous because the
right side of the equation is 0.  If the right side were 1 or $n^2$ or
some arbitrary function $g(n)$, then the recurrence would be called
\emph{inhomogeneous}.

\begin{defin*}
An inhomogeneous linear recurrence has the form:
\[
f(n) - a_1 f(n-1) - a_2 f(n-2) - \ldots - a_d f(n-d) = g(n)
\]
where $a_1, a_2, \ldots a_d$ are constants.
\end{defin*}

Inhomogeneous recurrences are trickier than homogeneous ones.
Remember that we used the following fact: if two distinct functions
satisfy a linear recurrence, then their sum does too.  This is no
longer true for inhomogeneous recurrences: if we have two functions
$f_1$ and $f_2$ that satisfy the inhomogeneous recurrence, that is to
say,
\begin{align*}
f_1(n)-\sum_{i=1}^d a_if_1(n-d) &= g(n)\\
f_2(n)-\sum_{i=1}^d a_if_2(n-d) &= g(n)\\
\intertext{then their sum $s(n)=f_1(n)+f_2(n)$ satisfies}\\
s(n)-\sum_{i=1}^d a_is(n-d) &= 2g(n)\\
\end{align*}
(we can see this by adding the equations for $f_1$ and $f_2$.
However, if we \emph{subtract} the equations for $f_1$ and $f_2$, and
define $t(n)=f_1(n)-f_2(n)$, then we find that
\[
t(n)-\sum_{i=1}^d a_i t(n-d) = 0,
\]
that is, the difference $t(n)$ satisfies the \emph{homogeneous}
portion of the inhomogeneous equation.  This leads to an approach for
inhomogeneous linear recurrences: solve the inhomogeneous part once,
and then add in the homogeneous part to deal with the boundary
conditions.


There are three steps to solving an inhomogeneous linear recurrence.
\begin{enumerate}
\item Replace $g(n)$ by 0 and solve the resulting homogeneous
  recurrence.  (Ignore boundary conditions for now; that is, do not
  solve for constants $c_1, c_2, \ldots, c_d$.)  The solution to the
  homogeneous recurrence is called the \emph{homogeneous solution}.
\item Restore $g(n)$ and find a single solution to the recurrence,
  again ignoring boundary conditions.  This is called the {\em
    particular solution}.  (This is the hard part!)
\item Add the homogeneous and particular solutions together to obtain
  the \emph{general solution}.  Now use the boundary conditions to
  determine the constant factors by the usual method of generating and
  solving a system of linear equations.
\end{enumerate}
Notice that the method for solving inhomogeneous linear recurrences is
closely analogous to the method for solving inhomogeneous linear 
differential equations!



\subsection{An Example of an Inhomogeneous Recurrence}

Let $f(n) = 4 f(n-1) + 3^n$ and, as a boundary condition, let $f(1) =
1$.  This is an inhomogeneous linear recurrence.

\subsubsection*{Step 1:  Solve the Homogeneous Recurrence}

The homogeneous recurrence is $f(n) - 4 f(n-1) = 0$.  The
characteristic equation is $\alpha - 4 = 0$.  The only root is $\alpha
= 4$.  Therefore, the homogeneous solution is $c_1 4^n$.

\subsubsection*{Step 2:  Find a Particular Solution}

We must find a single solution to the recurrence $f(n) = 4 f(n-1) +
3^n$.  This is usually the hard part of solving an inhomogeneous linear
recurrence.  Let's guess that there is a solution of the form $c 3^n$.
Substituting this into the recurrence gives:
\begin{eqnarray*}
f(n) & = & 4 f(n-1) + 3^n \\
c 3^n & = & 4 c 3^{n-1} + 3^n \\
3 c & = & 4 c  + 3 \\
c & = & -3
\end{eqnarray*}
The equation was divided by $3^{n-1}$ in the first step.  The second
and third steps were only simplification.  We now have a particular
solution, $f(n) = -3 \cdot 3^n = -3^{n+1}$.

\subsubsection*{Step 3:  Add Solutions and Find Constants}

We now add the homogeneous solution and the particular solution to
obtain the general solution:
\[
f(n) = c_1 4^n - 3^{n+1}
\]
The value of the constant is obtained from the boundary condition,
$f(1) = 1$:
\begin{eqnarray*}
1 & = & c_1 4^1 - 3^{1+1} \\
  & = & 4 c_1 - 9 \\
c_1 & = & 5/2
\end{eqnarray*}
The solution to the recurrence is $f(n) = \frac{5}{2} 4^n - 3^{n+1}$!

Since we could easily have made a mistake, let's check to make sure
that our solution at least works for $n = 2$.  From the recurrence,
$f(2) = 4 f(1) + 3^2 = 13$.  From our closed form, $f(2) = \frac{5}{2}
4^2 - 3^3 = 40 - 27 = 13$.  It looks right!

\subsection{Hanoi}

Now we can sledgehammer the Hanoi problem.  Recall the recurrence:
\[
T(n)=2T(n-1)+1.
\]
Let's apply our approach:

\subsubsection*{Step 1:  Solve the Homogeneous Recurrence}

The homogeneous recurrence is $T(n) - 2 T(n-1) = 0$.  The
characteristic equation is $\alpha - 2 = 0$.  The only root is $\alpha
= 2$.  Therefore, the homogeneous solution is $c 2^n$.


\subsubsection*{Step 2:  Find a Particular Solution}

Now we need a single solution to the recurrence $T(n) = 2T(n-1) + 1$
Let's guess a \emph{constant} solution $b$.  Is there a solution to
$b=2b+1$?  Yes!  Namely, $b=-1$.  So this is particular solution.

\subsubsection*{Step 3:  Add Solutions and Find Constants}

Adding the homogeneous solution and the particular solution gives the
general solution:
\[
T(n) = c 2^n -1
\]

Plugging in the boundary conditions gives $0=T(0)=c-1$ which tells us
that $c=1$.  So we get the expected answer $T(n)=2^n-1$.


\subsection{A Final Example}

Let $f(n) = 4 f(n-1) - 4 f(n-2) + n$ and, as a boundary condition, let
$f(0) = 4$ and $f(1) = 7$.

\subsubsection*{Step 1:  Solve the Homogeneous Recurrence}

The homogeneous recurrence is $f(n) - 4 f(n-1) + 4 f(n-2) = 0$.  The
characteristic equation is $\alpha^2 - 4 \alpha + 4$.  The only root
is $\alpha = 2$ with multiplicity 2.  Therefore, the homogeneous
solution is $c_1 2^n + c_2 n 2^n$.

\subsubsection*{Step 2:  Find a Particular Solution}

Now we need a single solution to the recurrence $f(n) = 4 f(n-1) - 4
f(n-2) + n$.  Let's guess a solution of the form $a n + b$ and
substitute into the recurrence:
\begin{eqnarray*}
f(n) & = & 4 f(n-1) - 4 f(n-2) + n \\
a n + b & = & 4 (a (n-1) + b) - 4 (a (n-2) + b) + n \\
        & = & 4 a n - 4 a + 4 b - 4 a n + 8 a - 4 b + n \\
        & = & 4 a + n \\
& \Rightarrow & a = 1, b = 4a = 4
\end{eqnarray*}

This gives the particular solution $f(n) = n + 4$.

\subsubsection*{Step 3:  Add Solutions and Find Constants}

Adding the homogeneous solution and the particular solution gives the
general solution:
\[
f(n) = c_1 2^n + c_2 n 2^n + n + 4
\]
The values of the constants are obtained from the boundary conditions,
$f(0) = 4$ and $f(1) = 7$.
\begin{eqnarray*}
4 & = & c_1 2^0 + 0 c_2 2^0 + 0 + 4 \\
  & = & c_1 + 4 \\
c_1 & = & 0 \\
7 & = & c_1 2^1 + 1 c_2 2^1 + 1 + 4 \\
  & = & 2 c_1 + 2 c_2  + 5 \\
c_2 & = & 1
\end{eqnarray*}
The solution to the recurrence is $f(n) = n 2^n + n + 4$.

\subsection{Finding a Particular Solution}

The hardest part in solving inhomogeneous recurrences is finding a
particular solution.  There are some good rules of thumb, however.
Suppose the recurrence has the form:
\[
f(n) - a_1 f(n-1) - a_2 f(n-2) - \ldots - a_d f(n-d) = g(n)
\]
If $g(n)$ is a polynomial of degree $r$, then guess that $f(n)$ is a
polynomial of degree $r$.  For example, if $g(n)= n^2$, then guess
$f(n) = a n^2 + b n + c$ and determine $a$, $b$, and $c$ by
substituting and verifying.  If a degree $r$ polynomial does not work,
then try degree $r+1$ and so on.

Similarly, if $g(n)$ is an exponential, then guess that $f(n)$ is an
exponential.  For example, if $g(n) = 2^n + 3^n$, then guess $f(n) =
a2^n + b3^n$.  In general, guess a particular solution with the same
form as $g(n)$.



\section{Generating Functions}

Generating functions are one of the most surprising, useful, and
clever inventions in discrete math.  There is a huge chunk of
mathematics concerning generating functions, so we will only get a
taste of the subject today.  Generating functions will come up again
later, though, when we cover probability.

Here is the idea behind generating functions.  We can represent a
sequence of numbers as a power series.  A power series defines a
function.  This lets us manipulate sequences of numbers with all the
tools that we have for working with functions.

\begin{definition*}
The \emph{ordinary generating function} (OGF) of the infinite sequence
$<g_0, g_1, g_2, g_3 \ldots>$ is the formal power series:
\[
g_0 + g_1 x + g_2 x^2 + g_3 x^3 + \ldots
\]
\end{definition*}
This definition requires a few comments.  All of the generating
functions in this lecture will be ordinary, so this is the only
definition that we will need.  A generating function is a ``formal''
power series in that we typically regard $x$ as a placeholder, not as
a number.  In particular, the convergence of the power series is
almost never an issue, since we will almost never evaluate the power
series for a particular $x$.  Throughout the lecture, we will indicate
the correspondence between a sequence and its generating function with
a double-sided arrow as follows:
\[
<g_0, g_1, g_2, g_3, \ldots> \leftrightarrow
        g_0 + g_1 x + g_2 x^2 + g_3 x^3 + \ldots
\]
Here are some basic examples of sequences and the corresponding
generating functions:
\begin{eqnarray*}
<0, 0, 0, 0, \ldots> & \leftrightarrow & 0 + 0 x + 0 x^2 + 0 x^3 \ldots
= 0 \\
<1, 0, 0, 0, \ldots> & \leftrightarrow & 1 + 0 x + 0 x^2 + 0 x^3 \ldots
= 1 \\
<1, 1, 0, 0, \ldots> & \leftrightarrow & 1 + 1 x + 0 x^2 + 0 x^3 \ldots
= 1 + x \\
<1, 1, 1, 1, \ldots> & \leftrightarrow & 1 + 1 x + 1 x^2 + 1 x^3 \ldots
= \frac{1}{1-x} \\
\end{eqnarray*}

These examples follow directly from the definition; the $i$-th term in
the sequence is the coefficient of $x^i$ in the generating function.
The last example has an interesting feature.  Recall that $1 + x + x^2
+ x^3 + \ldots$ is an infinite geometric sequence with sum
$\frac{1}{1-x}$.  As a result, we can represent the infinite sequence
of 1's with a simple, closed-form expression!  This generating
function arises frequently and is good to remember.  Below are some
more tricky examples of sequences and their generating functions.
\begin{eqnarray*}
<1, a, a^2, a^3, \ldots> & \leftrightarrow &
    = 1 + a x + a^2 x^2 + a^3 x^3 \ldots \\
& & = 1 + a x + (a x)^2 + (a x)^3 \ldots \\
& & = \frac{1}{1 - ax} \\
<1, -1, 1, -1, \ldots> & \leftrightarrow &
    = \frac{1}{1 + x} \\
<1, 0, 1, 0, \ldots> & \leftrightarrow &
    = 1 + x^2 + x^4 + \ldots \\
& & = \frac{1}{1 - x^2}
\end{eqnarray*}
In the first and third examples, the closed forms for the power series
follow from the formula for the sum of an infinite geometric sequence.
The second example is a special case of the first with $a = -1$.

The magic of generating functions is that they allow us to manipulate
sequences of numbers with all the tools usually applied to functions.
The sections below show how operations on sequences correspond to
operations on their generating functions.

\subsection{Adding Sequences}

Adding sequences term-by-term corresponds to adding the generating
functions.  For example:
\[
\begin{array}{clcl}
  & <1,  1,  1,  1, \ldots> & \leftrightarrow & \frac{1}{1-x} \\
+ & <1, -1,  1, -1, \ldots> & \leftrightarrow & \frac{1}{1+x} \\
\hline
  & <2,  0,  2,  0, \ldots> & \leftrightarrow & \frac{1}{1-x} + \frac{1}{1+x} =
        \frac{2}{1-x^2}\\
\\
\Rightarrow & <1,  0,  1,  0, \ldots> & \leftrightarrow & \frac{1}{1-x^2}\\
\end{array}
\]
The generating functions of the first two sequences were computed in
the preceding section.  On the third line, we sum the sequences and
sum their generating functions.  On the fourth line, we have divided
every term by two, which corresponds to dividing the generating
function by two.  We have ``derived'' the generating function of the
last sequence given in the preceding section!  The derivation is
justified by the following rule:
\begin{lemma}
\label{lemma:addition}
If $<f_0, f_1, f_2, \ldots> \leftrightarrow F(x)$ and
$<g_0, g_1, g_2, \ldots> \leftrightarrow G(x)$, then

\[
<\alpha f_0 + \beta g_0, \alpha f_1 + \beta g_1, \alpha f_2 + \beta
g_2, \ldots> \leftrightarrow \alpha F(x) + \beta G(x)
\]
\end{lemma}
\begin{proof}
\begin{eqnarray*}
<\alpha f_0 + \beta g_0, \alpha f_1 + \beta g_1, \alpha f_2 + \beta
g_2, \ldots>
& \leftrightarrow & \sum_{n=0}^\infty (\alpha f_n + \beta g_n) x^n \\
& = & \alpha \sum_{n=0}^\infty f_n x^n +
      \beta \sum_{n=0}^\infty g_n x^n \\
& = & \alpha F(x) + \beta G(x)
\end{eqnarray*}
\end{proof}

\subsection{Shifting a Sequence}

Suppose that we add $k$ leading zeroes to a sequence; how does the
generating function change?  For example, in the first section we
showed that:
\[
<1, 1, 1, \ldots> \leftrightarrow \frac{1}{1-x}
\]
If we add $k$ leading zeroes to the sequence, we can compute the new
generating function as follows:
\begin{eqnarray*}
<\underbrace{0, 0, \ldots, 0}_{\mbox{$k$ zeroes}}, 1, 1, 1, \ldots>
        & \leftrightarrow & x^k + x^{k+1} + x^{k+2} + \ldots \\
        & = & x^k (1  + x + x^2 + \ldots) \\
        & = & \frac{x^k}{1-x} \\
\end{eqnarray*}
In this example, adding $k$ leading zeroes to the sequence corresponds
to multiplying the generating function by $x^k$.  In fact, this holds
in general.
\begin{lemma}
\label{lemma:shift}
If $<f_0, f_1, f_2, \ldots> \leftrightarrow F(x)$, then
\[
<\underbrace{0, 0, \ldots, 0}_{\mbox{$k$ zeroes}}, f_0, f_1, f_2, \ldots>
        \leftrightarrow x^k F(x)
\]
\end{lemma}
\begin{proof}
\begin{eqnarray*}
<\underbrace{0, 0, \ldots, 0}_{\mbox{$k$ zeroes}}, f_0, f_1, f_2, \ldots>
& \leftrightarrow & f_0 x^k + f_1 x^{k+1} + f_2 x^{k+2} + \ldots \\
& = & x^k( f_0 + f_1 x + f_2 x^2 + \ldots) \\
& = & x^k F(x)
\end{eqnarray*}
\end{proof}

\subsection{Differentiation}

What happens if we take the derivative of a generating function?  As
an example, let's differentiate the now-familiar generating function
for an infinite sequence of 1's.
\begin{eqnarray*}
\frac{d}{dx} \ (1 + x + x^2 + x^3 + x^4 + \ldots)
        & = & \frac{d}{dx} \left( \frac{1}{1-x} \right) \\
1 + 2x + 3x^2 + 4x^3 + \ldots & = & \frac{1}{(1-x)^2} \\
<1, 2, 3, 4, \ldots> & \leftrightarrow & \frac{1}{(1-x)^2}
\end{eqnarray*}
We found a generating function for the sequence $<1, 2, 3, 4,
\ldots>$!  In general, differentiating a generating function has two
effects on the corresponding sequence:
\begin{enumerate}
\item Each term is multiplied by its index.
\item The sequence is shifted left one place.
\end{enumerate}
These effects are apparent in the following rule:
\begin{lemma}
\label{lemma:derivative}
If $<f_0, f_1, f_2, f_3, \ldots> \leftrightarrow F(x)$, then

\[
<f_1, 2f_2, 3f_3, \ldots> \leftrightarrow F'(x)
\]
\end{lemma}
\begin{proof}
\begin{eqnarray*}
<f_1, 2f_2, 3f_3, \ldots> & = & f_1 + 2 f_2 x + 3 f_3 x^2 + \ldots \\
        & = & \frac{d}{dx} \ (f_0 + f_1 x + f_2 x^2 + f_3 x^3 + \ldots) \\
        & = & \frac{d}{dx} \ F(x)
\end{eqnarray*}
\end{proof}
The derivative rule is very useful!  In fact, there is frequent,
independent need for each of differentiation's two effects,
multiplying terms by their index and left-shifting one place.
Typically, we want just one effect and must somehow cancel out the
other.

Suppose that we want the generating function for the sequence of
squares, $<0, 1, 4, 9, 16, \ldots>$.  We could start with the sequence
$<1, 1, 1, \ldots>$ and multiply each term by its index two times.
This would give the desired result:
\begin{eqnarray*}
<0 \cdot 0, 1 \cdot 1, 2 \cdot 2, 3 \cdot 3, \ldots>
& = &
<0, 1, 4, 9, \ldots>
\end{eqnarray*}
The problem is that differentiation not only multiplies each term by
its index, but also shifts a sequence left one place.  However,
Lemma~\ref{lemma:shift} tells how to cancel out this unwanted left-shift;
namely, multiply the generating function by $x$ to right-shift the
sequence back one place.

Our procedure, therefore, is to begin with the generating function for
$<1, 1, 1, \ldots>$, differentiate, multiply by $x$, and then again
differentiate and multiply by $x$.
\begin{eqnarray*}
<1, 1, 1, 1, \ldots>  & \leftrightarrow & \frac{1}{1-x} \\
<1, 2, 3, 4, \ldots>  & \leftrightarrow & \frac{d}{dx} \ \frac{1}{1-x}
                                          = \frac{1}{(1-x)^2} \\
<0, 1, 2, 3, \ldots>  & \leftrightarrow & x \cdot \frac{1}{(1-x)^2}
                                          = \frac{x}{(1-x)^2} \\
<1, 4, 9, 16, \ldots> & \leftrightarrow & \frac{d}{dx} \ \frac{x}{(1-x)^2}
                                          = \frac{1+x}{(1-x)^3} \\
<0, 1, 4, 9, \ldots>  & \leftrightarrow & x \cdot \frac{1+x}{(1-x)^3}
                                          = \frac{x(1+x)}{(1-x)^3}
\end{eqnarray*}
The generating function for squares is $\frac{x(1+x)}{(1-x)^3}$.

\section{The Fibonacci Sequence}

A sequence defined by a recurrence often has a simple generating
function.  An example is the Fibonacci sequence:
\[
<0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots> \leftrightarrow \frac{x}{1-x-x^2}
\]
It is amazing that such a tricky sequence could have so simple a
generating function!  In the next two sections, we will derive this
generating function and then use it to find a closed form for the
$n$-th Fibonacci number.  The techniques used here are applicable to a
large class of recurrence equations.

\subsection{Finding a Generating Function}

Recall the definition of the Fibonacci sequence:
\[
f_0 = 0, \quad f_1 = 1, \quad f_n = f_{n-1} + f_{n-2} \mbox{ for } n \geq 2
\]
We can write the generating function for the Fibonacci numbers as follows.
\begin{eqnarray*}
F(x) & = & \sum_{n=0}^\infty f_n x^n \\
     & = & \underbrace{0 + x}_{
\begin{array}{c}
\mbox{break out} \\
\mbox{base cases}
\end{array}
} + \sum_{n=2}^\infty \underbrace{(f_{n-1} + f_{n-2}) x^n}_{
\begin{array}{c}
\mbox{expand other terms with} \\
\mbox{the recurrence relation}
\end{array}
}
\end{eqnarray*}
Our objective is now to write $F(x)$ in terms of itself.  We can then
solve for $F(x)$ to find a closed form for the generating function.
The following sequence of equations is explained in the text that
follows.
\begin{eqnarray*}
F(x) & = & x + \sum_{n=2}^\infty f_{n-1} x^n + \sum_{n=2}^\infty f_{n-2} x^n \\
     & = & x + x \sum_{n=2}^\infty f_{n-1} x^{n-1} +
               x^2 \sum_{n=2}^\infty f_{n-2} x^{n-2} \\
     & = & x + x \sum_{n=1}^\infty f_n x^n +
               x^2 \sum_{n=0}^\infty f_n x^n \\
     & = & x + x \sum_{n=0}^\infty f_n x^n +
               x^2 \sum_{n=0}^\infty f_n x^n \\
     & = & x + x F(x) + x^2 F(x)
\end{eqnarray*}
In the first equation, we split the previous sum into two parts.  The
idea behind all subsequent steps is to make each part look like
$F(x)$.  In the second equation, we make subscripts of coefficients
match exponents by pulling $x$'s out of the summations.  In the third
equation, we adjust the indices of summation so that subscripts and
exponents are $n$ instead of $n-1$ and $n-2$.  In the fourth equation,
the range of the first summation is extended to include $n=0$; this is
valid because the summand is 0 in this case anyway.  Finally, in two
places we substitute $F(x)$ for its definition, $\sum_{n=0}^\infty f_n
x^n$.

We now have an equation in $F(x)$.  Solving for $F(x)$ gives the
generating function for Fibonacci numbers.
\begin{eqnarray*}
            F(x) & = & x + x F(x) + x^2 F(x) \\
\Rightarrow F(x) & = & \frac{x}{1 - x - x^2}
\end{eqnarray*}
Amazingly, the power series of $F(x)$ really does encode all the
Fibonacci numbers:
\[
\frac{x}{1 - x - x^2} = 0 + x + x^2 + 2 x^3 + 3 x^4 + 5 x^5 + 8x^6 + \ldots
\]

\subsection{Finding a Closed Form}

Why should one care about the generating function for a sequence?
There are several answers, but here is one.  If we can find a
generating function for a sequence, then we can often find a closed
form for the $n$-th term in the sequence.

For example, we found a generating function for the Fibonacci
sequence.  From this we can find a closed form for the $n$-th
Fibonacci number.  In particular, the $n$-th Fibonacci number is the
coefficient of $x^n$ in the power series of $\frac{x}{1 - x - x^2}$.
Our problem, therefore, is to extract the $n$-th coefficient from the
power series of a generating function.

One way to extract a coefficient from a generating function
works if the generating function is a ratio of polynomials.  This is
often true in recurrence problems.  The idea is to rewrite the
generating function using partial fractions; in this form, one can
immediately read out the coefficients of the power series.

There are two steps in rewriting the generating function $\frac{x}{1 -
x - x^2}$ with partial fractions.  First, we factor the denominator:
\begin{eqnarray*}
1 - x - x^2 & = & (1 - \alpha_1 x) (1 - \alpha_2 x) \\
\mbox{where } \alpha_1 = \frac{1 + \sqrt{5}}{2} & , & \alpha_2 = \frac{1 - \sqrt{5}}{2}
\end{eqnarray*}
Second, we find $A_1$ and $A_2$ which satisfy the following equation:
\[
\frac{x}{1 - x - x^2} =
        \frac{A_1}{1 - \alpha_1 x} + \frac{A_2}{1 - \alpha_2 x}
\]
To do this, we plug in various values of $x$ to generate linear
equations in $A_1$ and $A_2$.  We can then find $A_1$ and $A_2$ by
solving a linear system.  In this case, we get:
\begin{eqnarray*}
A_1 = \frac{1}{\alpha_1 - \alpha_2} = \frac{1}{\sqrt{5}} \\
A_2 = \frac{-1}{\alpha_1 - \alpha_2} = -\frac{1}{\sqrt{5}}
\end{eqnarray*}
Substituting into the equation above gives the partial fractions
expansion of $F(x)$:
\[
\frac{x}{1 - x - x^2} =
        \frac{1}{\sqrt{5}}
        \left(
        \frac{1}{1 - \alpha_1 x} - \frac{1}{1 - \alpha_2 x}
        \right)
\]
After the generating function is written with partial fractions,
reading out coefficients is easy, because each fraction has a simple
power series.
\begin{eqnarray*}
\frac{1}{1 - \alpha_1 x} & = & 1 + \alpha_1 x + \alpha_1^2 x^2 + \ldots \\
\frac{1}{1 - \alpha_2 x} & = & 1 + \alpha_2 x + \alpha_2^2 x^2 + \ldots
\end{eqnarray*}
We can now find the coefficient of $x^n$ in the generating function:
\begin{eqnarray*}
F(x) & = &
        \frac{1}{\sqrt{5}}
        \left(
        \frac{1}{1 - \alpha_1 x} -
        \frac{1}{1 - \alpha_2 x}
        \right) \\
& = &
        \frac{1}{\sqrt{5}}
        \left(
        (1 + \alpha_1 x + \alpha_1^2 x^2 + \ldots) -
        (1 + \alpha_2 x + \alpha_2^2 x^2 + \ldots)
        \right) \\
\Rightarrow f_n & = & \frac{1}{\sqrt{5}} (\alpha_1^n - \alpha_2^n) \\
                & = & \frac{1}{\sqrt{5}}
\left(
        \left(\frac{1 + \sqrt{5}}{2}\right)^n -
        \left(\frac{1 - \sqrt{5}}{2}\right)^n
\right)
\end{eqnarray*}
This is the same scary formula for the $n$-th Fibonacci number that we
found using the method for solving linear recurrences!  The closed
form for Fibonacci numbers was actually first found by DeMoivre in
1718 using this technique.  The same approach can be used to solve any
linear recurrence and even some non-linear recurrences.

\subsection{Review of the Method}

Since we will see only this one example of using generating functions
to solve a recurrence, let's review the process.  There are two main
steps and some tricks in each.  First, we find a generating function
for the sequence defined by the recurrence as follows.
\begin{enumerate}
\item Write the generating function as $F(x) = \sum_{n=0}^\infty f_n x^n$.
\item Pull out base cases, apply the recurrence equation to remaining terms.
\item Massage this formula to get an equation in $F(x)$.
\item Solve the equation to obtain the generating function $F(x)$.
\end{enumerate}
Second, we have to extract coefficients from the generating function:
\begin{enumerate}
\item Expand the generating function into partial fractions.
\item Expand each fraction into a simple power series.
\item Read out the coefficients of the generating function.
\end{enumerate}


\end{document}
