Given a generating function $f(x)=\sum_{n\geq0}a_nx^n$, I've been trying to obtain the generating function of the terms $a_n$ such that $n\equiv k\mod m$. For $m=2$ this is easy enough:
$\begin{cases}f(x)=\sum_{n\geq0}a_{2n}x^{2n}+\sum_{n\geq0}a_{2n+1}x^{2n+1}\\ f(-x)=\sum_{n\geq0}a_{2n}x^{2n}-\sum_{n\geq0}a_{2n+1}x^{2n+1}\end{cases}\Rightarrow \sum_{n\geq0}a_{2n}x^{2n}=\dfrac{f(x)+f(-x)}{2}\text{ and}\\\sum_{n\geq0}a_{2n+1}x^{2n+1}=\dfrac{f(x)-f(-x)}{2}$
How would it be generalized? I suspect you'd have to use roots of unity, but I am stumped as to how.
Any help will be appreciated. Thanks in advance.
Let $\omega = \exp(2\pi i/d)$ a first $d$-th root of unity. Note that for $j < d$ $$ f(\omega^j x) =\sum_{n\ge 0} a_n \omega^{jn} x^n = \sum_{k=0}^{d-1} \sum_{n\ge 0} a_{dn + k} \omega^{jdn + jk} x^{dn+k} = \sum_{k=0}^{d-1} \omega^{jk} \sum_{n\ge 0} a_{dn + k} x^{dn+k} $$ Fix $\ell < d$, then $$ \sum_{j=0}^{d-1} \omega^{-j\ell} f(\omega^{j}x) = \sum_{k=0}^{d-1} \sum_{j=0}^{k-1}\omega^{j(k-\ell)} \sum_{n\ge 0} a_{dn + k} x^{dn+k} $$ Now $\sum_{j=0}^{k-1}\omega^{j(k-\ell)} = d\delta_{k,\ell}$, hence $$ \frac 1d \sum_{j=0}^{d-1} \omega^{-j\ell} f(\omega^{j}x) = \sum_{n\ge 0} a_{dn + \ell} x^{dn+\ell}$$