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},\ldots ,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\rightarrow r=2$

$H_{n}=\alpha 2^{n}$ This is the homogeneous form.

$H_{n}=C\rightarrow C=2C+1\rightarrow C=-1$ This is the particular equation

${\begin{aligned}H_{n}&=\mathrm {homog} +\mathrm {particular} \\&=\alpha 2^{n}-1\end{aligned}}$