Skip to main content

Worksheet 2.5 Worksheet: linear recurrences

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 (xn) 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
xn+k=a0xk+a1xk+1++ak1xn+k1.
(Here we assume a00 to have the appropriate length.) The most famous example of a linear recurrence is, of course, the Fibonacci sequence, which is defined by x0=1,x1=1, and xn+2=xn+xn+1 for all n0.
Recall from Example 1.1.6 that the set of all sequences of real numbers (xn)=(x0,x1,x2,) is a vector space, denoted by R.
The set of all sequences satisfying a linear recursion of length k form a subspace V of the vector space R of all real-valued sequences. (Can you prove this?) Since each sequence is determined by the k initial conditions x0,x1,,xk1, each such subspace V is isomorphic to Rk.
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 xn in the sequence.
Since we know the dimension of the space V of solutions, it suffices to understand two things:
  • How to produce a basis for V.
  • How to write a given solution in terms of that basis.
Consider a geometric sequence, of the form xn=cλn. If this sequence satisfies the recursion
xn+k=a0xn+a1xn+1++ak1xn+k1,
then (with n=0)
cλk=a0c+a1cλ++ak1λk1,
or c(λkak1λk1a1λa0)=0. That is, λ is a root of the associated polynomial
p(x)=xkak1xk1a1xa0.
Thus, if the associated polynomial p(x) has roots λ1,,λm, we know that the sequences (λ1n),,(λmn) 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λ)r is a factor of p(x), then the sequences (λn),(nλn),,(nr1λn) all satisfy the recursion.
If we can factor p(x) completely over the reals as
p(x)=(xλ1)m1(xλ2)m2(xλp)mp,
then a basis for the space of solutions is given by
(λ1n),(nλ1n),,(nm11λ1n)(λ2n),(nλ2n),,(nm21λ2n)(λpn),(nλpn),,(nmp1λpn).
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 (xn) satisfying the recurrence
xn+3=2xn+xn+1+2xn+2.
Then find a formula for the sequence satisfying the initial conditions x0=3,x1=2,x2=4.
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 λ is a root of the polynomial, then (λ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=(xn) be the recursion that satisfies the given initial conditions. We want to write (xn) in terms of the basis we just found. Since our basis has three elements, there is an isomorphism T:R3V, where T(a,b,c) is equal to the sequence (xn) in V that satisfies the initial conditions x0=a,x1=b,x2=c. Thus, our desired sequence is given by s=T(3,2,4).
Let v1,v2,v3R3 be the vectors such that B={T(v1),T(v2),T(v3)}. (That is, write out the first three terms in each sequence in your basis to get three vectors.) We then need to find scalars c1,c2,c3 such that
c1v1+c2v2+c3v3=(3,2,4).
We will then have
s=T(3,2,4)=c1T(v1)+c2T(v2)+c3T(v3),
and we recall that the sequences T(vi) are the sequences in our basis B.
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λ)k, then your basis will include the sequences (λn),(nλn),,(nk1λn).

2.

Find a basis for the space V of sequences (xn) satisfying the recurrence
xn+3=8xn12xn+1+6xn+2.
Then find a formula for the sequence satisfying the initial conditions x0=2,x1=5,x2=3.

3.

Find a basis for the space V of sequences (xn) satisfying the recurrence
xn+6=72xn+12xn+170xn+2+5xn+3+15xn+4xn+5.
Then find a formula for the sequence satisfying the initial conditions x0=1,x1=2,x2=1,x3=2,x4=3,x5=4.
You have attempted 1 of 4 activities on this page.