Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers



Recurrence Relations


When we wrapped up our discussion of derangements, we illustrated a recurrence relationship to describe the derangement of n objects. Earlier in the course we introduced the idea of recursion in the context of Fibonacci's Sequence. We also justified Pascal's Formula as a recurrence relation. Here we review and extend the ideas of recursion.

We first develop a recurrence relation for a pattern in Pascal's Triangle.

Let's write a recurrence relation for the sum of the elements in column 1 of the triangle. That is, find a recurrence relation to represent the values 1, 1+2=3, 1+2+3=6, 1+2+3+4=10, and so on.

We first identify the initial conditions. Here, we can use S(1)=1 to indicate that the first sum is 1. Now, how can we use that term to get to the next one?

We want S(2) to be represented in terms of S(1), if possible. We note that S(2) = S(1) + 2 = 3. We also note that the Sum #2 is generated by adding 2 to Sum #1.

In general, the nth sum, S(n), is found by adding n to the (n-1)th sum. That is, S(n) = S(n -1) + n. This is a recurrence relationship to describe the sums of the elements in the first column of Pascal's Triangle.

Try to determine a recursion relationship for each of the following sequences or situations.

Now determine an explicit representation for each of the sequences or situations above, including that of the sum of column 1 in Pascal's Triangle.

Here are other situations for which recurrence relations are useful.

The Tower of Hanoi Problem

The object here is to move all of the rings to the right most peg. You may only move one ring at a time, you must never allow a large ring to rest on a smaller ring. Write a recurrence relation H(n) to describe the number of moves required when the left tower has n rings on it. Include initial conditions.

Balance due on a Loan

An $80,000 loan is to be paid off in monthly installments of $629. Annual interest is 7%, computed each month. Write a recurrence relation b(n) to describe the balance due on the loan after n payments. Include initial conditions.


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes