3.5: Recurrence Relations

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}.\nonumber$$

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.\nonumber$$

and

$$D_1=0, D_2=1, D_n=(n-1)(D_{n-1}+D_{n-2}).\nonumber$$

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,\nonumber$$

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 $\PageIndex{1}$

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

Solution

Let $$f(x)=\sum_{i=0}^\infty F_ix^i\nonumber$$

and note that

$$xf(x)=\sum_{i=0}^\infty F_ix^{i+1}=\sum_{i=1}^\infty F_{i-1}x^{i}.\nonumber$$

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}.\nonumber$$

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}\nonumber$$

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\nonumber$$

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 }\nonumber$$

recalling that $F_0=0$ and $F_1=1$. Now

$$f(x)={x\over 1-x-x^2}={-x\over x^2+x-1}.\nonumber$$

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}.\nonumber$$ Borrowing a technique from calculus, we write

$${-x\over x^2+x-1}={A\over x-a}+{B\over x-b}.\nonumber$$

Solving for $A$ and $B$ gives

$$A={1-\sqrt5\over2\sqrt5}, B={-1-\sqrt5\over 2\sqrt5}.\nonumber$$

Then

$${-x\over x^2+x-1}=-{A\over a}{1\over 1-x/a}-{B\over b}{1\over 1-x/b}.\nonumber$$

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.\nonumber$$

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.\nonumber$$

Simplifying gives

$$F_i={1\over\sqrt5}\Bigl({1+\sqrt5\over2}\Bigr)^i- {1\over\sqrt5}\Bigl({1-\sqrt5\over2}\Bigr)^i.\nonumber$$

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.

view sourceprint?

1	from sympy import Function, rsolve

2	from sympy.abc import n

3	y = Function('y')

4	g = y(n)-y(n-1)-y(n-2)

5	rsolve(g, y(n), { y(0):0, y(1):1 })

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),\nonumber$$

that is, the first term rounded to the nearest integer. As it turns out, this is true starting with $i=0$.

We can check this in Sage.

view sourceprint?

1	f(x)=((1+sqrt(5))/2)^x/sqrt(5)

2	[round(N(f(i))) for i in range(0,21)]

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

We can also use this expression for $F_n$ to compute $\lim_{n\to\infty}F_n /F_{n-1}$.

$$\underset{n\to\infty}{\lim}\frac{F_{n}}{F_{n-1}}=\underset{n\to\infty}{\lim}\frac{\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^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-1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}}=\frac{1+\sqrt{5}}{2}. \nonumber$$

This is the so-called "golden ratio''.