Skip to main content

Section 5.2 Recurrence relations

Previously, we saw that the sequence \((n!)_0^\infty\) of factorials has both a closed form representation and a recursive representation.

Consider the sequence \((n!)_{n=0}^\infty\) of factorials. Since

\begin{equation*} n! = n \times \big( (n-1) \times (n-2) \times \cdots \times 2 \times 1 \big) = n(n-1)! \end{equation*}

we can express \(n!\) via the “recurrence relation”

\begin{equation*} n! = \begin{cases} n(n-1)! \amp n \ge 1 \\ 1 \amp n = 0 \end{cases} \end{equation*}

This is read: “\(n!\) is equal to \(n(n-1)!\) when \(n \ge 1\text{,}\) and equal to \(1\) when \(n=0\text{.}\)”

Definition 5.2.2.

Consider the sequence \((a_n)_k^\infty\text{.}\) A recurrence relation is a relation that allows \(a_n\) to be calculated using the preceding terms \(a_{n-1}, a_{n-2}, \ldots, a_{k+1}, a_k\text{.}\) Some number of initial terms in the sequence, depending on the formula for the relation, must be known.

As we mentioned in our discussion on recursion, there has to be a “base case”. We must know one or more starting terms of the sequence in order to use a recurrence relation. In the case of \(n!\text{,}\) we must know that \(0!=1\text{.}\)

The Fibonacci sequence

\begin{equation*} (F_n)_{n=0}^\infty = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots) \end{equation*}

has a very difficult closed form expression. It is much easier to calculate the terms recursively by adding the prior two terms together. Therefore,

\begin{equation*} F_n = \begin{cases} F_{n-1} + F_{n-2} \amp n \ge 2 \\ 1 \amp n = 1 \\ 1 \amp n = 0 \end{cases} \end{equation*}

Notice that we require knowledge of the first two terms of the sequence, because the recurrence relation involves knowing two terms.

We can calculate the terms of a sequence given via recurrence relation in two different ways.

Definition 5.2.4.

Consider the sequence \((a_n)_k^\infty\) and suppose \(a_n\) is defined via recurrence relation. We can calculate \(a_n\) iteratively by beginning with the known terms and calculating each term of the sequence one at a time until \(a_n\) is reached.

Alternatively, we can calculate \(a_n\) recursively by starting with \(a_n\) and repeatedly using the recurrence relation to express \(a_n\) as a function of only the known terms, and then substituting those terms to find \(a_n\text{.}\)

In other words, to calculate \(a_n\) iteratively we must calculate every term of the sequence leading up to it. We only need to calculate one term of the sequence to calculate recursively, but there is a lot of preparatory work.

You might be wondering why this difference is significant. Here, it is important to remember that the target audience for this book is computer science students, where the goal may be to implement a program whereby a computer calculates \(a_n\text{.}\) There are practical considerations involved. Is it faster to do simple calculations and store a thousand terms of a sequence, or is it faster to do more complicated calculations but only need to store a few terms? Since it depends on the problem, it is good to know both methods.

Return to the Fibonacci sequence

\begin{equation*} F_n = \begin{cases} F_{n-1} + F_{n-2} \amp n \ge 2 \\ 1 \amp n = 1 \\ 1 \amp n = 0 \end{cases} \end{equation*}

and suppose we want to calculate \(F_5\text{.}\) The iterative calculation starts at \(F_0\) and “works up” to \(F_5\text{.}\)

\begin{align*} F_0 \amp = 1\\ F_1 \amp = 1\\ F_2 \amp = F_1 + F_0 = 1 + 1 = 2\\ F_3 \amp = F_2 + F_1 = 2 + 1 = 3\\ F_4 \amp = F_3 + F_2 = 3 + 2 = 5\\ F_5 \amp = F_4 + F_3 = 5 + 3 = 8 \end{align*}

So, \(F_5 = 8\text{.}\) All the calculations were relatively simple, but we needed to know six terms of the sequence in the end.

Let's try it recursively. This time we will start with \(F_5\) and continue applying the recurrence relation until we have an expression only involving the known values \(F_0\) and \(F_1\text{.}\)

\begin{align*} F_5 \amp = F_4 + F_3\\ \amp = (F_3 + F_2) + (F_2 + F_1)\\ \amp = ([F_2+F_1] + [F_1+F_0]) + ([F_1+F_0] + F_1)\\ \amp = ([(F_1+F_0)+F_1]+ [F_1+F_0])+ ([F_1+F_0] + F_1) \end{align*}

Notice the use of alternating types of brackets to aid readability.

At this point we can do two different things to calculate \(F_5\text{.}\) One thing we can do is combine like terms.

\begin{align*} F_5 \amp = ([(F_1+F_0)+F_1]+ [F_1+F_0])+ ([F_1+F_0] + F_1)\\ \amp = 5F_1 + 3F_0\\ \amp = 5(1) + 3(1)\\ \amp = 8 \end{align*}

Alternatively, we can start from the innermost pair of brackets and work outward. If we do this, something interesting happens.

\begin{align*} F_5 \amp = ([(F_1+F_0)+F_1]+ [F_1+F_0])+ ([F_1+F_0] + F_1)\\ \amp = ([(1+1)+1]+ [1+1])+ ([1+1] + 1)\\ \amp = ([2+1] + 2)+ (2 + 1)\\ \amp = (3 + 2)+ 3\\ \amp = 5+ 3\\ \amp = 8 \end{align*}

When we calculate \(F_5\) this way, the previous terms in the Fibonacci sequence appear as well. That way, if we have already done the calculation iteratively, we know what numbers to expect!

Consider the sequence \((x_n)\) where

\begin{equation*} x_n = \begin{cases} x_{n-1} - 2x_{n-2}, \amp n > 2 \\ 1 \amp n = 2, \\ -1 \amp n = 1 \end{cases} \end{equation*}

To calculate \(x_4\) iteratively, we simply calculate each term of \((x_n)\) until we arrive at \(x_4\text{.}\)

\begin{align*} x_1 \amp = -1\\ x_2 \amp = 1\\ x_3 \amp = x_2 - 2x_1 = 1 - 2(-1) = 3\\ x_4 \amp = x_3 - 2x_2 = 3 - 2(1) = 1. \end{align*}

Thus, \(x_4 = 1\text{.}\)

In the recursive calculation, we will begin with \(x_4\) and repeatedly apply the recurrence relation until we have only known values of the sequence: so, \(x_2\) and \(x_1\text{.}\)

\begin{align*} x_4 \amp = x_3 - 2x_2.\\ \amp = (x_2 - 2x_1) - 2x_2\\ \amp = (1 - 2(-1)) - 2(1)\\ \amp = 3 - 2\\ \amp = 1 \end{align*}

which agrees with our iterative calculation.

Consider the sequence \((b_k)\) where

\begin{equation*} b_k = \begin{cases} b_{k-1}2^k \amp k \ge 2 \\ 3 \amp k = 1 \end{cases} \end{equation*}

This time we will just calculate \(b_5\) recursively. You can do the iterative calculation yourself to check.

\begin{align*} b_5 \amp = b_4 2^4\\ \amp = (b_3 2^3) 2^4\\ \amp = ([b_2 2^2] 2^3) 2^4\\ \amp = ([(b_1 2^1)2^2]2^3)2^4\\ \amp = ([(3 \times 2^1)2^2]2^3)2^4\\ \amp = 3 \times 2^{10}\\ \amp = 3\times 1024\\ \amp = 3072 \end{align*}

So, \(b_5 = 3072\text{.}\)