In this worksheet, we will sketch some of the basic ideas related to linear recurrence. For further reading, and more information, the reader is directed to Section 7.5 of Linear Algebra with Applications, by Keith Nicholson.
A linear recurrence of length \(k\) is a sequence \((x_n)\) that is recursively defined, with successive terms in the sequence defined in terms of the previous \(k\) terms, via a linear recursion formula of the form
\begin{equation*}
x_{n+k} = a_0x_k + a_1x_{k+1}+\cdots + a_{k-1}x_{n+k-1}\text{.}
\end{equation*}
(Here we assume \(a_0\neq 0\) to have the appropriate length.) The most famous example of a linear recurrence is, of course, the Fibonacci sequence, which is defined by \(x_0=1, x_1=1\text{,}\) and \(x_{n+2}=x_n+x_{n+1}\) for all \(n\geq 0\text{.}\)
Recall from
Example 1.1.6 that the set of all sequences of real numbers
\((x_n)=(x_0,x_1,x_2,\ldots)\) is a vector space, denoted by
\(\R^\infty\text{.}\)
The set of all sequences satisfying a linear recursion of length \(k\) form a subspace \(V\) of the vector space \(\mathbb{R}^\infty\) of all real-valued sequences. (Can you prove this?) Since each sequence is determined by the \(k\) initial conditions \(x_0, x_1, \ldots, x_{k-1}\text{,}\) each such subspace \(V\) is isomorphic to \(\mathbb{R}^k\text{.}\)
The goal of this worksheeet is to understand how to obtain closed form expressions for a recursively defined sequence using linear algebra. That is, rather than having to generate terms of the sequence one-by-one using the recursion formula, we want a function of \(n\) that will produce each term \(x_n\) in the sequence.
Since we know the dimension of the space \(V\) of solutions, it suffices to understand two things:
Consider a geometric sequence, of the form \(x_n=c\lambda^n\text{.}\) If this sequence satisfies the recursion
\begin{equation*}
x_{n+k} = a_0x_n + a_1x_{n+1}+\cdots + a_{k-1}x_{n+k-1}\text{,}
\end{equation*}
then (with \(n=0\))
\begin{equation*}
c\lambda^k=a_0c+a_1c\lambda+\cdots+a_{k-1}\lambda^{k-1}\text{,}
\end{equation*}
or \(c(\lambda^k-a_{k-1}\lambda^{k-1}-\cdots - a_1\lambda-a_0)=0\text{.}\) That is, \(\lambda\) is a root of the associated polynomial
\begin{equation*}
p(x) = x^k - a_{k-1}x^{k-1}-\cdots -a_1x-a_0\text{.}
\end{equation*}
Thus, if the associated polynomial \(p(x)\) has roots \(\lambda_1,\ldots, \lambda_m\text{,}\) we know that the sequences \((\lambda_1^n),\ldots, (\lambda_m^n)\) satisfy our recursion. The remaining difficulty is what to do when \(p(x)\) has repeated roots. We will not prove it here, but if \((x-\lambda)^r\) is a factor of \(p(x)\text{,}\) then the sequences \((\lambda^n),(n\lambda^n),\ldots, (n^{r-1}\lambda^n)\) all satisfy the recursion.
If we can factor \(p(x)\) completely over the reals as
\begin{equation*}
p(x) = (x-\lambda_1)^{m_1}(x-\lambda_2)^{m_2}\cdots (x-\lambda_p)^{m_p}\text{,}
\end{equation*}
then a basis for the space of solutions is given by
\begin{align*}
\left(\lambda_1^n\right), \amp \left(n\lambda_1^n\right),\ldots, \left(n^{m_1-1}\lambda_1^n\right)\\
\left(\lambda_2^n\right), \amp \left(n\lambda_2^n\right),\ldots, \left(n^{m_2-1}\lambda_2^n\right)\\
\amp \vdots \\
\left(\lambda_p^n\right), \amp \left(n\lambda_p^n\right),\ldots, \left(n^{m_p-1}\lambda_p^n\right)\text{.}
\end{align*}
Once we have a basis, we can apply the given coefficients to determine how to write a particular sequence as a linear combination of the basis vectors.
