Recurrence Relations
A recurrence relation is an equation that uses recursion to relate terms in a sequence or elements in an array. It is a way to define a sequence or array in terms of itself. Recurrence relations have applications in many areas of mathematics:
- number theory - the Fibonacci sequence
- combinatorics - distribution of objects into bins
- calculus - Euler's method
- and many more.
Recurrence relations are used when an exhaustive approach to problem solving is simply too arduous to be practical. Although it is not ideal to compute the terms in a sequence one at a time by using previous terms, this approach can be much more efficient than the alternative of exhaustive casework.
Sometimes, a recurrence relation can be "solved" by defining the terms of a sequence in terms of its index rather than previous terms in the sequence. This gives a closed form expression for each term in the sequence and eliminates the need for an iterative process to solve for terms in the sequence. There are several ways to accomplish this:
- solving linear recurrence relations
- solving recurrence relations with generating functions
- solving recurrence relations with the substitution method
- solving recurrence relations with the method of summation factors.
Even if a solution of this form is not possible, a recurrence relation is still useful, as it can be used to develop computer algorithms. When terms in a sequence are stored, dynamic programming allows one to compute new terms in a sequence efficiently. Recurrence relations are also applicable for recursive backtracking, in which recursion is used to optimize algorithms.
Contents
Setting up a Recurrence Relation
Recurrence relations are used to reduce complicated problems to an iterative process based on simpler versions of the problem. An example problem in which this approach can be used is the Tower of Hanoi puzzle.
The Tower of Hanoi puzzle consists of three vertical pegs and several disks of various sizes. Each disk has a hole in its center for the pegs to go through.
A Tower of Hanoi puzzle with 8 disks
The rules of the puzzle are as follows:
The puzzle begins with all disks placed on one of the pegs. They are placed in order of largest to smallest, bottom to top.
The goal of the puzzle is to move all of the disks onto another peg.
Only one disk may be moved at a time, and disks are always placed onto pegs.
Disks may only be moved onto an empty peg or onto a larger disk.
Let \(T_n\) be defined as the minimum number of moves needed to solve a puzzle with \(n\) disks.
Image Credit: Ævar Arnfjörð Bjarmason, Wikimedia Commons
It's not immediately clear that a recursion solution will work for this problem. However, there are a couple things about this problem that make it a good candidate to solve with a recurrence relation.
Identifying a candidate problem to solve with a recurrence relation:
- The problem can be reduced to simpler cases. The Tower of Hanoi puzzle can be simplified by removing some of the disks.
- There is a numerical value, \(n\), to identify each case. For the Tower of Hanoi puzzle, this numerical value is the number of disks.
- The problem increases in complexity as the numerical identifier increases. As the number of disks in the Tower of Hanoi problem increases, it becomes more difficult to find a solution.
The goal for this exercise will be to develop a recurrence relation for \(T_n\). Rather than try to tackle a complicated puzzle, like the one with 8 disks pictured above, it is often best to start off with the most simple version of the problem possible.
Step 1: Define a Base Case
The most simple version of the Tower of Hanoi puzzle would contain only one disk.
In terms of the recurrence relation, \(n=1\).
\(T_1=1\), because it would only take \(1\) move to move all the disks to another peg.
The base case is often trivially simple. However, it will be necessary for developing more complicated cases. Even though the goal of this exercise is to come up with an equation for \(T_n\), it's not immediately clear what that equation will look like. It's necessary to do casework to get an understanding of how the problem works. After a couple of cases have been completed, one starts to develop an understanding of how to set up the recurrence relation.
Step 2: Develop More Complicated Cases
Below is the solution to a Tower of Hanoi puzzle with \(n=2\).
It can be seen from above that \(T_2=3\).
Below is a solution to a Tower of Hanoi puzzle with \(n=3\).
It can be seen from above that \(T_3=7\).
You can continue developing more complicated cases as needed. The goal of this process is to understand how the problem works, and to begin to think about how to set up the recurrence relation.
Although two cases were analyzed in the example above, it may sometimes be necessary to develop more cases in order to gain a better understanding of the problem. With the two cases above, one can probably begin to see how the cases are related to each other.
Step 3: Write the Recurrence Relation
Think about how the cases are related to each other.
With \(n=1\), it was a simple matter to move the disk once, and then the puzzle was complete.
With \(n=2\), the smaller disk had to be moved before the larger disk could be moved. Then, the smaller disk was placed on the larger disk to complete the puzzle.
With \(n=3\), the smaller disks had to be moved before the largest disk could be moved. Then, the smaller disks were placed on the larger disk to complete the puzzle.
One can begin to see a pattern in how these solutions are structured. You move the smaller disks, then you move the largest disk, then you move the smaller disks back onto the largest disk to complete the puzzle.
In terms of \(n\),
Do \(T_{n-1}\) moves to get the smaller disks off the largest disk.
Do \(1\) move to move the largest disk.
Do \(T_{n-1}\) moves to get the smaller disks back onto the largest disk.
In total, the number of moves for \(n\) disks is
\[T_n=2T_{n-1}+1.\]
One can confirm the recurrence relation written above by matching it to the known values of \(T_n\):
\[\begin{align} T_1&=1\\ T_2&=2T_1+1=2(1)+1=3\\ T_3&=2T_2+1=2(3)+1=7. \end{align}\]
The recurrence relation for the Tower of Hanoi puzzle is an example of a linear recurrence relation. It can be put into a closed form solution using the techniques discussed in the given link.
A string of \(n\) characters is made from the characters \(\text{A}\), \(\text{B}\), and \(\text{C}\).
Let \(G_n\) be the number of such strings of \(n\) characters which contain no instance of \(\text{AB}\) (in that order).
Write a recurrence relation for \(G_n\).
Applications of Recurrence Relations
Number Theory
Combinatorics
Calculus
Computer Science
Using Generating Functions to Solve Recurrence Relations
Main Article: Using Generating Functions to Solve Recurrence Relations
One method to solve recurrence relations is to use a generating function.
A generating function is a power series whose coefficients correspond to terms in a sequence of numbers.
What is the generating function of the Fibonacci sequence?
The generating function of the Fibonacci sequence is
\[f(x)=\sum_{n=0}^\infty F_n x^n = 1 + x + 2x^2 + 3x^3 + 5x^4+\cdots, \]
where \(F_n\) is the \(n^{\text{th}}\) Fibonacci number. Using techniques demonstrated here, it can be shown that this generating function has a closed form expression
\[f(x)=\sum_{n=0}^\infty F_n x^n =\frac{1}{1 - x - x^2}.\ _\square\]
Use the generating function of \(T_n\) to write a closed form expression for \(T_n\).
Recall the recurrence relation for \(T_n\):
\[T_{n+1} = 2T_{n}+1.\]
It has already been established that \(T_1=1\), but a value for \(T_0\) is also required. Let \(T_0 = 0\), and note that the recurrence relation still holds.
Define the generating function:
\[\begin{align} T(x) &= \sum\limits_{n = 0}^{\infty} T_n x^n \\ \\ &= T_0 + T_1 x + T_2 x^2 + \cdots. \end{align}\]
Recall that \(T_0=0\). Divide both sides of the equation by \(x\), which gives
\[\begin{align} \frac{T(x)}{x} &= T_1 + T_2 x + T_3 x^2 + \cdots \\ \\ &= \sum\limits_{n=0}^{\infty} T_{n+1} x^n. \end{align}\]
Now substitute the recurrence relation for \(T_{n+1}\) into the equation:
\[\begin{align} \frac{T(x)}{x} &= \sum\limits_{n = 0}^{\infty} (2T_{n}+1 )x^n \\ \\ &= 2T(x) + \sum\limits_{n = 0}^{\infty} x^n. \end{align}\]
Provided that \(|x|<1\), the series above converges as an infinite geometric progression:
\[\sum\limits_{n=0}^{\infty}x^n=\frac{1}{1-x},\ \, |x|<1.\]
Substituting this expression gives
\[\frac{T(x)}{x} = 2T(x) + \frac{1}{1-x},\ \, |x|<1.\]
Solving for \(T(x)\),
\[T(x) = \frac{x}{(1-x)(1-2x)},\ \, |x|<1.\]
Now that a closed form expression for the generating function has been found, the goal shifts to finding a closed-form expression for \(T_n\).
As the generating function is equal to a rational expression with binomial factors in the denominator, a good starting point would be to do partial fraction decomposition:
\[\begin{align} T(x)&=\frac{x}{(1-x)(1-2x)} \\ \\ &= x\left( \frac{2}{1-2x} - \frac{1}{1-x}\right). \end{align}\]
Recall infinite geometric progressions. For the next step, the two rational expressions are put back into power series form using the identities:
\[\begin{align} \frac{2}{1-2x}&=\sum\limits_{n=0}^{\infty}{2^{n+1}x^n} \\ \\ \frac{1}{1-x}&=\sum\limits_{n=0}^{\infty}x^n. \end{align}\]
Substituting these identities gives
\[\begin{align} T(x) &= x\left(\sum\limits_{n=0}^{\infty}{2^{n+1}x^n}-\sum\limits_{n=0}^{\infty}x^n \right) \\ \\ &=\sum\limits_{n=0}^{\infty}{(2^{n+1}-1)x^{n+1}} \\ \\ &=\sum\limits_{n=1}^{\infty}{(2^{n}-1)x^{n}}. \end{align}\]
From here, it is clear that the coefficient of the generating function \((\)the series \(T_n)\) is given by
\[\boxed{T_n = 2^{n}-1}.\ _\square\]
Method of Summation Factors
Main Article: Method of Summation Factors
There is another way of solving recurrence relations of the form \(Aa_n = Ba_{n-1} + C\), where \(A\), \(B\) and \(C\) are functions of \(n\), known as the method of summation factors.
This method can be used in the Tower of Hanoi problem, resolved once more in the example below.
Show that the closed form of the recurrence relation \(T_0 = 0\), \(T_n = 2T_{n-1} + 1\) is \(T_n = 2^n - 1\).
The summation factor \(s_n\) with \(A(n) = 1\) and \(B(n) = 2\) is
\[s_n = \frac{1 \cdot 1 \cdot \cdots \cdot 1}{2 \cdot 2 \cdot \cdots \cdot 2} = \frac{1}{2^{n-1}},\]
where the 1's and 2's occur \(n-1\) times each. Multiplying this to the recurrence relation gives
\[\frac{1}{2^{n-1}} T_n = \frac{1}{2^{n-2}}T_{n-1} + \frac{1}{2^{n-1}}.\]
Let \(b_n = \dfrac{1}{2^{n-1}} T_n\). Then \(b_{n - 1} = \dfrac{1}{2^{n-2}}T_{n-1}\) and \(b_0 = \dfrac{1}{2^{0-1}} T_0 = 0\). So,
\[b_n = b_{n - 1} + \frac{1}{2^{n-1}}.\]
It follows that the closed form of \(b_n\) is
\[b_n = 0 + \sum_{k = 1}^n \frac{1}{2^{k-1}} = \frac{1 \cdot \left(\frac12\right)^n - 1}{\frac12 - 1} = 2 - \frac{1}{2^{n - 1}}.\]
Note that the summation above is a finite geometric series. But since \(b_n = \dfrac{1}{2^{n-1}} T_n\), the closed form of \(T_n\) is therefore
\[T_n = 2^{n - 1} \left( 2 - \frac{1}{2^{n - 1}} \right) = \boxed{2^n - 1}.\ _\square\]