An aside: why we care about recurrence relations as computer scientists

In class we took a moment to talk about why recurrence relations are important in computer science. The first reason - and an obvious one - is that when we want to count how many operations are performed by a recursive algorithm, this invariably gives rise to a recurrence relation. However, there are many more places where recurrences show up. Here's a different kind of example.

In IC210 you have learned about linked lists. Linked lists are the simplest kind of linked data structures, but there are many, many others. Perhaps the next simplest is this: a node in a linked list has a link to exactly one "next" node (except for the last, which has zero next nodes). What if each node had exactly two "next" nodes, which we call the left and right child nodes. Obviously this has to end, so at the lowest level we have nodes without children, which are called leaf nodes. Note: I had lots of pictures! We considered the question of how many leaf nodes a "full" binary tree of height $h$ has (which we called $l(h)$), and that led us to ... $$ l(h) = 2\cdot l(h), l(0) = 1. $$ In other words, we get a recurrence relation! (We explained how we got it in class.) You solved this recurrence as an in-class activity, and got $l(h) = 2^h$. We might also ask how many total nodes are in a "full" binary tree of height $h$ (which we called $c(h)$), and that led us to ... $$ c(h) = c(h-1) + l(h) = c(h-1) + 2^h, c(0) = 1. $$ Once again we got a recurrence relation! The solution to this is $c(h) = 2^{h+1}-1$.
Note: in class we talked very briefly about the connection to this and efficient storage a retreival of data.

The "order" of a recurrence relation

int f(int n) {
  if (n == 0)
    return -2;
  else
    return f(n-1) + n*n - 3*n;
}

Consider the recurrence relation: $$f(0) = -2, f(n) = f(n-1) + n^2 - 3n, \ \ f(0) = -2$$ We talked already about how this can be turned trivially into a recursive function in a programming language (see code on the right). However, since the value of $f(n)$ only relies on the previous value (i.e. $f(n-1)$), we can also write this with a loop, using a variable "fold" that carries the result from the previous loop iteration into the current loop iteration.

  // calculate f(10)
  int fold = -2;
  for(int n = 1; n <= 10; n++) {
    int f = fold + n*n - 3*n;
    fold = f;
  }   
  cout << fold << endl;

So now let's consider recurrence relation: $h(n) = 1 + h(n-2),\ \ h(0) = 7$.
Is this well-defined? No! Why not? Because $h(1)$ doesn't have a value (since it would rely on $h(-1)$, which doesn't exist). So we have to add an explicit value for it - let's say 4. Now we have $$ h(n) = 1 + h(n-2),\ \ h(0) = 7,\ \ h(1) = 4 $$ So will that same simple loop-based code work for $h(n)$? No! Why not? Because now we need to remember the last two values from one iteration to the next, not just the last one. This points to a crucial difference between the two recurrences. The recurrence for $f$ is called "first order", because $f(n)$ relies only as far back as $f(n-1)$. On the other hand, $h$ is called "second order", because $h(n)$ relies as far back as $h(n-2)$.

So: if recurrence relation defines $f(n)$ in terms of $f(n-1),...,f(n-k)$, it is order $k$.

Capping it all off: 2nd order, homogeneous recurrence relations with constant coefficients ... oh my!

As our sort of "capstone experience" for the course, we are going to tackle recurrence relations of the form $$ f(n) = af(n-1) + bf(n-2), \ \ f(0) = c_0, f(1) = c_1, \text{ where }a, b, c_0, c_1\text{ are all constants} $$ Mathematicians would categorize these as 2nd order homogeneous recurrence relations with constant coefficients. "2nd order" is because $f(n)$ is described in terms of the previous two sequence values. "Homogeneous" because all terms have $f$s in them (that's just what the term means). "With constant coefficients" because the coefficients are constants (of course), as opposed to having $n$ appear in them in some way. The method we will develop works for any 2nd order homogeneous recurrence relation with constant coefficients, but we will actually derive it and use it for one specific recurrence relation: Hopefully you see that this defines each element of the sequence simply as the sum of the previous two elements. So we get:

0,1,1,2,3,5,8,13,21,34,55,89,...

Guess and check: substituting a function into a recurrence

Let's consider just the recurrence equation for the fibonacci numbers: $f(n) = f(n-1) + f(n-2)$Ⓐ

It's important to understand that in an equation like this, "$f$" is a function variable. I.e. it's a variable that stands for a function instead of a number. So just as we can substutite $5$ for the variable $x$ into $3x-4=7$, we should be able to take a concrete function and substitute it for $f$ in Ⓐ. In what follows, it's actually a bit easier to rewrite Ⓐ so that the right-hand side is zero, as in:

$f(n) - f(n-1) - f(n-2) = 0$Ⓑ

Hopefully it's clear that this is equivalent. So, consider the function $g(x) = x^2 + 1$. Substituting $g(x)$ for $f$ we get $$ \begin{array}{ccl} \left(g(x)\ @\ x=n\right) - \left(g(x)\ @\ x=n-1\right) - \left(g(x)\ @\ x=n-2\right) &=& \left(n^2+1\right) - \left((n-1)^2+1\right) - \left((n-2)^2+1\right)\\ &=& (n^2 + 1) - (n^2 - 2n + 1 + 1) - (n^2 - 4n + 4 + 1)\\ &=& - n^2 + 6n - 6 \neq 0 \end{array} $$ Clearly, $g(x)$ is not a solution function for equation Ⓑ. In class, I gave you another proposed solution function: $h(x) = r^x$, where $r\neq 0$ and asked you to try the same thing with that. One big difference is that "$r$" is left as a free parameter, so what we really want is to see if we can find any values of $r$ for which $h(x)$ is a solution function for Ⓑ. Substituting $h(x)$ for $f$ gives: $$ r^n - r^{n-1} - r^{n-2} = 0 $$ Since $r\neq 0$, we can divide both sides of the equation by $r^{n-2}$, which gives $$ r^2 - r - 1 = 0 $$ But that's just a quadratic equation! So we apply the quadratic formula and get two solutions, $\frac{1 - \sqrt{5}}{2}$ and $\frac{1 + \sqrt{5}}{2}$.

So, this means we've found two functions that satisfy Ⓑ: $f_1(x) = \left(\frac{1 - \sqrt{5}}{2}\right)^x$, $f_2(x) = \left(\frac{1 + \sqrt{5}}{2}\right)^x$.

Unfortunately, neither of these functions satisfy the definition of the fibonacci sequence! Why? Because although they do satisfy the recurrence, they do not satisfy the initial conditions $f(0)=0$ and $f(1)=1$. So we've made progress, but we're still not there. We still don't have a closed form for the fibonacci sequence.

From two solutions to infinitely many solutions

This is a powerful result, since it tells us that from our two solutions we can form infinitely many new solutions. Maybe we can form a new solution that satisfies the initital conditions, right?

The final piece of the puzzle

We would like to form a linear combination $sf_1(x)+tf_2(x)$ that satisfies the initial conditions for the fibonacci sequence, i.e. $f(0)=0$ and $f(1)=1$. To satisfy $f(0)=0$, we need $$ \begin{array}{c} s\cdot \left(\frac{1 - \sqrt{5}}{2}\right)^0 + t\cdot \left(\frac{1 + \sqrt{5}}{2}\right)^0 = s\cdot 1 + t\cdot 1 = 0 \end{array} $$ ... and to satsfy $f(1)=1$, we need $$ \begin{array}{c} s\cdot \left(\frac{1 - \sqrt{5}}{2}\right)^1 + t\cdot \left(\frac{1 + \sqrt{5}}{2}\right)^1 = s\cdot\frac{1 - \sqrt{5}}{2} + t\cdot \frac{1 + \sqrt{5}}{2} = 1. \end{array} $$ In other words, we need to solve the linear system $$ \begin{array}{ccccc} s\cdot 1 &+& t\cdot 1 &=& 0\\ s\cdot\frac{1 - \sqrt{5}}{2} &+& t\cdot \frac{1 + \sqrt{5}}{2} &=& 1 \end{array} \text{, which is equivalent to } \begin{bmatrix} 1 & 1\\ \frac{1 - \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2} \end{bmatrix} \cdot \begin{bmatrix} s\\ t \end{bmatrix} = \begin{bmatrix} 0\\ 1 \end{bmatrix}. $$ Funny how we somehow ended up with a linear algebra problem, right? In any event, we know how to solve this! $$ \begin{bmatrix} 1 & 1 & 0\\ \frac{1 - \sqrt{5}}{2} & \frac{1 + \sqrt{5}}{2} & 1 \end{bmatrix} \longrightarrow \begin{bmatrix} 1 & 1 & 0\\ 0 & \frac{1 + \sqrt{5}}{2} -\frac{1 - \sqrt{5}}{2} & 1 \end{bmatrix} \longrightarrow \begin{bmatrix} 1 & 1 & 0\\ 0 & \sqrt{5} & 1 \end{bmatrix} \longrightarrow \begin{array}{l} s=-\sqrt{5}/5\\ t=\sqrt{5}/5 \end{array} $$ So our solution is $ -\sqrt{5}/5\cdot \left(\frac{1 - \sqrt{5}}{2}\right)^n + \sqrt{5}/5\cdot \left(\frac{1 + \sqrt{5}}{2}\right)^n = \sqrt{5}/5\cdot \left( \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right). $ In other words, the fibonacci sequence has closed form $$ f(n) = \sqrt{5}/5\cdot \left( \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right) $$ ... which is pretty crazy! You can test it for yourself using the unix command line tool bc.

$ bc -lq
n=0
sqrt(5)/5*(((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
0
n=6
sqrt(5)/5*(((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
7.99999999999999999983
n=20
sqrt(5)/5*(((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
6764.99999999999999958869

Putting a bow on it

Hopefully you appreciate what we did in this lecture. We started with one topic, recurrence relations, which led us to algebra (aka rings), and of course that led to proof (for the theorem about linear combinations of solutions), and ultimately we ended up with a linear system, a matrix equation and gaussian elimination. And what we got out of it was something that, at least for me when I first saw it, was totally unexpected. Not only that we have a closed form, but that this crazy expression with exponents and square roots of five always gives us integer results.