Linear recursions and geometric series

As I mentioned in a previous post, one way to look at a linear recursion is as a matrix. When you do this, it's natural to think about the eigenvalues and eigenvectors of that matrix, and the eigenvectors turn out to be the initial conditions for the recursion that get it to greate a geometric series. We can use this fact to create an nth order recursion that creates n different geometric series of our choice, with the particular series being created determined by the initial conditions of the recursion. So if we pick any two numbers, it's possible to find a single second-order linear recursion that we can make create a geometric series with our chosen numbers as the ration of consecutive terms. Which ratio we get is determined by the initial conditions for the recursion.

Suppose that we write the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

as

xn-k+1 ... ... xn

=

0 1 ... 0 1 a0 a1 ... ak-1

xn-k ... ... xn-1

If λ is a solution to

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then

1 λ ... λk-1

is an eigenvector that corresponds to the eigenvalue λ, and this eigenvector is also the initial state that turns the recursion into a geometric series: if we have

x₀ = 1, x₁ = λ, x₂ = λ², …, x_k-1 = λ^k-1

then we’ll always have x_n = λⁿ.

This means that for an nth order recursion, we can pick any n values λ_i (which are exactly these eigenvalues), and find initial conditions for the recursion such that x_n = λ_iⁿ. The eigenvectors are the initial conditions that do this, and they get the recursion to create a geometric series with the ratio between successive terms being the eigenvalue which corresponds to the eigenvector. It's also easy to write down the recursion that does this for us. In particular, if the eigenvalues are the roots of

x^k – a_k-1 x ^k-1 - … - a₁ x – a₀ = 0

then the recursion

x_n = a_k-1 x_n-1 + … + a₁ x_n-k+1 + a₀ x_n-k

does this for us.

An example

Suppose that we want to find a second-order recursion that will create either the series

x_n = (-2)ⁿ

or

x_n = 3ⁿ

This corresponds to having

λ₁ = -2

and

λ₂ = 3

for the zeroes of

(x - λ₁) (x - λ₂) = (x + 2) (x - 3)

= x² - x - 6

so that the recursion

x_n+2 = x_n+1 + 6 x_n

will do this for us.

The initial conditions

x₀ = 1

and

x₁ = -2

give

x_n = (-2)ⁿ

and the initial conditions

x₀ = 1

and

x₁ = 3

give

x_n = 3ⁿ