recurrence Relations

Linear with Constant Coefficients

A linear recurrence with constant coefficients is an equation of the form

$$y_t=a_1{y}_{t-1}+\cdots +a_n{y}_{t-n}+b.$$

If $b$ is 0, then the recurrence is said to be homogeneous, and non-homogeneous otherwise.

The positive integer $n$ is said to be the order of the recurrence.

Solutions of Homogeneous Equations

The roots of the characteristic polynomial equation, along with initial conditions, are used to find solutions.

If there are $d$ distinct roots $r_1,r_2,\dots ,r_d,$ then each solution to the recurrence takes the form

$$a_n=k_1{r}_1^n+k_2{r}_2^n+\cdots +k_d{r}_d^n.$$

If there are repeated roots, terms the second and higher occurrences of the same root are multiplied by increasing powers of $n,$ so if the characteristic polynomial can be factored as $(x-r{)}^3,$ then the solution would have the form

$$a_n=k_1{r}^n+k_{2}n{r}^n+k_3{n}^2{r}^n.$$

Order 1

The recurrence

$$a_n=r{a}_{n-1}$$

has the solution $a_n=k{r}^n$ with $a_0=k.$

Order 2

Consider a recurrence relation of the form

$$a_n=A{a}_{n-1}+B{a}_{n-2}.$$

If we assume it as a solution of the form $a_n=r^n$, we can make the substitution to get

$$r^n=A{r}^{n-1}+B{r}^{n-2},$$

which must be true for all

If we divide everything by $r^{n-2}$ we get

$$r^2=Ar+b,r^2-Ar-B=0.$$

We can solve for $r$ to get the two roots ${\lambda }_1$ and ${\lambda }_2,$ which are the characteristic roots or eigenvalues of the characteristic equation.

If the roots are distinct, our general solution has the form

$$a_n=C{\lambda }_1^n+D{\lambda }_2^n,$$

and if they are identical we have

$$a_n=C{\lambda }^n+Dn{\lambda }^n.$$

We can use initial conditions to find the values of $C$ ad $D.$

Note that this process is almost exactly the same as finding the solution for linear homogenous differential equations.