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.
The ordinary generating function of the sequence isThe floor function takes the same value at and . Grouping those adjacent terms giveswhich simplifies to the displayed expression. The middle identity follows by differentiating the geometric series. The calculation is valid as an identity of formal power series, or analytically for .
Articles by others on the same topic
There are currently no matching articles.