Is there a formula for sum of all nCr for a given n, such that r varies from 0 to n in steps of 4.

Question

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.

Answer 1

Yes there is. In fact, you can generalise by using steps of size $s$ so that the sum is

$$\sum_{k=0}^{\lfloor n/s\rfloor}\binom{n}{sk}$$

Simply consider the $s$-roots of unity $\{e^{2(0)i\pi/s},e^{2i\pi/s},e^{4i\pi/s},\ldots,e^{2(s-1)i\pi/s}\}$ then input them into the binomial formula

$$(1+z)^n=\sum_{k=0}^{n}\binom{n}{k}z^k$$

giving

$$(1+e^{2i(0)\pi/s})^n=\sum_{k=0}^{n}\binom{n}{k}e^{2k(0)i\pi/s}$$ $$(1+e^{2i\pi/s})^n=\sum_{k=0}^{n}\binom{n}{k}e^{2ki\pi/s}$$ $$(1+e^{4i\pi/s})^n=\sum_{k=0}^{n}\binom{n}{k}e^{4ki\pi/s}$$ $$\vdots$$ $$(1+e^{2(s-1)i\pi/s})^n=\sum_{k=0}^{n}\binom{n}{k}e^{2k(s-1)i\pi/s}\, .$$

Add these up

$$\sum_{r=0}^{s-1}(1+e^{2ri\pi/s})^n=\sum_{k=0}^{n}\binom{n}{k}\sum_{r=0}^{s-1}e^{2kri\pi/s}\tag{1}$$

Notice the order of summation swap on the right.

Now, the inner sum

$$\sum_{r=0}^{s-1}e^{2kri\pi/s}$$

is a finite geometric series with ratio $e^{2ki\pi/s}$ and first term $1$.

• When $s$ divides $k$ this ratio is $1$ and the sum is simply $s$.
• when $s$ doesn't divide $k$ the sum is

$$\frac{1-e^{2ki\pi}}{1-e^{2ki\pi/s}}=\frac{0}{1-e^{2ki\pi/s}}=0\, .$$

We have, for $(1)$:

$$\sum_{r=0}^{s-1}(1+e^{2ri\pi/s})^n=s\sum_{k=0}^{\lfloor n/s\rfloor}\binom{n}{sk}\, ,$$

or

$$\sum_{k=0}^{\lfloor n/s\rfloor}\binom{n}{sk}=\frac{1}{s}\sum_{r=0}^{s-1}(1+e^{2ri\pi/s})^n$$

In this case $s=4$:

$$\sum_{k=0}^{\lfloor n/4\rfloor}\binom{n}{4k}=\frac{1}{4}\left(2^n+(1+i)^n+(1-i)^n\right)\tag*{}$$

this may be simplified but I'll leave that as an exercise.

This method is called the "roots of unity filter" or the "discrete fourier transform method".

Answer 2

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.