Blog Post 4

\(1\) \(\underline{\text{Recurrence Relations}}\) Throughout one’s education and as one progresses through grade levels, a common math problem that students are faced with are puzzles in which they have to determine what number comes next in a sequence. For example, a teacher may ask a student to fill in the missing number given the following:

\[1,4,5,9,14 \underline{\hspace{1cm}}, ...\]

A student may then notice a pattern of adding the two terms before to get to the next. This idea, at its very core, is an illustration of a recurrence relation.

Defined mathematically, a recurrence relation is an equation in which the next term in the sequence is dependent upon or acts as a function of the previous term(s).

Using the case above, and applying it to recurrence relations, we would write the relation as: \(a_n=a_{n-1}+a_{n-2}\) where the initial conditions are \(a_0=1\) and \(a_1=4\).

Some of the more well known examples from the study of discrete mathematics include the Fibonacci sequence as well as binomial coefficients. While the Fibonacci sequence defined by \(F_n=F_{n-1}+F_{n-2}\) where \(F_1=F_2=1\) is fairly easy to recognize as a recurrence relation, binomial coefficients are not primarily described in this way. However, we see from the following illustration that they can, indeed, be accepted as following a recurrence relation. \[{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\]

A game that has been derived from the idea of recurrence relations that some may find entertaining is called the Tower of Hanoi. This was invented by Edouard Lucas in 1883. If this name sounds familiar, it is because Edouard Lucas is more famously known for his recurrence relation called the Lucas Numbers, which follow the same relation as the Fibonacci sequence. In this game, there are a certain number of disks and three “towers.” The objective is to move all the disks stacked on one tower over to another without placing larger disks on smaller ones. An illustration can be seen as such:

Pictured (above) is the Tower of Hanoi.

If you were to try to solve the puzzle with a small number of disks, say \(1\) disk, \(2\) disks, or \(3\) disks, you would find that \(T_1=1, T_2=3\), and \(T_3=7\) where \(T_n\) is the minimum number of moves required to solve the problem with \(n\) disks. It may also be helpful to note that \(T_0=0\). With this information, one can find that the recurrence relation that is followed is \(T_n=2T_{n-1}+1\), where the next term in the sequence depends on the one before it.