Linear recurrence with constant coefficients

Definition

Let $R$ be a commutative ring and let $d$ be a natural number. A linear recurrence of order $d$ with constant coefficients over $R$ is given by coefficients $c_0, c_1, \dots, c_{d-1} \in R$. It is the recurrence relation $$u_{n+d} = c_0 u_n + c_1 u_{n+1} + \dots + c_{d-1} u_{n+d-1} \qquad (n \ge 0)$$ for sequences $(u_n)_{n \ge 0}$ in $R$.

Remarks

This form is homogeneous. A non-homogeneous recurrence adds a term $g(n)$ that does not depend on $u$. The Fibonacci sequence satisfies the recurrence of order $2$ with $c_0 = c_1 = 1$. The sequences that satisfy it are its solutions. Its characteristic polynomial is $X^d - c_{d-1} X^{d-1} - \dots - c_1 X - c_0$.

Explanations

L1 human

In a linear recurrence with constant coefficients, each new term is a fixed weighted sum of the previous $d$ terms. The weights do not change with $n$.