A **recurrence relation**
defines a sequence $\{a_i\}_{i=0}^\infty$ by expressing a typical term
$a_n$ in terms of earlier terms, $a_i$ for $i< n$. For example, the
famous Fibonacci sequence is defined by
$$ F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}.$$
Note that some initial values must be specified for the recurrence
relation to define a unique sequence.

The starting index for the sequence need not be zero if it doesn't make sense or some other starting index is more convenient. We saw two recurrence relations for the number of derangements of $[n]$: $$D_1=0, D_n=nD_{n-1}+(-1)^n.$$ and $$D_1=0, D_2=1, D_n=(n-1)(D_{n-1}+D_{n-2}).$$

To "solve'' a recurrence relation means to find a formula for $a_n$. There are a variety of methods for solving recurrence relations, with various advantages and disadvantages in particular cases. One method that works for some recurrence relations involves generating functions. The idea is simple, if the execution is not always: Let $$f(x)=\sum_{i=0}^\infty a_ix^i,$$ that is, let $f(x)$ be the generating function for $\{a_i\}_{i=0}^\infty$. We now try to manipulate $f(x)$, using the recurrence relation, until we can solve for $f(x)$ explicitly. Finally, we hope that we can find a formula for the coefficients from the formula for $f(x)$.

Example 3.4.1 Solve $\ds F_0=0$, $\ds F_1=1$, $\ds F_n=F_{n-1}+F_{n-2}$.

Let $$f(x)=\sum_{i=0}^\infty F_ix^i$$ and note that $$xf(x)=\sum_{i=0}^\infty F_ix^{i+1}=\sum_{i=1}^\infty F_{i-1}x^{i}.$$ To get the second sum we have simply "re-indexed'' so that the index value gives the exponent on $x$, just as in the series for $f(x)$. Likewise, $$x^2f(x)=\sum_{i=0}^\infty F_ix^{i+2}=\sum_{i=2}^\infty F_{i-2}x^{i}.$$ In somewhat more suggestive form, we have $$\matrix{ f(x)&=&x&+&F_2x^2&+&F_3x^3&+&F_4x^4&+\cdots\cr xf(x)&=&&&x^2&+&F_2x^3&+&F_3x^4&+\cdots\cr x^2f(x)&=&&&&&x^3&+&F_2x^4&+\cdots\cr} $$ and combining the three equations we get $$f(x)-xf(x)-x^2f(x)=x + (F_2-1)x^2+(F_3-F_2-1)x^3+(F_4-F_3-F_2)x^4+\cdots$$ or in more compact form $$\eqalign{ f(x)-xf(x)-x^2f(x) &=\sum_{i=0}^\infty F_ix^i - \sum_{i=1}^\infty F_{i-1}x^{i} - \sum_{i=2}^\infty F_{i-2}x^{i}\cr &=x+\sum_{i=2}^\infty (F_i-F_{i-1}-F_{i-2})x^i\cr &=x+\sum_{i=2}^\infty 0\cdot x^i\cr &=x,\cr }$$ recalling that $F_0=0$ and $F_1=1$. Now $$f(x)={x\over 1-x-x^2}={-x\over x^2+x-1}.$$ If we can find an explicit representation for the series for this function, we will have solved the recurrence relation. Here is where things could go wrong, but in this case it works out. Let $a$ and $b$ be the roots of $x^2+x-1$; using the quadratic formula, we get $$a={-1+\sqrt5\over2}, b={-1-\sqrt5\over2}.$$ Borrowing a technique from calculus, we write $${-x\over x^2+x-1}={A\over x-a}+{B\over x-b}.$$ Solving for $A$ and $B$ gives $$A={1-\sqrt5\over2\sqrt5}, B={-1-\sqrt5\over 2\sqrt5}.$$ Then $${-x\over x^2+x-1}=-{A\over a}{1\over 1-x/a}-{B\over b}{1\over 1-x/b}.$$ From calculus we know that $${1\over 1-x/a}=\sum_{i=0}^\infty (1/a)^ix^i\quad\hbox{and}\quad {1\over 1-x/b}=\sum_{i=0}^\infty (1/b)^ix^i.$$ Finally, this means the coefficient of $x^i$ in the series for $f(x)$ is $$F_i=-{A\over a}(1/a)^i-{B\over b}(1/b)^i.$$ Simplifying gives $$F_i={1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^i- {1\over\sqrt5}\Bigl({1-\sqrt5\over2}\Bigr)^i.$$ Sage can solve many recurrence relations; this allows us to check our answers. Sometimes the format may be a bit different than what you get by hand.

Here's an interesting feature of this expression: since $|(1-\sqrt5)/2|< 1$, the limit of $((1-\sqrt5)/2)^i$ as $i$ goes to infinity is 0. So when $i$ is large, $$F_i=\mathop{\hbox{round}} \left({1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^i\right),$$ that is, the first term rounded to the nearest integer. As it turns out, this is true starting with $i=0$.

You can see how to do the entire solution in Sage.

## Exercises 3.4

**Ex 3.4.1**
Find the generating function for the solutions to
$h_n=4h_{n-1}-3h_{n-2}$, $h_0=2$, $h_1=5$, and use it to find a formula
for $h_n$.

**Ex 3.4.2**
Find the generating function for the solutions to
$h_n=3h_{n-1}+4h_{n-2}$, $h_0=h_1=1$, and use it to find a formula
for $h_n$.

**Ex 3.4.3**
Find the generating function for the solutions to
$h_n=2h_{n-1}+3^n$, $h_0=0$, and use it to find a formula
for $h_n$.

**Ex 3.4.4**
Find the generating function for the solutions to $h_n=4h_{n-2}$,
$h_0=0$, $h_1=1$, and use it to find a formula for $h_n$. (It is easy
to discover this formula directly; the point here is to see that the
generating function approach gives the correct answer.)

**Ex 3.4.5**
Find the generating function for the solutions to
$h_n=h_{n-1}+h_{n-2}$, $h_0=1$, $h_1=3$, and use it to find a formula
for $h_n$.

**Ex 3.4.6**
Find the generating function for the solutions to
$h_n=9h_{n-1}-26h_{n-2}+24h_{n-3}$, $h_0=0$, $h_1=1$, $h_2=-1$,
and use it to find a formula for $h_n$.

**Ex 3.4.7**
Find the generating function for the solutions to
$h_n=3h_{n-1}+4h_{n-2}$, $h_0=0$, $h_1=1$,
and use it to find a formula for $h_n$.

**Ex 3.4.8**
Find a recursion for the number of ways to place flags on an
$n$ foot pole, where we have red flags that are 2 feet high, blue
flags that are 1 foot high, and yellow flags that are 1 foot high; the
heights of the flags must add up to $n$. Solve the recursion.

**Ex 3.4.9**
In Fibonacci's original problem, a farmer started with one
(newborn) pair of rabbits at month 0. After each pair of rabbits was
one month old, they produced another pair each month in perpetuity.
Thus, after 1 month, he had the original pair, after two months 2
pairs, three months, 3 pairs, four months, 5 pairs, etc. The number
of pairs of rabbits satisfies $h_n=h_{n-1}+h_{n-2}$, $h_0=h_1=1$. (Note
that this is slightly different than our definition, in which $h_0=0$.)

Suppose instead that each mature pair gives birth to *two* pairs
of rabbits. The sequence for the number of pairs of rabbits now
starts out $h_0=1$, $h_1=1$, $h_2=3$, $h_3=5$, $h_4=11$. Set up and
solve a recurrence relation for the number of pairs of rabbits. Show
also that the sequence statisfies $h_n=2h_{n-1}+(-1)^n$.