Generating Function for mth Terms of Sequence/Proof

From ProofWiki
Jump to navigation Jump to search

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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Generating_Function_for_mth_Terms_of_Sequence/Proof&oldid=437450"