# CSCE 222 Lecture 22

« previous | *Wednesday, March 30, 2011* | next »

## Recurrence Relations

A **recurrence relation** for the sequence of integers is an equation that expresses as a function of some of the previous terms to starting from an integer

A **linear homogeneous recurrence** relation of **degree** with constant coefficients is of the form:

- linear
- is a linear function of the terms before it (no exponents).
- EX: is
*not*linear. - homogeneous
- every term is a multiple of
- degree
- the number of terms added to get the current .

This function can be rewritten as a series:

- where is a constant.

### Theorem

Let and be real numbers. Suppose that has 2 distinct roots and . Then has a solution iff is of the form: for constants and .

### Example 1: Fibonacci Numbers

Given and ,

The Fibonacci sequence is a **linear homogeneous** function of **degree 2**

From here, we can get .

Using the theorem, we can rewrite as a degree 2 polynomial: has roots (the golden ratio).

More complicated math can solve for the constants and . Now we can solve the Fibonacci sequence in a single formula that runs in time:

The sequence grows asymptotically according to .

### Example 2: Towers of Hanoi

Moving one disk at a time, move all disks from peg 1 to peg 3. A larger disk cannot be placed on top of a smaller one.

In order to do this, the top disks have to be moved to peg 2, the largest disk is moved to peg 3, then the top disks are moved to peg 3.

The towers of hanoi function is **linear**, but not homogeneous since we add 1.

Given , we can find , .