TAOCP 1.2.9 Exercise 14
Let G(z)=\sum_{n\ge 0} a_n z^n.
Section 1.2.9: Generating Functions
Exercise 14. [HM21] Prove Eq. (13).
Verified: yes
Solve time: 52s
Solution
Let
$$ G(z)=\sum_{n\ge 0} a_n z^n. $$
Consider the right-hand side of Eq. (13):
$$ \frac{1}{m}\sum_{0\le k<m}\omega^{-kr}G(\omega^k z). $$
Substituting the definition of $G$ gives
$$ \frac{1}{m}\sum_{0\le k<m}\omega^{-kr}\sum_{n\ge 0} a_n(\omega^k z)^n. $$
Reordering the summations yields
$$ \sum_{n\ge 0} a_n z^n \cdot \frac{1}{m}\sum_{0\le k<m}\omega^{kn}\omega^{-kr} = \sum_{n\ge 0} a_n z^n \cdot \frac{1}{m}\sum_{0\le k<m}\omega^{k(n-r)}. $$
Define
$$ S_{n,r}=\frac{1}{m}\sum_{0\le k<m}\omega^{k(n-r)}. $$
Since $\omega^m=1$, the factor $\omega^{n-r}$ is an $m$th root of unity. Two cases occur.
If $n-r\equiv 0 \pmod m$, then $\omega^{n-r}=1$, hence every term in the sum equals $1$, so
$$ S_{n,r}=\frac{1}{m}\cdot m=1. $$
If $n-r\not\equiv 0 \pmod m$, then $\omega^{n-r}\ne 1$ and
$$ \sum_{k=0}^{m-1}\omega^{k(n-r)} $$
is a finite geometric sum with ratio $\omega^{n-r}$. Its value is
$$ \frac{1-(\omega^{n-r})^m}{1-\omega^{n-r}}. $$
Since $(\omega^{n-r})^m=\omega^{m(n-r)}=1$, the numerator is $0$, while the denominator is nonzero, hence the sum is $0$, so
$$ S_{n,r}=0. $$
Therefore,
$$ S_{n,r}= \begin{cases} 1, & n\equiv r \pmod m,\ 0, & n\not\equiv r \pmod m. \end{cases} $$
Substitution into the previous expression yields
$$ \sum_{\substack{n\ge 0\ n\equiv r\ (\mathrm{mod}\ m)}} a_n z^n, $$
which matches the left-hand side of Eq. (13).
This completes the proof. ∎