# Sequences defined using a Linear Recurrence

**Freakonometrics » R-english**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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).

**First order recurence**

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 .

**Second order recurence**

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) > 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.

**Higher order recurence**

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.

**leave a comment**for the author, please follow the link and comment on their blog:

**Freakonometrics » R-english**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.