= Ordinary generating function of a recurrence
For a <sequence> $(u_n)$, its <ordinary generating function> is the <formal power series>
$$
G(x)=\sum_{n\geq0}u_nx^n.
$$
A constant-coefficient <linear recurrence relation> turns into an algebraic equation for $G$ after multiplication by powers of $x$ and summation; the initial values supply the correction <polynomial>. For example, if $u_0=a$, $u_1=b$ and $u_{n+2}=u_{n+1}+u_n$, then
$$
(1-x-x^2)G(x)=a+(b-a)x.
$$
Hence $G$ is a <rational function>, interpreted as a <formal power series> at zero. No analytic convergence is needed. Variable coefficients can instead lead to operations such as <differentiation>, so the constant-coefficient hypothesis is part of this rational-function conclusion.
Back to article page