Assume $G(z)$ is a generating function for a sequence $a_n$.

$$ G(z) = a_0 + a_1\cdot z + a_2\cdot z^2 + a_3\cdot z^3 + \cdots $$

To extract every odd term or even term of the sequence:

$$ \frac{1}{2}(G(z) + G(-z)) = a_0 + a_2\cdot z^2 + \cdots $$ $$ \frac{1}{2}(G(z) - G(-z)) = a_1\cdot z + a_3\cdot z^3 + \cdots $$

We can generalize this trick to get every $m$‘th term.

$$ \sum_{\text{i mod m = r}}{a_i\cdot z^i} = \frac{1}{m}\sum_{0 \leq k \lt m}{\omega^{-k r}\cdot G(\omega^{k} z)} $$

Using the fact that

$$ \omega = \exp{\frac{2 \pi i}{m}} $$ $$ \sum_{0 \leq k \lt m}{\omega^{k r}} = m \cdot [\text{r mod m = 0}] $$

Assume $a_i = 0$ for all $i \geq m$. Let’s define another generating function $\mathcal{F}_G$:

$$ \mathcal{F}_G(z) = G(\omega^0) + G(\omega^1)\cdot z + G(\omega^2)\cdot z^2 + \cdots $$

Each term of $\mathcal{F}_G$ is defined from $G$:

$$ [z^r]\mathcal{F}_G(z) = G(\omega^r) = \sum_{0 \leq k \lt m}{\omega^{k r} \cdot ([z^k]G(z))} $$

In reverse, using the previous trick, we can evaluate each term of $G$ using $\mathcal{F}_G$:

$$ [z^r]G(z) = \frac{1}{m}\mathcal{F}_G(\omega^{-r}) = \frac{1}{m}\sum_{0 \leq k \lt m}{\omega^{-k r}\cdot ([z^k]\mathcal{F}_G(z))} $$