---
tag: 07TZV87Y0T
kind: definition
name: Recurrence relation
msc: [39A05]
defines: 0FYX44GP92
sources:
  - url: https://en.wikipedia.org/wiki/Recurrence_relation
    locator: Definition
---

## 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|0WFCGVMRRC]] satisfies $u_{n+1} = (n + 1) u_n$ of order $1$. The [[Fibonacci sequence|0GA9K57A39]] satisfies $u_{n+2} = u_{n+1} + u_n$ of order $2$.
An important special case is a [[linear recurrence with constant coefficients|081THG13JZ]].

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