Recurrence Relations

A recurrence relation is simply a rule for getting each term of a sequence from the ones before it: "to get the next number, do something to the last one or two." The name comes from the sequence recurring, or calling back to itself. The sequences in the last lesson had formulas you could write down right away, but lots of sequences don't; what you can usually see instead is how one term relates to the previous ones. $F_n = F_{n-1} + F_{n-2}$ just reads "each Fibonacci number is the sum of the two before it," and $H_n = 2H_{n-1} + 1$ reads "do the smaller job twice, plus one extra move." The little subscripts ($n$, $n-1$, $n-2$) are only place numbers in the list. It's the same idea as induction, run forward: know the start, know how to take one step, and you know everything.

Tower of Hanoi. You have $n$ disks stacked on one peg, largest at the bottom, and you want them on another peg, moving one disk at a time and never putting a bigger disk on a smaller one. Think about the biggest disk. It can only move when everything else is out of the way, sitting on the third peg. So: move the top $n - 1$ out of the way ($H_{n-1}$ moves), move the biggest disk (1 move), then move the $n - 1$ back on top of it ($H_{n-1}$ moves). That gives $H_n = 2H_{n-1} + 1$. Listing values, $1, 3, 7, 15, 31, \dots$, these are each one less than a power of 2, which suggests $H_n = 2^n - 1$. Induction proves it: $2(2^{n-1} - 1) + 1 = 2^n - 1$.

Fibonacci numbers show up in a surprising number of counting problems. Here's one. Let $s_n$ be the number of bit strings of length $n$ with no two consecutive 1s. Look at how a valid string ends. If it ends in 0, anything valid of length $n - 1$ can come before it. If it ends in 1, the bit before that has to be 0, so it ends in 01, and anything valid of length $n - 2$ comes before that. Those two cases don't overlap and cover everything, so $s_n = s_{n-1} + s_{n-2}$. With $s_1 = 2$ and $s_2 = 3$, that makes $s_n = F_{n+2}$.

Solving a recurrence means finding a closed form, so you can jump straight to the 100th term. One approach is to compute terms, guess a pattern, and prove it by induction, as we did for Hanoi. For linear recurrences like Fibonacci there's a systematic method using characteristic roots, which is the next lesson.

Ratios of consecutive Fibonacci numbers approach the golden ratio $\varphi = \frac{1 + \sqrt 5}{2} \approx 1.618$. We'll see exactly why in the next lesson too.

Recurrences describe population growth, loan balances and the running time of recursive algorithms such as merge sort.