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.
1.
Find a basis for the space \(V\) of sequences \((x_n)\) satisfying the recurrence
\begin{equation*}
x_{n+3}=-2x_n+x_{n+1}+2x_{n+2}\text{.}
\end{equation*}
Then find a formula for the sequence satisfying the initial conditions \(x_0=3, x_1=-2, x_2=4\text{.}\)
To solve this problem, you may use Python code, as outlined below. To get started, load the functions you’ll need from the SymPy library.
First, determine the associated polynomial for the recurrence.
(Input your polynomial in the cell below. To get proper formatting, wrap your math in $ delimiters, and can use ^ to enter exponents.)
Next, factor the polynomial. You can do this using the factor() command. In Python, you will need to enter ** for the exponents.
In the cell below, list the roots of the polynomial, and the resulting basis \(B\) for the space \(V\) of solutions. Recall that if \(\lambda\) is a root of the polynomial, then \((\lambda^n)\) will be a basis vector for the vector space \(V\) of solutions. You may wish to confirm that each of your basis sequences indeed satisfies our recursion.
Next, let \(s=(x_n)\) be the recursion that satisfies the given initial conditions. We want to write \((x_n)\) in terms of the basis we just found. Since our basis has three elements, there is an isomorphism \(T:\R^3\to V\text{,}\) where \(T(a,b,c)\) is equal to the sequence \((x_n)\) in \(V\) that satisfies the initial conditions \(x_0=a, x_1=b, x_2=c\text{.}\) Thus, our desired sequence is given by \(s=T(1,2,1)\text{.}\)
Let \(\vv_1, \vv_2, \vv_3\in\R^3\) be the vectors such that \(B=\{T(\vv_1), T(\vv_2), T(\vv_3)\}\text{.}\) (That is, write out the first three terms in each sequence in your basis to get three vectors.) We then need to find scalars \(c_1,c_2,c_3\) such that
\begin{equation*}
c_1\vv_1+c_2\vv_2+c_3\vv_3=(1,2,1)\text{.}
\end{equation*}
We will then have
\begin{align*}
s \amp = T(1,2,1)\\
\amp = c_1T(\vv_1)+c_2T(\vv_2)+c_3T(\vv_3)\text{,}
\end{align*}
and we recall that the sequences \(T(\vv_i)\) are the sequences in our basis \(B\text{.}\)
Set up this system, and then use the computer to solve. Let A be the coefficient matrix for the system, which you will need to input into the cell below, and let B be the column vector containing the initial conditions.
Using the solution above, state the answer to this exercise.
Now, we leave you with a few more exercises. Recall that if the associated polynomial for your recursion has a repeated root \((x-\lambda)^k\text{,}\) then your basis will include the sequences \((\lambda^n), (n\lambda^n), \ldots, (n^{k-1}\lambda^n)\text{.}\)
