Can some one help me understand the technique called "Root of unity filter" . I just know how to use it. It's as follow:
For series $f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$ we need to find the sum of coefficient of terms in which the power is a multiple of any number say $k$ for finding the same we have $\omega $ as $\mathrm{k^{th}}$ of unity and write
$$ \dfrac{f(1)+f(\omega)+f(\omega ^2)+ \cdots+ f(\omega^{k-1})}{k}=(a_0 + a_k + a_{2k}+\cdots)$$
please help me understand why and how this works , I tried googling but didn't get any satisfactory answer
Best Answer
Theorem: (Root of Unity Filter)
Define $\omega=e^{2\pi i/n}$ for a positive integer $n$. For any polynomial $F(x)=a_0+a_1x+a_2x^2+\dots$(where we take $a_k=0$ if $k>deg(F)$), the sum $a_0+a_n+a_{2n}+...$ is given by $$a_0+a_n+a_{2n}+\dots=\frac{1}{n}(F(1)+F(\omega)+\dots+F(\omega^{n-1}))$$
Proof: Let $s_k=1+\omega^k+\dots+\omega^{(n-1)k}$
If $n$ divides $k$, then $\omega^k=1$ and so $s_k=1+1+1\dots+1=n$ otherwise $s_k=\frac{1-\omega^{nk}}{1-\omega^k}=0$. So
$F(1)+F(\omega)+\dots+F(\omega^{n-1})=a_0s_0+a_1s_1+a_2s_2+\dots=n(a_0+a_n+a_{2n}+\dots)$
Divide the both sides of the equation by $n$ and the proof is complete.
Source of my knowledge: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf
There are some examples also which may help you. Please have a look at Problem $2 $ on page $3$.