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.
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\).
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