---
tag: 081THG13JZ
kind: definition
name: Linear recurrence with constant coefficients
msc: [39A06]
defines: 0NDVHBVBXB
uses: [07TZV87Y0T]
sources:
  - url: https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients
    locator: Definitions
---

## 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|07TZV87Y0T]]
$$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|0GA9K57A39]] satisfies the recurrence of order $2$ with $c_0 = c_1 = 1$.
The sequences that satisfy it are its [[solutions|0ZV2YKKZ58]]. Its [[characteristic polynomial|0BWDJGQYST]] 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$.