MATH 302 Lecture 16

« previous | Monday, October 24, 2011 | next »

Solving Recurrence Relations

Linear Homogeneous Recurrence Relation of Degree $k$ with constant coefficients:

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\dots +c_k{a}_{n-k}$, where $c_1,\dots ,c_k$ are constants.

We want to describe $a_n=\alpha r^n$ in terms of a single equation without any recursion.

$\alpha r^n=c_1\alpha r^{n-1}+c_2\alpha r^{n-2}+\dots +c_k\alpha r^{n-k}$

Bring all terms to the left-hand side

$\cancel{\alpha r^{n-k}}(r^k-c_1{r}^{k-1}-c_2{r}^{k-2}-\dots -c_k)=0$

The parenthesized polynomial is called the characteristic equation.

2 Cases for characteristic equation:

1. distinct characteristic roots (Theorems 1 & 3)
2. nondistinct characteristic roots (Theorems 2 & 4)

---

How many ways are there to tile a 2 × n surface area with two types of tiles: 2 × 2 and 2 × 1 . . .

---

Take a non-homogeneous recurrence relation. Dropping anything that has nothing to do with recursion results in the associated homogeneous equation. Solve this:

• Recurrence Relation: $H_n=2H_{n-1}+1$
• Assoc. Homog. Eq: $H_n=2H_{n-1}$

$r-2=0\to r=2$

$H_n=\alpha 2^n$ This is the homogeneous form.

$H_n=C\to C=2C+1\to C=-1$ This is the particular equation

$\begin{array}{rl}{H}_n& =\mathrm{h}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{g}+\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}\\ & =\alpha 2^n-1\end{array}$