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 enough, $$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. $\square$
We can also use this expression for $F_n$ to compute $\lim_{n\to\infty} F_n/F_{n-1}$. $$\lim_{n\to\infty} {F_n\over F_{n-1}}=\lim_{n\to\infty} {{1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^n- {1\over\sqrt5}\Bigl({1-\sqrt5\over2}\Bigr)^n\over {1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^{n-1}- {1\over\sqrt5}\Bigl({1-\sqrt5\over2}\Bigr)^{n-1}}={1+\sqrt{5}\over 2}. $$ This is the so-called "golden ratio''.
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$.
Ex 3.4.10 Explain why $$\lim_{n\to\infty}{F_n\over F_{n-1}}=\lim_{n\to\infty} {{1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^n- {1\over\sqrt5}\Bigl({1-\sqrt5\over2}\Bigr)^n\over {1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^{n-1}- {1\over\sqrt5}\Bigl({1-\sqrt5\over2}\Bigr)^{n-1}}={1+\sqrt{5}\over 2}. $$