This post is mostly concerned with solving recurrences through programming. More specifically, given a homogeneous linear recurrence:
$f(n)=\sum\limits_{i=1}^{d} a_i f(n - i)$
we want to compute the value of $f(n)$ for any given integer $n$.
Fibonacci Sequence
We will use the Fibonacci sequence as a starting point: $F(n) = F(n - 1) + F(n - 2)$, with $F(1) = 1$, $F(0) = 0$. Last time we discovered a closed form solution for $F(n)$:
$F(n) = \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1 - \sqrt{5}}{2})^n$
This would allow us to compute $F(n)$ in $O(1)$ time, but suffers from precision errors when $n$ gets high. We want a solution that does not need to deal with irrational numbers. The first approach is to write the recurrence explicitly:
FIBONACCI(n):
if n = 0
return 0
if n = 1
return 1
return FIBONACCI(n - 1) + FIBONACCI(n - 2)
This works, but has the disadvantage of being very slow. If we let $T(n)$ denote the number of steps it takes to compute FIBONACCI(n), then $T(n)$ satisfies the recurrence:
$T(n) = T(n - 1) + T(n - 2)$
which, as we saw last time, has exponential growth. If we look at the recursion tree generated by the FIBONACCI function we see that we do a lot of unnecessary computation:
From the above, we see that we are computing some quantities several times. For instance, $F(n-2)$ will be called twice in the computation of $F(n)$. To avoid unnecessary computation, we introduce two variables $a$, and $b$, that will maintain intermediate results:
FIBONACCI(n, a, b):
if n = 0:
return b
if n = 1:
return a
return FIBONACCI(n - 1, a + b, a)
We just need to figure out what the initial values of $a$ and $b$ should be. But since $F(0) = 0$, we have that $b = 0$, and since $F(1) = 1$, we require $a = 1$.
As it turns out, although there is little difference between the two code blocks, the performance difference is huge. If we let $T(n)$ be the number of operations required to compute FIBONACCI(n), we have $T(n) = T(n - 1) + 1$, the $1$ coming from the evaluation of $a+b$ in the recursive call. A solution to that recurrence relation is $T(n) = n$.
Although linear is oftentimes the best we can hope for, in this case we can do better. For the extra performance boost, we have to notice the following identity:
Proof. The first half is immediate if we multiply the two. For the second half, we will proceed by induction. Denote the statement by $P(n)$. Then:Theorem 1. Define the $2x2$ matrix $C$ as:
$C = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$
Then the following identity holds:
$$ \begin{equation}\label{id} C \begin{bmatrix} F(n-1) \\ F(n) \end{bmatrix} = \begin{bmatrix} F(n) \\ F(n + 1) \end{bmatrix} \end{equation}$$
Moreover, a natural extension of this fact is:
$$ \begin{equation}\label{pow} C^n \begin{bmatrix} F(0) \\ F(1) \end{bmatrix} = \begin{bmatrix} F(n) \\ F(n + 1) \end{bmatrix} \end{equation}$$
$P(0): C^0 \begin{bmatrix} F(0) \\ F(1) \end{bmatrix} = I_{2} \begin{bmatrix} F(0) \\ F(1) \end{bmatrix} = \begin{bmatrix} F(0) \\ F(1) \end{bmatrix}$
Suppose $P(n - 1)$ holds. We write $P(n)$ as:$$ \begin{eqnarray*} P(n): C^n \begin{bmatrix} F(0) \\ F(1) \end{bmatrix} &=& C \left( C^{n-1} \begin{bmatrix} F(0) \\ F(1) \end{bmatrix} \right)\\ &=& C \begin{bmatrix} F(n - 1) \\ F(n) \end{bmatrix} = \begin{bmatrix} F(n) \\ F(n + 1) \end{bmatrix} \end{eqnarray*}$$
The second equality follows from the inductive hypothesis, while the third follows from \eqref{id}.
Corollary.
$$ \begin{equation} C^n = \begin{bmatrix} F(n-1) & F(n) \\ F(n) & F(n + 1) \end{bmatrix} \end{equation}$$
The good thing about powers is that you can compute them in logarithmic time by exploiting the following identities:
$$ \begin{eqnarray*} x^n &=& (x^{\frac{n}{2}})^2, &\forall n, \text{ n even}\\ x^n &=& x (x^\left\lfloor \frac{n}{2} \right\rfloor)^2, &\forall n, \text{ n odd} \end{eqnarray*}$$
Here is some pseudocode. In the following, $X$ can be any type that supports multiplication (including an $nxn$ matrix), and $I$ is the identity element with respect to multiplication.
FAST-POWER(X, n)
if n = 0
return I
Z <- FAST-POWER(X, n/2)
if n mod 2 = 0
return Z * Z
else
return X * Z * Z
If we let $T(n)$ denote the number of operations, we have $T(n) = T(n/2) + O(1)$, if the multiplication can be performed in constant time. This recurrence has a solution $T(n) = O(log(n))$. I will not prove this now, but intuitively, the problem size gets halved at each step.
With this, we can now proceed to our final algorithm. This computes the $n$-th Fibonacci number in $O(log(n))$ time by exploiting the properties above. $C$ is the matrix from Theorem 1.
FIBONACCI(n) Z <- FAST-POWER(C, n) return Z[1, 2]
Multiplying two $nxn$ takes $O(n^3)$ time, but since $C$ is a $2x2$ matrix, this is $O(1)$, so all we care about is the time complexity of FAST-POWER, which is $O(log(n))$.
This concludes part II of this series. In part III, we will generalize these results to other linear recurrences.
