I am trying to compute the number of possible ways, in which $r$ objects can be chosen from a bin containing $n$ distinct objects, such that $r$ is a multiple of $4$. ($r$ can be $0$).
$$\sum_{i=0}^{\lfloor{n/4}\rfloor}\binom{n}{4i}$$
When I am trying to compute this, it's taking a lot of time.
I have tried to find an equivalent expression by iteratively using the following identity, but I am not able to reduce it to a simpler form.
$$ \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}\binom{n}{r}$$
Can someone help me find a simpler expression for the above expression? I am looking for an equivalent expression that's easy to compute.
Best Answer
This is a classic application of discrete Fourier transform and has already been explained on the site but here we go: for every complex number $z$, the binomial identity reads $$\sum_k{n\choose k}z^k=(1+z)^n$$ hence, if one can find a finite collection $Z$ of complex numbers such that $$\sum_{z\in Z}z^k=\left\{\begin{array}{cc}c&\text{if $4$ divides $k$}\\ 0&\text{otherwise}\end{array}\right.\tag{$\ast$}$$ then one gets $$c\sum_k{n\choose4k}=\sum_{z\in Z}(1+z)^n$$ Now, it happens that the set of fourth unit roots $$Z=\{1,i,-1,-i\}$$ solves $(\ast)$ for $c=4$ hence $$4\sum_k{n\choose4k}=2^n+(1+i)^n+0^n+(1-i)^n$$ Finally, $$1\pm i=\sqrt2e^{\pm i\pi/4}$$ hence, for every positive integer $n$, $$\sum_k{n\choose4k}=2^{n-2}+2^{(n-2)/2}\cos(n\pi/4)$$ For $n=0$, the term $0^n$ is $1$ hence one finds again the correct value.