# Generating Function for mth Terms of Sequence/Proof

## Theorem

Let $G \left({z}\right)$ be the generating function for the sequence $\left\langle{a_n}\right\rangle$.

Let $m \in \Z_{>0}$ be a (strictly) positive integer.

Let $\omega = e^{2 i \pi / m} = \cos \dfrac {2 \pi} m + i \sin \dfrac {2 \pi} m$.

Then for $r \in \Z$ such that $0 \le r < m$:

$\displaystyle \sum_{n \bmod m \mathop = r} a_n z^n = \dfrac 1 m \sum_{0 \mathop \le k \mathop < m} \omega^{-k r} G \left({\omega^k z}\right)$

## Proof

 $\ds \omega^{-k r} G \left({\omega^k z}\right)$ $=$ $\ds \sum_{j \mathop \ge 0} a_j \omega^{k \left({j - r}\right)} z^j$ Definition of Generating Function $\ds \leadsto \ \$ $\ds \dfrac 1 m \, \sum_{0 \mathop \le k \mathop < m} \omega^{-k r} G \left({\omega^k z}\right)$ $=$ $\ds \dfrac 1 m \, \sum_{0 \mathop \le k \mathop < m} \,\, \sum_{j \mathop \ge 0} a_j \omega^{k \left({j - r}\right)} z^j$ $\ds$ $=$ $\ds \dfrac 1 m \sum_{j \mathop \ge 0} a_j z^j \,\, \sum_{0 \mathop \le k \mathop < m} \omega^{k \left({j - r}\right)}$

By definition of $\omega$:

$\omega = \exp \dfrac {2 \pi i} m \implies \omega^m = 1$

and so:

 $\ds \sum_{0 \mathop \le k \mathop < m} \omega^{k \left({j - r}\right)}$ $=$ $\ds \begin{cases} \dfrac {1 - \omega^{m \left({j - r}\right)} } {1 - \omega^{j - r} } & : j - r \not \equiv 0 \pmod m \\ m & : j \equiv r \pmod m \end{cases}$ Sum of Geometric Progression $\ds \leadsto \ \$ $\ds \dfrac 1 m \sum_{0 \mathop \le k \mathop < m} \omega^{-k r} G \left({\omega^k z}\right)$ $=$ $\ds \dfrac 1 m \sum_{j \mathop \ge 0} m a_j \left[{j \equiv r \pmod m}\right] z^j$ where $\left[{\cdots}\right]$ is Iverson's convention $\ds$ $=$ $\ds \sum_{n \bmod m \mathop = r} a_n z^n$

$\blacksquare$