CSCE 222 Lecture 22

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

Recurrence Relations

A recurrence relation for the sequence of integers $\{a_n\}n\ge 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}+\dots +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\ge 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}\text{for}n\ge 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 $\frac{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:

$f_n={\alpha }_1{\left(\frac{1+\sqrt{5}}{2}\right)}^n+{\alpha }_2{\left(\frac{1-\sqrt{5}}{2}\right)}^n$

The sequence grows asymptotically according to $\mathrm{\Theta }\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n\right)$.

Example 2: Towers of Hanoi

Moving one disk at a time, move all $n$ 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 $n-1$ disks have to be moved to peg 2, the largest disk is moved to peg 3, then the top $n-1$ disks are moved to peg 3.

$H_n=H_{n-1}+1+H_{n-1}=2H_{n-1}+1=2^n-1$

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

Given $H_1=1$, we can find $H_2=3$, $H_3=7$.