Discrete Math Home

## Linear Recurrence Relations

In this section, we learn how to solve a particular type of recurrence relations called linear recurrence relations.

Definition (Linear recurrence relation). A linear homogeneous recurrence relation of degree $$k$$ is a recurrence relation of the form $a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k},$ where $$c_1,c_2,\ldots,c_k$$ are constants and $$c_k\neq 0$$. Its characteristic equation is $r^k=c_1r^{k-1}+c_2r^{k-2}+\cdots+c_k.$

Example.

1. $$a_n=-a_{n-1}+6a_{n-2}$$
The above recurrence relation is a linear homogeneous recurrence relation of degree $$2$$. Its characteristic equation is $$r^2=-r+6$$.

2. $$a_n=4a_{n-1}+3a_{n-2}-18a_{n-3}$$
The above recurrence relation is a linear homogeneous recurrence relation of degree $$3$$. Its characteristic equation is $$r^3=4r^2+3r-18$$.

Theorem. Consider the recurrence relation $$a_n=c_1a_{n-1}+c_2a_{n-2}$$. Suppose its characteristic equation $$r^2=c_1r+c_2$$ has two distinct roots $$r_1$$ and $$r_2$$. Then a solution of this recurrence relation is $$\{a_n\}$$ where $a_n=d_1r_1^n+d_2r_2^n,$ for some constants $$d_1$$ and $$d_2$$.

$\begin{eqnarray*} c_1a_{n-1}+c_2a_{n-2} &=& c_1 \left(d_1r_1^{n-1}+d_2r_2^{n-1}\right)+c_2\left(d_1r_1^{n-2}+d_2r_2^{n-2}\right)\\ &=& d_1r_1^{n-2} \left(c_1r_1+c_2\right)+ d_2r_2^{n-2} \left(c_1r_2+c_2\right)\\ &=& d_1r_1^{n-2} r_1^2+ d_2r_2^{n-2} r_2^2 \;\;(\text{since } r_1 \text{ and } r_2 \text{ are roots of }r^2=c_1r+c_2)\\ &=& d_1r_1^n+d_2r_2^n\\ &=& a_n \end{eqnarray*}$

Example. Solve the recurrence relation $$a_n=-a_{n-1}+6a_{n-2}$$, $$a_0=3$$, $$a_1=16$$.

Solution. The characteristic equation is $$r^2=-r+6$$. $\begin{eqnarray*} r^2+r-6 &=& 0\\ (r-2)(r+3) &=& 0\\ r&=&2,-3 \end{eqnarray*}$ Then $a_n=d_1 2^n+d_2 (-3)^n,$ for some constants $$d_1$$ and $$d_2$$. Using the initial conditions $$a_0=3$$, $$a_1=16$$, we have $\begin{eqnarray*} d_1+d_2 &=& 3\\ 2d_1-3d_2 &=& 16. \end{eqnarray*}$ Solving these equations, we get $$d_1=5$$ and $$d_2=-2$$. Thus $a_n=5\cdot 2^n-2 (-3)^n,\; n=0,1,2,\ldots.$

Example. Find an explicit formula for the $$n$$th term of the Fibonacci sequence.

Solution. The Fibonacci sequence $$\{F_n\}$$ is given by the following recurrence relation: $F_n=F_{n-1}+F_{n-2},\; n\geq 2;\; F_0=0,\; F_1=1$ Its characteristic equation is $$r^2=r+1$$. $\begin{eqnarray*} r^2-r-1 &=& 0\\ r&=&\frac{1+\sqrt{5}}{2}, \frac{1-\sqrt{5}}{2} \end{eqnarray*}$ Then $F_n=d_1 \left( \frac{1+\sqrt{5}}{2} \right)^n+d_2 \left( \frac{1-\sqrt{5}}{2} \right)^n,$ for some constants $$d_1$$ and $$d_2$$. Using the initial conditions $$F_0=0$$, $$F_1=1$$, we have $\begin{eqnarray*} d_1+d_2 &=& 0\\ \left( \frac{1+\sqrt{5}}{2} \right)d_1+\left( \frac{1-\sqrt{5}}{2} \right)d_2 &=& 1. \end{eqnarray*}$ Solving these equations, we get $$d_1=\frac{1}{\sqrt{5}}$$ and $$d_2=-\frac{1}{\sqrt{5}}$$. Thus $F_n=\frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n -\frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2} \right)^n,\; n=0,1,2,\ldots.$

In the last theorem and examples, two roots are distinct. The following theorem covers the general case of any number of roots with all possible multiplicities.

Theorem. Consider the recurrence relation $$a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}$$. Suppose its characteristic equation $$r^k=c_1r^{k-1}+c_2r^{k-2}+\cdots+c_k$$ has $$t$$ distinct roots $$r_1,r_2,\ldots,r_t$$ with multiplicities $$m_1,m_2,\ldots,m_t$$ respectively. Then a solution of this recurrence relation is $$\{a_n\}$$ where $\begin{eqnarray*} a_n= && \left( d_{1,0}+d_{1,1}n+\cdots+d_{1,m_1-1}n^{m_1-1} \right)r_1^n\\ &+& \left( d_{2,0}+d_{2,1}n+\cdots+d_{2,m_2-1}n^{m_2-1} \right)r_2^n\\ &\vdots& \\ &+& \left( d_{t,0}+d_{t,1}n+\cdots+d_{t,m_t-1}n^{m_t-1} \right)r_t^n, \end{eqnarray*}$ for some constants $$d_{i,j}$$, $$1\leq i\leq t$$, $$0\leq j\leq m_i-1$$.

Example. Solve the recurrence relation $$a_n=4a_{n-1}+3a_{n-2}-18a_{n-3}$$, $$a_0=8$$, $$a_1=3$$, $$a_2=21$$.

Solution. The characteristic equation is $$r^3=4r^2+3r-18$$. $\begin{eqnarray*} r^3-4r^2-3r+18 &=& 0\\ (r+2)(r-3)^2 &=& 0\\ r&=&-2,3,3 \end{eqnarray*}$ Then $a_n=d_1 (-2)^n+(d_2+d_3n) 3^n,$ for some constants $$d_1$$, $$d_2$$, and $$d_3$$. Using the initial conditions $$a_0=8$$, $$a_1=3$$, $$a_2=21$$, we have $\begin{array}{rcrcrcr} d_1&+&d_2& & &=& 8\\ -2d_1&+&3d_2&+&3d_3 &=& 3\\ 4d_1&+&9d_2&+&18d_3 &=& 21 \end{array}$ Solving these equations, we get $$d_1=3$$, $$d_2=5$$, and $$d_3=-2$$. Thus $a_n=3 (-2)^n+(5-2n) 3^n,\; n=0,1,2,\ldots.$

Last edited