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

  • 2
    $\begingroup$ Much more efficient than mine, which involved getting $\equiv 0$ and $\equiv 1$ separately. $\endgroup$ – André Nicolas Sep 13 '14 at 4:07
  • 1
    $\begingroup$ This is very fancy, thank you! $\endgroup$ – 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.

  • $\begingroup$ Thank you! it never came to my mind to use imaginary numbers in the Binomial Theorem. $\endgroup$ – sbthesy Sep 13 '14 at 3:56
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Sep 13 '14 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.