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$.