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.

• 5, 10, 15, 20, 25, . . .
• 2, 4, 8, 16, . . .
• 10, 7, 4, 1, . . .
• 80, 20, 5, . . .
• the number of people that can be seated at k square tables lined up adjacent to one another, under the condition that one person sits at each available side of a table.

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