CSCE 222 Lecture 22

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

Recurrence Relations

A recurrence relation for the sequence of integers $\{a_{n}\}n\geq 0$ is an equation that expresses $a_{n}$ as a function of some of the previous terms $a_{0}$ to $a_{n-1}$ starting from an integer $n_{0}$

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

a_{n}=C_{1}a_{n-1}+C_{2}a_{n-2}+\ldots +C_{k}a_{n-k}

linear: $a_{i}$ is a linear function of the terms before it (no exponents).; EX: $a_{n}=a_{n-1}+a_{n-2}^{2}$ is not linear.
homogeneous: every term is a multiple of $a_{i}$
degree: the number of $a_{i}$ terms added to get the current $a_{n}$ .

This function can be rewritten as a series:

a_{n}=r^{n}

where

r

is a constant.

Theorem

Let $c_{1}$ and $c_{2}$ be real numbers. Suppose that $r^{2}-c_{1}r-c_{2}=0$ has 2 distinct roots $r_{1}$ and $r_{2}$ . Then $a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}$ has a solution $\{a_{n}\}\ n\geq 0$ iff $a_{n}$ is of the form: $a_{n}=\alpha _{1}r_{1}^{n}+\alpha _{2}r_{2}^{n}$ for constants $\alpha _{1}$ and $\alpha _{2}$ .

Example 1: Fibonacci Numbers

Given $f_{1}=1$ and $f_{2}=1$ ,

f_{n}=f_{n-1}+f_{n-2}\quad {\text{for}}\ n\geq 3

The Fibonacci sequence is a linear homogeneous function of degree 2

From here, we can get $\{1,1,2,3,5,8,13,21,34,55,89\}$ .

Using the theorem, we can rewrite $a_{n}$ as a degree 2 polynomial: $r_{1}^{2}-r_{2}-1$ has roots ${\tfrac {1\pm {\sqrt {5}}}{2}}$ (the golden ratio).

More complicated math can solve for the constants $\alpha _{1}$ and $\alpha _{2}$ . Now we can solve the Fibonacci sequence in a single formula that runs in $O(1)$ time: