Find the sum of the series $$\binom{4n}{0}+\binom{4n}{4}+\binom{4n}{8}+\ldots+\binom{4n}{n}=\sum_{j=0}^{n}\binom{4n}{4j}.$$
My approach is to consider $(1+x)^{4n} = \sum_{j=0}^{4n}\binom{4n}{j}x^j.$
How to proceed further now? Please help on this since I am quite clueless. Thanks a lot .
A standard trick to evaluate such binomial sums is to use the discrete Fourier transform (DFT).
The characteristic function $\chi$ of the integers that are multiples of four can be written as: $$ \chi(n) = \frac{1}{4}\left(1^n + i^n + (-1)^n + (-i)^n\right),$$ hence: $$\sum_{j=0}^{n}\binom{4n}{4j} = \sum_{j=0}^{4n}\binom{4n}{j}\chi(j) = \frac{1}{4}\left(2^{4n}+(1+i)^{4n}+(1-i)^{4n}\right) = \color{red}{\frac{16^n+2(-4)^n}{4}}.$$
$$\newcommand{\c}{\binom} (1+x)^{4n}=\c{4n}0+\c{4n}1x+\c{4n}2x^2+....\c{4n}{4n}x^{4n} $$ Now one property of $j$-th roots of unit is(see here for proof): $$\sum_{\alpha}\alpha^k=\begin{cases}0&k\not\equiv0\pmod j\\1&k\equiv0\pmod j\end{cases}$$ So for fourth roots of unit, viz. $\alpha,\beta,\gamma,\delta\leftrightarrow 1,-1,+i,-i$ $$(1+\alpha)^{4n}+(1+\beta)^{4n}+(1+\gamma)^{4n}+(1+\delta)^{4n}=\sum_{k=0}^{4n}\c{4n}{4k}$$
