# Can anybody help me solve this combinatorial identity?

While trying to derive some physical equation, I noticed that the following identity was needed:

$\sum^{4a \leq 2k}_{a=0}{2k \choose 4a} + \sum^{4a+1 \leq 2k}_{a=0} {2k \choose 4a+1} = \left\{ \begin{array}{ll} \frac{2^k(2^k +1)}{2} & (k=4l+1, 4l+4)\\ \frac{2^k(2^k -1)}{2} & (k=4l+2, 4l+3) \end{array} \right.$

(where $l,a$ are positive integers)

My strategy was to change the $2^k$'s of RHS into $\sum_{a=0}^{a=k}{k \choose a}$ and use ${n \choose k}={n-1 \choose k} +{n-1 \choose k-1}$, but obtained only incomplete and partial relations. Can anybody solve this identity explicitly, or at least suggest another strategy that might work better?

This is just a rephrasing of André Nicolas' answer, I put it here just because I was typing it when his answer suddenly appeared.

The Discrete Fourier Transform gives: $$1^k+i^k+(-1)^k+(-i)^k = 4\cdot\mathbb{1}_{k\equiv 0\pmod{4}} \tag{1}$$ hence: $$\mathbb{1}_{k\equiv 0,1\pmod{4}} = \frac{1}{4}\left(2+(1-i)\,i^k+(1+i)\,(-i)^k\right)\tag{2}$$ and: $$\begin{eqnarray*}\sum_{\substack{0\leq a\leq 2k\\ a\equiv{0,1}\pmod{4}}}\!\!\!\!\!\binom{2k}{a}&=&\sum_{a=0}^{2k}\binom{2k}{a}\mathbb{1}_{a\equiv 0,1\pmod{4}}\\&=&\frac{1}{2}\left(2^{2k}+(1+i)^{2k-1}+(1-i)^{2k-1}\right)\end{eqnarray*}\tag{3}$$ hence the claim follows by considering that $(1+i)$ is $\sqrt{2}$ times an eigth root of unity, $e^{\frac{\pi i}{4}}$.

• Much more efficient than mine, which involved getting $\equiv 0$ and $\equiv 1$ separately. – André Nicolas Sep 13 '14 at 4:07
• This is very fancy, thank you! – sbthesy Sep 13 '14 at 4:50

A tool: By the Binomial Theorem, we have $$(1+x)^n=1+\binom{n}{1}x+\binom{n}{2}x^2+\binom{n}{3}x^3+\binom{n}{4}x^4+\binom{n}{5}x^5+\cdots. \tag{1}.$$ Putting $x=1$ we get a familiar identity, and putting $x=-1$ we get something almost as familiar.

Using addition and subtraction, we get the sum of the binomial coefficients of the shape $\binom{n}{k}$, where $k$ ranges over the even numbers, and also the sum where $k$ ranges over the odd numbers.

Now comes the interesting part. Put $x=i$. We get $$(1+i)^n=1+\binom{n}{1}i-\binom{n}{2}^2-\binom{n}{3}i+\binom{n}{4}+\binom{n}{5}i+\cdots \tag{2}.$$ We get a similar result by using $x=-i$. It can also be obtained from (2) by conjugation.

We connect Equation (2) with powers of $2$. Note that $1+i=\frac{1}{\sqrt{2}}\left(\cos(\pi/4)+i\sin(\pi/4)\right)$. Taking the $n$-th power, we get $(1+i)^n=2^{n/2}\left(\cos(n\pi/4)+i\sin(n\pi/4)\right)$. Do the same with the substitution $x=1-i$. By taking real and imaginary parts, we get explicit formulas for sums of certain types of binomial coefficients.

By playing with the ideas above, we can get explicit formulas for $\sum \binom{n}{k}$, where (i) $k$ ranges over multiples of $4$; (ii) $k$ ranges over the numbers that have remainder $1$ on division by $4$; $k$ ranges over the numbers with remainder $2$ on division by $4$; (iv) $k$ ranges over the numbers with remainder $3$.

For remainder $0$ or $1$ (your problem) one may not need remainder $0$ and remainder $1$ separately.

• Thank you! it never came to my mind to use imaginary numbers in the Binomial Theorem. – sbthesy Sep 13 '14 at 3:56
• Plugging in $q$-th roots of unity is a standard tool for picking up the sum of the binomial coefficients $\binom{n}{k}$ where $k\equiv a\pmod{q}$. It is pleasant enough for $q=2$, and somewhat messy for $q=3$ and $q=4$. After that, it gets kind of painful. There are other tools, such as generating functions. What I mentioned will be enough, but not much fun. – André Nicolas Sep 13 '14 at 4:01