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 is a sequence that is recursively defined, with successive terms in the sequence defined in terms of the previous terms, via a linear recursion formula of the form
(Here we assume to have the appropriate length.) The most famous example of a linear recurrence is, of course, the Fibonacci sequence, which is defined by and for all
Recall from Example 1.1.6 that the set of all sequences of real numbers is a vector space, denoted by
The set of all sequences satisfying a linear recursion of length form a subspace of the vector space of all real-valued sequences. (Can you prove this?) Since each sequence is determined by the initial conditions each such subspace is isomorphic to
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 that will produce each term in the sequence.
Since we know the dimension of the space of solutions, it suffices to understand two things:
- How to produce a basis for
- How to write a given solution in terms of that basis.
Consider a geometric sequence, of the form If this sequence satisfies the recursion
then (with )
Thus, if the associated polynomial has roots we know that the sequences satisfy our recursion. The remaining difficulty is what to do when has repeated roots. We will not prove it here, but if is a factor of then the sequences all satisfy the recursion.
If we can factor completely over the reals as
then a basis for the space of solutions is given by
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.
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.
xxxxxxxxxx
from sympy import symbols,factor,init_printing
x = symbols('x')
init_printing()
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.)xxxxxxxxxx
Next, factor the polynomial. You can do this using the
factor()
command. In Python, you will need to enter **
for the exponents.xxxxxxxxxx
In the cell below, list the roots of the polynomial, and the resulting basis for the space of solutions. Recall that if is a root of the polynomial, then will be a basis vector for the vector space of solutions. You may wish to confirm that each of your basis sequences indeed satisfies our recursion.
xxxxxxxxxx
Next, let be the recursion that satisfies the given initial conditions. We want to write in terms of the basis we just found. Since our basis has three elements, there is an isomorphism where is equal to the sequence in that satisfies the initial conditions Thus, our desired sequence is given by
Let be the vectors such that (That is, write out the first three terms in each sequence in your basis to get three vectors.) We then need to find scalars such that
We will then have
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.xxxxxxxxxx
from sympy import Matrix
A = Matrix()
B = Matrix()
X = A**(-1)*B
X
Using the solution above, state the answer to this exercise.
xxxxxxxxxx
Now, we leave you with a few more exercises. Recall that if the associated polynomial for your recursion has a repeated root then your basis will include the sequences
2.
xxxxxxxxxx
3.
xxxxxxxxxx
You have attempted 1 of 4 activities on this page.