Editing Generating function (section)

==== 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>