Linear recursive sequences

A sequence $\{a_n\}$ is said to satisfy the linear recurrence with coefficients $c_k$, $c_{k-1}$, ..., $c_0$ if

$$c_k a_{n+k} + c_{k-1} a_{n+k-1} + \cdots + c_1 a_{n+1} + c_0 a_n = 0$$ (2)

holds for all integers $n$ for which this makes sense. (If the sequence starts with $a_1$, then this means for $n \ge 1$.) The integer $k$ is called the order of the linear recurrence.

A linear recursive sequence is a sequence of numbers $a_1,a_2,a_3,\dots$ satisfying some linear recurrence as above with $c_k \not= 0$ and $c_0 \not=0$. For example, the sequence (1) satisfies

$$a_{n+1} - 2 a_n = 0$$

for all integers $n \ge 1$, so it is a linear recursive sequence satisfying a recurrence of order 1, with $c_1=1$ and $c_0=-2$.

Requiring $c_k \not= 0$ guarantees that the linear recurrence can be used to express $a_{n+k}$ as a linear combination of earlier terms:

$$a_{n+k} = -\frac{c_{k-1}}{c_k} a_{n+k-1} - \cdots - \frac{c_1}{c_k} a_{n+1} - \frac{c_0}{c_k} a_n.$$

The requirement $c_0 \not=0$ lets one express $a_n$ as a linear combination of later terms:

$$a_n = -\frac{c_k}{c_0} a_{n+k} -\frac{c_{k-1}}{c_0} a_{n+k-1} - \cdots - \frac{c_1}{c_0} a_{n+1}.$$

This lets one define $a_0$, $a_{-1}$, and so on, to obtain a doubly infinite sequence

$$\dots,a_{-2},a_{-1},a_0,a_1,a_2,\dots$$

that now satisfies the same linear recurrence for all integers $n$, positive or negative.