Recurrence relation

Definition

Let $X$ be a set and let $k$ be a positive integer. A recurrence relation of order $k$ on $X$ is an equation $$u_{n+k} = f(n, u_n, u_{n+1}, \dots, u_{n+k-1}) \qquad (n \ge 0)$$ for a sequence $(u_n)_{n \ge 0}$ in $X$, where $f : \mathbb{N} \times X^k \to X$ is a given function.

A solution is a sequence that satisfies the equation for all $n \ge 0$.

Remarks

For each choice of initial values $u_0, \dots, u_{k-1}$ there is exactly one solution. This follows by induction on $n$. Examples: the factorial satisfies $u_{n+1} = (n + 1) u_n$ of order $1$. The Fibonacci sequence satisfies $u_{n+2} = u_{n+1} + u_n$ of order $2$. An important special case is a linear recurrence with constant coefficients.

Explanations

L1 human

A recurrence relation gives each term of a sequence from the terms just before it. Once you know the first few terms, the rule determines all the others.