{"word_count": 399, "character_count": 2996}
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 recurenceThe 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 recurenceConsider 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.&#62; a=.5&#62; b=-.9&#62; u1=1; u0=1Then, we iterate to generate the sequence,&#62; v=c(u1,u0)&#62; while(length(v)&#60;100) v=c(a*v[1]+b*v[2],v)&#62; 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&#62; r=polyroot(c(-b, -a, 1))&#62; r[1] 0.25+0.9151503i 0.25-0.9151503i&#62; plot(r,xlim=c(-1.1,1.1),ylim=c(-1.1,1.1),pch=19,col="red")&#62; u=seq(-1,1,by=.01)&#62; lines(u,sqrt(1-u^2),lty=2)&#62; 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,&#62; A=sum(solve(matrix(c(1,r[1],1,r[2]),2,2),c(u0,u1)))&#62; 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&#62; plot(0:99,rev(v))and then we can also plot the sine wave, too&#62; t=seq(0,100,by=.1)&#62; bv=function(t) Mod(r)[1]^t&#62; fv=function(t) Mod(r)[1]^t*(A*cos(t*Arg(r)[1])+B*sin(t*Arg(r)[1]))&#62; lines(t,Vectorize(bv)(t-1),col="red",lty=2)&#62; lines(t,-Vectorize(bv)(t-1),col="red",lty=2)&#62; 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 recurenceMore 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.