# Sequences defined using a Linear Recurrence

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, $u_n=a+b u_{n-1}$ where $b\neq 1$ (for convenience). Observe that we can remove the constant, using a simple translation $\underbrace{[u_n-m]}_{v_n} = b \underbrace{[u_{n-1}-m]}_{v_{n-1}}$ if $m=a/(1-b)$. So, starting from this point, we will always remove the constant in the recurent equation. Thus, ${v_n} = b{v_{n-1}}$. From this equation, observe that ${v_n} = b^n{v_{0}}$, which is the general expression of ${v_n}$.

• Second order recurence

Consider now a second order recurence, ${v_n} = a{v_{n-1}}+b{v_{n-2}}$. In order to find the general expression of ${v_n}$, define $\boldsymbol{V}_n =(v_{n}},{v_{n-1}})^{\sffamily T}$. Then $\underbrace{\begin{bmatrix}v_n\\v_{n-1} \end{bmatrix} }_{\boldsymbol{V}_n }= \underbrace{\begin{bmatrix}a& b \\ 1 & 0\end{bmatrix}}_B\underbrace{\begin{bmatrix}v_{n-1} \\v_{n-2} \end{bmatrix} }_{\boldsymbol{V}_{n-1} }$ This time, we have a vectorial linear recurent equation. But what we’ve done previously still holds. For instance, ${\boldsymbol{V}_n }=B{\boldsymbol{V}_{n-1} }=\cdots=B^n\boldsymbol{V}_{0}$ What could we say about $B^n$ ? If $B$ can be diagonalized, then $B=P\Delta P^{-1}$ and $B^n=P\Delta^n P^{-1}$. Thus, $\underbrace{\begin{bmatrix}v_n\\v_{n-1} \end{bmatrix} }_{\boldsymbol{V}_n }= B^n \underbrace{\begin{bmatrix}v_{0} \\v_{-1} \end{bmatrix} }_{\boldsymbol{V}_{0} }= P\underbrace{\begin{bmatrix}\lambda_1^n& 0 \\ 0 & \lambda_2^n\end{bmatrix}}_{\Delta^n} P^{-1}\underbrace{\begin{bmatrix}v_{0} \\v_{-1} \end{bmatrix} }_{\boldsymbol{V}_{0} }$ so what we’ll get here is something like$v_n = \alpha \lambda_1^n +\beta\lambda_2^n$ for some constant $\alpha$ and $\beta$. Recall that $\lambda_1$ and $\lambda_2$ are the eigenvalues of matrix $B$, and they are also the roots of the characteristic polynomial $P(x)=x^2 - ax - b$. Since $a$ and $b$ 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 $re^{\pm i\theta}$. In that case $v_n =r^n(\alpha\cos(n\theta) + \beta\sin(n\theta))$ 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, $v_n = \alpha \lambda_1^n +\beta\lambda_2^n$, then $\begin{cases} \alpha + \beta = v_0 \\ \alpha r_1 + \beta r_2 = v_1 \end{cases}$ it is possible to derive numerical expressions for the two parameters. If $v_n =r^n(A\cos(n\theta) + B\sin(n\theta))$, then $A=\lambda+\mu$ while $B=i(\lambda-\mu)$. 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.

• Higher order recurence

More generally, we can write $\underbrace{\begin{bmatrix}v_n\\v_{n-1}\\v_{n-2}\\ \vdots \\ v_{n-p+1} \end{bmatrix} }_{\boldsymbol{V}_n }= \underbrace{\begin{bmatrix}b_{1} & b_{2} &b_3& \cdots & b_{p} \\ 1 & 0 & 0& \cdots &0\\ 0 & 1 & 0& \cdots &0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0& \cdots & 0\end{bmatrix}}_B\underbrace{\begin{bmatrix}v_{n-1} \\v_{n-2}\\v_{n-3} \\ \vdots \\ v_{n-p} \end{bmatrix} }_{\boldsymbol{V}_{n-1} }$ 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.

## One thought on “Sequences defined using a Linear Recurrence”

1. hui shan says:

Bonjour, Monsieur:

Ces 3 dernière lignes de code en R ne marchent pas. R dit : Error in formals(FUN) : object ‘bv’ not found et Error in formals(FUN) : object ‘fv’ not found.

Je ne sais pas comment définir ces 2 objets.
Pouvez-vous me donner des indices pour ca?

Merci