 Linear recurrence relation

A linear recurrence relation expresses each term of a sequence as a linear combination of earlier terms, possibly with an added forcing term. A constant-coefficient homogeneous recurrence of order $r$ has the formTogether with $r$ consecutive initial conditions, it determines the following terms uniquely. For example, the Fibonacci sequence satisfies $F_{n+2}=F_{n+1}+F_n$, $F_0=0$, $F_1=1$.

Substituting $u_n={\lambda }^n$ gives the characteristic polynomial of a linear recurrence. Distinct characteristic roots give independent geometric solutions; repeated roots introduce factors polynomial in $n$. This converts repeated term-by-term computation into polynomial or matrix arithmetic, useful for obtaining a distant term efficiently.