Editing Generating function (section)

=== Rational functions ===
{{Main|Linear recursive sequence}}

The ordinary generating function of a sequence can be expressed as a [[rational function]] (the ratio of two finite-degree polynomials) if and only if the sequence is a [[linear recursive sequence]] with constant coefficients; this generalizes the examples above. Conversely, every sequence generated by a fraction of polynomials satisfies a linear recurrence with constant coefficients; these coefficients are identical to the coefficients of the fraction denominator polynomial (so they can be directly read off). This observation shows it is easy to solve for generating functions of sequences defined by a linear [[finite difference equation]] with constant coefficients, and then hence, for explicit closed-form formulas for the coefficients of these generating functions. The prototypical example here is to derive [[Binet's formula]] for the [[Fibonacci numbers]] via generating function techniques.

We also notice that the class of rational generating functions precisely corresponds to the generating functions that enumerate ''quasi-polynomial'' sequences of the form <ref name="GFLECT">{{harvnb|Lando|2003|loc=§2.4}}</ref>
<math display="block">f_n = p_1(n) \rho_1^n + \cdots + p_\ell(n) \rho_\ell^n, </math>

where the reciprocal roots, <math>\rho_i \isin \mathbb{C}</math>, are fixed scalars and where {{math|''p''<sub>''i''</sub>(''n'')}} is a polynomial in {{mvar|n}} for all {{math|1 ≤ ''i'' ≤ ''ℓ''}}.

In general, [[Generating function transformation#Hadamard products and diagonal generating functions|Hadamard products]] of rational functions produce rational generating functions. Similarly, if
<math display="block">F(s, t) := \sum_{m,n \geq 0} f(m, n) w^m z^n</math>

is a bivariate rational generating function, then its corresponding ''diagonal generating function'',
<math display="block">\operatorname{diag}(F) := \sum_{n = 0}^\infty f(n, n) z^n,</math>

is ''algebraic''. For example, if we let<ref>Example from {{cite book |chapter=§6.3 |first1=Richard P. |last1=Stanley |first2=Sergey |last2=Fomin |title=Enumerative Combinatorics: Volume 2 |url=https://books.google.com/books?id=zg5wDqT6T-UC |year=1997 |publisher=Cambridge University Press |isbn=978-0-521-78987-5 |series=Cambridge Studies in Advanced Mathematics |volume=62}}</ref>
<math display="block">F(s, t) := \sum_{i,j \geq 0} \binom{i+j}{i} s^i t^j = \frac{1}{1-s-t}, </math>

then this generating function's diagonal coefficient generating function is given by the well-known OGF formula
<math display="block">\operatorname{diag}(F) = \sum_{n = 0}^\infty \binom{2n}{n} z^n = \frac{1}{\sqrt{1-4z}}. </math>

This result is computed in many ways, including [[Cauchy's integral formula]] or [[contour integration]], taking complex [[residue (complex analysis)|residue]]s, or by direct manipulations of [[formal power series]] in two variables.