# Find the sum $\sum_{j=0}^{n}\binom{4n}{4j}$

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 .

HINT:

Set $x^4=1$ i.e., $x=\pm1,\pm i$ in the given identity and add

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}$$

• Does $1$ satisfy $1+x+x^2+x^3=0?$ – lab bhattacharjee Jan 11 '15 at 16:12
• @labbhattacharjee: do you mean $x=1$? – Marc van Leeuwen Jan 11 '15 at 16:30
• @MarcvanLeeuwen, Yes, definitely. – lab bhattacharjee Jan 11 '15 at 16:31
• @labbhattacharjee edited – RE60K Jan 11 '15 at 16:32