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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_2} . Now we can solve the Fibonacci sequence in a single formula that runs in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(1)} time:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta\left(\left(\frac{1+\sqrt{5}}{2}\right)^n\right)} .

Example 2: Towers of Hanoi

Moving one disk at a time, move all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} disks have to be moved to peg 2, the largest disk is moved to peg 3, then the top Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} disks are moved to peg 3.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_1 = 1} , we can find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_2 = 3} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_3 = 7} .