quality:corruption
Enumerating arithmetic progressions of sequences

In this section we give formulas for generating functions enumerating the sequence { f } given an ordinary generating function F (z), where a ≥ 2, 0 ≤ b < a, and a and b are integers (see the main article on transformations). For a = 2, this is simply the familiar decomposition of a function into even and odd parts (i.e., even and odd powers): ∑ n = 0 ∞ f 2 n z 2 n = F (z) + F (− z) 2 ∑ n = 0 ∞ f 2 n + 1 z 2 n + 1 = F (z) − F (− z) 2. {\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned}}}

More generally, suppose that a ≥ 3 and that ω = exp 2 πi / a denotes the a th primitive root of unity. Then, as an application of the discrete Fourier transform, we have the formula ∑ n = 0 ∞ f a n + b z a n + b = 1 a ∑ m = 0 a − 1 ω a − m b F (ω a m z). {\displaystyle \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).}

For integers m ≥ 1, another useful formula providing somewhat reversed floored arithmetic progressions — effectively repeating each coefficient m times — are generated by the identity ∑ n = 0 ∞ f ⌊ n m ⌋ z n = 1 − z m 1 − z F (z m) = (1 + z + ⋯ + z m − 2 + z m − 1) F (z m). {\displaystyle \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}).}