Linear recurrence equations

The general method for solving a recurrence equation of the form

$$s_{k+i}= a_0s_i+a_1s_{i+1}+...+a_{k-1}s_{k+i-1}, i>1,$$

with $s_1,s_2,...,s_k$ given, is rather simple to describe (in principle - in practice it may be quite hard).

First, ``guess'' $s_n=cr^n$ , where $c$ and $r$ are constants. Substituting into the recursion relation and simplifying, we find that $c$ can be arbitrary but $r$ must satisfy

$$a_0+a_1r+...+a_{k-1}r^{k-1}-r^k=0.$$

Let $r_1,...,r_k$ be the roots of this polynomial. We shall assume that these roots are distinct. Under these conditions, let $s_n$ be an arbitrary linear combination of all your ``guesses'',

$$s_n=c_1r_1^n+c_2r_2^n+...c_kr_k^n.$$

Recall that $s_1,...,s_k$ are known, so we have $k$ equations in the $k$ unknown $c_1,...,c_k$ . This completely determines $s_n$ .

Example 1.7.20   Let $s_n$ satisfy $s_n=s_{n-1}+s_{n-2}$ and let $s_1=1,s_2=1$ .

We must solve $r^2-r-1=0$ , whose roots are $r_1={1+\sqrt{5}\over 2}$ and $r_2={1-\sqrt{5}\over 2}$ . Therefore,

$$s_n=c_1({1+\sqrt{5}\over 2})^n +c_2({1-\sqrt{5}\over 2})^n, n>0.$$

Since $s_1=1$ and $s_2=1$ , we have

$$s_n=5^{-1/2}r_1^n-5^{-1/2}r_2^n.$$

The recurrence equation

$$s_{k+n}= a_0s_n+a_1s_{n+1}+...+a_{k-1}s_{k+n-1}, n>1,$$ (1.3)

is equivalent to the matrix equation

$$\left( \begin{array}{ccccc} 0 & 1 & 0 & \dots & 0\\ 0 & 0 &... ...} s_{n+1}\\ s_{n+2}\\ \vdots \\ s_{n+k} \end{array}\right),$$

where $s_{n+k}$ is given as above. Let

$$A= \left( \begin{array}{ccccc} 0 & 1 & 0 & \dots & 0\\ 0 & ... ...{c} s_n\\ s_{n+1}\\ \vdots \\ s_{n+k-1} \end{array}\right).$$

Then the recursive equation is equivalent to $A\vec{s}_n=\vec{s}_{n+1}$ . The sequence $s_1,s_2,...$ is periodic with period $N$ if and only if $A^N\vec{s}_1=\vec{s}_{N+1}$ . The sequence $s_1,s_2,...$ is eventually periodic with period $N$ if and only if $A^N\vec{s}_r=\vec{s}_{N+r}$ , for some $r>0$ .

Example 1.7.21   Define $s_{i+2}=s_{i+1}+s_i ({\rm mod 11})$ , $s_1=1$ , $s_2=1$ . The above method gives

$$s_i=(3\cdot 8^i+8\cdot 4^i ({\rm mod 11}).$$