> [!NOTE] **Definition** (Recurrence relation) >A *recurrence relation* or *difference equation* is a [[Functional Equation|functional equation]] that expresses each element of a [[Real sequences|sequence]] as a function of the preceding ones. > >More precisely, a $k$-th order recurrence relation has the form $F(n,u_{n},u_{n-1},u_{n-2},\dots,u_{n-k}) = 0$for $n \geq k$, where $F:\mathbb{N} \times X^{k+1} \to X$ is a [[Function]] and $X$ is a set to which the elements of a sequence must belong. > # Properties A recurrence relation is [[Linear Recurrence Relation|linear]] if $F$ is linear in $u_{n},\dots,u_{n-k}$. A recurrence relation is homogenous if $F(t,0,\dots,0)\equiv 0$. A recurrence relation is [[autonomous recurrence relation|non-autonomous]] if its index doesn't explicitly appear in the equation. We may find a closed form formula for a recurrence relation using its [[Ordinary Generating Function]]. # Examples - [[Fibonacci Sequence]]; - [[Bessel Function]]; - [[Master Theorem for Polynomial Work]]. - [[Chebyshev polynomials]]. # Applications - [[Recursive Function]].