In this section, we learn the basics of recurrence relations.

Definition (Recurrence relation). A recurrence relation is an equation that defines a sequence \(\{a_n\}\) by writing \(a_n\) in terms of one or more of the preceding terms \(a_{n-1},a_{n-2},\ldots,a_1,a_0\). A solution of a recurrence relation is a sequence whose terms satisfy the recurrence relation. The explicit values of the first few terms of a solution sequence that make the solution unique are the initial conditions of the recurrence relation.

Example. \(a_n=2a_{n-1}-a_{n-2},\;n\geq 2\) is a recurrence relation. The sequence \(\{3n\}\) is a solution because \[3n=2\cdot 3(n-1)-3(n-2).\] The sequence \(\{5\}\) is also a solution because \[5=2\cdot 5-5.\] If the recurrence relation has the initial conditions \(a_0=0,\; a_1=3\), then the unique solution is \(\{3n\}\).

Example. The Fibonacci sequence \(\{F_n\}\) is given by the following recurrence relation: \[F_n=F_{n-1}+F_{n-2},\; n\geq 2,\] together with the initial conditions \(F_0=0,\; F_1=1\). By iteration we can generate first few terms of \(\{F_n\}\) as follows: \[\begin{eqnarray*} F_2 &=& F_1+F_0=1+0=1\\ F_3 &=& F_2+F_1=1+1=2\\ F_4 &=& F_3+F_2=2+1=3\\ F_5 &=& F_4+F_3=3+2=5\\ F_6 &=& F_5+F_4=5+3=8\\ \end{eqnarray*}\]

To see the usefulness of recurrence relations, we discuss the following puzzle.

The tower of Hanoi:
The tower of Hanoi is a puzzle consists of three pegs or rods mounted on a board and \(n\) disks of different sizes initially placed on a peg in the decreasing order of their sizes (the largest disk at the bottom). The objective of the puzzle is to move all the \(n\) disks to a different peg and stack them in the decreasing order of their sizes (the largest disk at the bottom). The rule of the puzzle is to move one disk at a time and place it on a different peg with no disks or on top of a bigger disk on a different peg.

We find \(H_n\), the number of moves needed to solve the puzzle for \(n\) disks. Note that \(H_1=1\). To find a recurrence relation for \(\{H_n\}\), we solve the puzzle in the following three steps where the disks are initially stacked on peg 1:

1. Transfer the top \(n-1\) disks from peg 1 to peg 2. This requires \(H_{n-1}\) moves.


2. Move the largest disk from peg 1 to peg 3.


3. Transfer \(n-1\) disks from peg 2 to peg 3. This requires \(H_{n-1}\) moves.

Thus the total number of moves is \[H_n=2H_{n-1}+1.\] Now we solve this recurrence relation by iteration as follows: \[\begin{eqnarray*} H_n &=& 2H_{n-1}+1\\ &=& 2(2H_{n-2}+1)+1=2^2H_{n-2}+2+1\\ &=& 2^2(2H_{n-3}+1)+2+1=2^3H_{n-3}+2^2+2+1\\ &=& \cdots\\ &=& 2^{n-1}H_1+2^{n-2}+\cdots +2^2+2+1 \end{eqnarray*}\] Using the initial condition \(H_1=1\), we get \[H_n=2^{n-1}+2^{n-2}+\cdots +2^2+2+1=2^n-1.\] There is a myth that monks in a tower of Hanoi started to solve this puzzle with 64 golden disks and the world will end before they solve the puzzle. If it takes one second per move, then it will take \(2^{64} -1 \) seconds which is more than 580 billion years.

Last edited