Editing Generating function (section)

=== Operations on generating functions ===

==== Multiplication yields convolution ====
{{Main|Cauchy product}}

Multiplication of ordinary generating functions yields a discrete [[convolution]] (the [[Cauchy product]]) of the sequences. For example, the sequence of cumulative sums (compare to the slightly more general [[Euler–Maclaurin formula]])
<math display="block">(a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots)</math>
of a sequence with ordinary generating function {{math|''G''(''a<sub>n</sub>''; ''x'')}} has the generating function
<math display="block">G(a_n; x) \cdot \frac{1}{1-x}</math>
because {{math|{{sfrac|1|1 − ''x''}}}} is the ordinary generating function for the sequence {{nowrap|(1, 1, ...)}}. See also the [[#Convolution (Cauchy products)|section on convolutions]] in the applications section of this article below for further examples of problem solving with convolutions of generating functions and interpretations.

==== Shifting sequence indices ====

For integers {{math|''m'' ≥ 1}}, we have the following two analogous identities for the modified generating functions enumerating the shifted sequence variants of {{math|⟨ ''g''<sub>''n'' − ''m''</sub> ⟩}} and {{math|⟨ ''g''<sub>''n'' + ''m''</sub> ⟩}}, respectively:
<math display="block">\begin{align}
& z^m G(z) = \sum_{n = m}^\infty g_{n-m} z^n \\[4px]
& \frac{G(z) - g_0 - g_1 z - \cdots - g_{m-1} z^{m-1}}{z^m} = \sum_{n = 0}^\infty g_{n+m} z^n.
\end{align}</math>

==== Differentiation and integration of generating functions ====

We have the following respective power series expansions for the first derivative of a generating function and its integral:
<math display="block">\begin{align}
G'(z) & = \sum_{n = 0}^\infty (n+1) g_{n+1} z^n \\[4px]
z \cdot G'(z) & = \sum_{n = 0}^\infty n g_{n} z^n \\[4px]
\int_0^z G(t) \, dt & = \sum_{n = 1}^\infty \frac{g_{n-1}}{n} z^n.
\end{align}</math>

The differentiation–multiplication operation of the second identity can be repeated {{mvar|k}} times to multiply the sequence by {{math|''n''<sup>''k''</sup>}}, but that requires alternating between differentiation and multiplication. If instead doing {{mvar|k}} differentiations in sequence, the effect is to multiply by the {{mvar|k}}th [[falling factorial]]:
<math display="block"> z^k G^{(k)}(z) = \sum_{n = 0}^\infty n^\underline{k} g_n z^n = \sum_{n = 0}^\infty n (n-1) \dotsb (n-k+1) g_n z^n \quad\text{for all } k \in \mathbb{N}. </math>

Using the [[Stirling numbers of the second kind]], that can be turned into another formula for multiplying by <math>n^k</math> as follows (see the main article on [[Generating function transformation#Derivative transformations|generating function transformations]]):
<math display="block"> \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} z^j F^{(j)}(z) = \sum_{n = 0}^\infty n^k f_n z^n \quad\text{for all } k \in \mathbb{N}. </math>

A negative-order reversal of this sequence powers formula corresponding to the operation of repeated integration is defined by the [[Generating function transformation#Derivative transformations|zeta series transformation]] and its generalizations defined as a derivative-based [[generating function transformation|transformation of generating functions]], or alternately termwise by and performing an [[Generating function transformation#Polylogarithm series transformations|integral transformation]] on the sequence generating function. Related operations of performing [[fractional calculus|fractional integration]] on a sequence generating function are discussed [[Generating function transformation#Fractional integrals and derivatives|here]].

==== Enumerating arithmetic progressions of sequences ====
In this section we give formulas for generating functions enumerating the sequence {{math|{''f''<sub>''an'' + ''b''</sub>}<nowiki/>}} given an ordinary generating function {{math|''F''(''z'')}}, where {{math|''a'' ≥ 2}}, {{math|0 ≤ ''b'' < ''a''}}, and {{math|''a''}} and {{math|''b''}} are integers (see the [[generating function transformation|main article on transformations]]). For {{math|''a'' {{=}} 2}}, this is simply the familiar decomposition of a function into [[even and odd functions|even and odd parts]] (i.e., even and odd powers):
<math display="block">\begin{align}
\sum_{n = 0}^\infty f_{2n} z^{2n} &= \frac{F(z) + F(-z)}{2} \\[4px]
\sum_{n = 0}^\infty f_{2n+1} z^{2n+1} &= \frac{F(z) - F(-z)}{2}.
\end{align}</math>

More generally, suppose that {{math|''a'' ≥ 3}} and that {{math|''ω<sub>a</sub>'' {{=}} exp {{sfrac|2''πi''|''a''}}}} denotes the {{mvar|a}}th [[root of unity|primitive root of unity]]. Then, as an application of the [[discrete Fourier transform]], we have the formula<ref name="TAOCPV1">{{harvnb|Knuth|1997|loc=§1.2.9}}</ref>
<math display="block">\sum_{n = 0}^\infty f_{an+b} z^{an+b} = \frac{1}{a} \sum_{m=0}^{a-1} \omega_a^{-mb} F\left(\omega_a^m z\right).</math>

For integers {{math|''m'' ≥ 1}}, another useful formula providing somewhat ''reversed'' floored arithmetic progressions — effectively repeating each coefficient {{mvar|m}} times — are generated by the identity<ref>Solution to {{harvnb|Graham|Knuth|Patashnik|1994|p=569, exercise 7.36}}</ref>
<math display="block">\sum_{n = 0}^\infty f_{\left\lfloor \frac{n}{m} \right\rfloor} z^n = \frac{1-z^m}{1-z} F(z^m) = \left(1 + z + \cdots + z^{m-2} + z^{m-1}\right) F(z^m).</math>