In the introduction to the time series course (MAT8181) this morning, we did spend some time on the expression of (deterministic) sequences defined using a linear recurence (we will need that later on, so I wanted to make sure that those results were familiar to everyone).
The most simple case is the first order recurence,
where
(for convenience). Observe that we can remove the constant, using a simple translation
if
. So, starting from this point, we will always remove the constant in the recurent equation. Thus,
. From this equation, observe that
, which is the general expression of
.
Consider now a second order recurence,
. In order to find the general expression of
, define
. Then
This time, we have a vectorial linear recurent equation. But what we’ve done previously still holds. For instance,
What could we say about
? If
can be diagonalized, then
and
. Thus,
so what we’ll get here is something like
for some constant
and
. Recall that
and
are the eigenvalues of matrix
, and they are also the roots of the characteristic polynomial
. Since
and
are real-valued, there are two roots for the polynomial, possibly identical, possibly complex (but then conjugate). An interesting case is obtained when the roots are
. In that case
To visualize this general term, consider the following code. A first strategy is to define the sequence, given the two parameters, and two starting values. E.g.
> a=.5
> b=-.9
> u1=1; u0=1
Then, we iterate to generate the sequence,
> v=c(u1,u0)
> while(length(v)<100) v=c(a*v[1]+b*v[2],v)
> plot(0:99,rev(v))
It is also possible to use the generic expression we’ve just seen. Here, the roots of the characteristic polynomial are
> r=polyroot(c(-b, -a, 1))
> r
[1] 0.25+0.9151503i 0.25-0.9151503i
> plot(r,xlim=c(-1.1,1.1),ylim=c(-1.1,1.1),pch=19,col="red")
> u=seq(-1,1,by=.01)
> lines(u,sqrt(1-u^2),lty=2)
> lines(u,-sqrt(1-u^2),lty=2)
Since,
, then
it is possible to derive numerical expressions for the two parameters. If
, then
while
. Thus,
> A=sum(solve(matrix(c(1,r[1],1,r[2]),2,2),c(u0,u1)))
> B=diff(solve(matrix(c(1,r[1],1,r[2]),2,2),c(u0,u1)))* complex(real=0,imaginary=1)
We can plot the sequence of points
> plot(0:99,rev(v))
and then we can also plot the sine wave, too
> t=seq(0,100,by=.1)
> bv=function(t) Mod(r)[1]^t
> fv=function(t) Mod(r)[1]^t*(A*cos(t*Arg(r)[1])+B*sin(t*Arg(r)[1]))
> lines(t,Vectorize(bv)(t-1),col="red",lty=2)
> lines(t,-Vectorize(bv)(t-1),col="red",lty=2)
> lines(t,Vectorize(fv)(t-1),col="blue")

We will see a lot of graph like this in the course, when looking at autocorrelation functions.
More generally, we can write
The matrix is a so called companion matrix. And similar results could be obtained for the expression of the general term of the sequence. If all that is not familar, I strongly recommand to read carefully a textbook on sequences and linear recurence.