Ordinary generating function of a recurrence
ID: ordinary-generating-function-of-a-recurrence
For a sequence , its ordinary generating function is the formal power seriesA constant-coefficient linear recurrence relation turns into an algebraic equation for after multiplication by powers of and summation; the initial values supply the correction polynomial. For example, if , and , thenHence 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.
New to topics? Read the docs here!