I want to find the sum: $1 - \binom{n}{2} + \binom{n}{4} - \binom{n}{6} + ...$

but i'm not entirely sure where to start. I know that alternating sums of binomial coefficients is zero, but don't know if that will help at the moment.

Any ideas?


You can also attack this by brute force if you first collect some data:

$$\begin{array}{c|l} n&f(n)=\sum_{k\ge 0}(-1)^k\binom{n}{2k}\\ \hline 0&1\\ 1&1\\ 2&1-1=0\\ 3&1-3=-2\\ \hline 4&1-6+1=-4\\ 5&1-10+5=-4\\ 6&1-15+15-1=0\\ 7&1-21+35-7=8\\ \hline 8&1-28+70-28+1=16\\ 9&1-36+126-84+9=16\\ 10&1-45+210-210+45-1=0\\ 11&1-55+330-462+165-11=-32\\ \hline 12&1-66+495-924+495-66+1=-64 \end{array}$$

There’s a pretty obvious pattern with a period of $4$: it appears that

$$f(n)=\begin{cases} (-4)^k,&\text{if }n=4k\\ (-4)^k,&\text{if }n=4k+1\\ 0,&\text{if }n=4k+2\\ -2(-4)^k,&\text{if }n=4k+3\;. \end{cases}$$

The third case is fairly easy to prove outright by showing that the $2k+2$ non-zero terms appear in pairs with equal magnitude and opposite sign. All cases can be proved by induction on $k$. For example,

$$\begin{align*} f\big(4(k+1)+1\big)&=\sum_{\ell\ge 0}(-1)^\ell\binom{4k+5}{2\ell}\\ &=\sum_{\ell\ge 0}(-1)^\ell\left(\binom{4k+3}{2\ell}+2\binom{4k+3}{2\ell-1}+\binom{4k+3}{2\ell-2}\right)\\ &=f(4k+3)+\sum_{\ell\ge 0}(-1)^\ell\binom{4k+3}{2(\ell-1)}+2\sum_{\ell\ge 0}(-1)^\ell\binom{4k+3}{2\ell-1}\\ &=f(4k+3)-\sum_{\ell\ge 0}(-1)^\ell\binom{4k+3}{2\ell}+2\sum_{\ell\ge 0}(-1)^\ell\binom{4k+3}{2\ell-1}\\ &=2\sum_{\ell\ge 0}(-1)^\ell\binom{4k+3}{2\ell-1}\\ &=2\sum_{\ell\ge 0}(-1)^\ell\binom{4k+3}{4k+4-2\ell}\\ &=2\sum_{\ell\ge 0}(-1)^{2k+2-\ell}\binom{4k+3}{2\ell}\\ &=2\sum_{\ell\ge 0}(-1)^{\ell}\binom{4k+3}{2\ell}\\ &=2f(4k+3)\\ &=(-4)^{k+1}\;. \end{align*}$$

  • $\begingroup$ The identity used in the second equality in the given induction step is the "second order Pascal's Identity" which was exactly the subject of this question posted earlier today: math.stackexchange.com/questions/1434366/… $\endgroup$ – Travis Willse Sep 14 '15 at 3:53
  • $\begingroup$ @Travis Yep! I knew that identity. Is Brian's answer equivalent to Whacka's? While his answer is a bit cleaner since it isn't brute forcey, I don't quite understand it. $\endgroup$ – Trlyo Sep 14 '15 at 3:56
  • $\begingroup$ @Trlyo: The result is the same, but the means of getting there is quite different. $\endgroup$ – Brian M. Scott Sep 14 '15 at 3:59
  • $\begingroup$ @Trlyo They're equivalent in that they're both valid proofs of the claim, but I don't see immediately how to translate one into the other 'laterally'. Most of Whacka's answer is about how one can write the alternating sum in the simple terms given. To be a little more explicit about his argument, we can write his expression as $\frac{1}{2} [(\sqrt{2} e^{\pi i / 4})^n + (\sqrt{2} e^{-\pi i / 4})^n]$. Expanding and factoring out the common factor $2^{n / 2}$ reveals the usual formula for the cosine in terms of complex exponentials, which leads quickly to the answer. $\endgroup$ – Travis Willse Sep 14 '15 at 4:08
  • $\begingroup$ @Triyo Whacka's proof is certainly cleaner and shorter, but it's also less obvious and less accessible to someone who is, e.g., encountering the problem as a challenge in a first course that treats induction. Both proofs are quite nice in their own ways, I think. $\endgroup$ – Travis Willse Sep 14 '15 at 4:12

This is $(1+i)^n+(1-i)^n$ divided by $2$. Simplify it by converting the complex numbers to polar form and then split into cases depending on $n$ mod $4$.

Here's an explanation of how I got this (beyond "I've seen this type of thing before and know how to deal with it now"). One may write the sum as $\sum_{k\ge0}\binom{n}{k} f(k)$ where $f(k)$ is $0$ if $k$ is of the form $4r+1$ or $4r+3$, is $-1$ if $k$ is of the form $4r+2$ and is $+1$ if $k$ is of the form $4r$. This function is periodic.

According to discrete Fourier analysis, every function $f:\Bbb Z/m\Bbb Z\to\Bbb C$ is expressible as

$$f(k)=\sum_\zeta\color{Blue}{a_\zeta} \color{Green}{\zeta^k} $$

where $\zeta$ in the sum ranges over all $m$th roots of unity, for some constant coefficients $a_\zeta$ (these are the "Fourier amplitudes," one for every "harmonic" $\zeta^k$). The $\zeta$ in $a_\zeta$ is an index.

Then, after "twisting" any series $\sum_{k\ge0}c_k$ termwise with this periodic function $f$, we get

$$\sum_{k\ge0} c_k f(k)=\sum_{k\ge0}c_k \sum_\zeta a_\zeta \zeta^k=\sum_\zeta a_\zeta\left(\sum_{k\ge0}c_k\zeta^k\right).$$

In particular, here we have $c_k=\binom{n}{k}$, and our $f(k)$ may be written as

$$\begin{array}{ll} f(k) & =\color{Blue}{0}\cdot\color{Green}{1^k}+\color{Blue}{\frac{1}{2}}\cdot\color{Green}{i^k}+\color{Blue}{0}\cdot\color{Green}{(-1)^k}+\color{Blue}{\frac{1}{2}}\cdot\color{Green}{(-i)^k} \\ & \displaystyle = \frac{i^k+(-i)^k}{2}.\end{array}$$

The $4$th roots of unity are $1,i,-1,-i$. One can solve for the constant coefficients (in blue) by letting the coefficients be indeterminates, writing down the equation for $f(k)$ and setting $k=0,1,2,3$. This yields a linear system of four equations in four unknowns, which one can solve with linear algebra.

Therefore, the sum is

$$\begin{array}{ll} \displaystyle \sum_{k\ge0}\binom{n}{k}f(k) & \displaystyle =\sum_{k\ge0}\binom{n}{k}\frac{i^k+(-i)^k}{2} \\ & \displaystyle =\frac{1}{2}\sum_{k\ge0}\binom{n}{k}i^k+\frac{1}{2}\sum_{k\ge0}\binom{n}{k}(-i)^k \\ & = \frac{1}{2}(1+i)^n+\frac{1}{2}(1-i)^n \end{array}$$

by the binomial theorem.

  • $\begingroup$ How did you know it was $(1+i)^n + (1-i)^n$? $\endgroup$ – Trlyo Sep 14 '15 at 2:41
  • $\begingroup$ @Triyo Short answer: because I've seen these types of periodic subsums before, and have learned that the way to solve them is with this "polarization" technique. I'll update with a slightly less short explanation. $\endgroup$ – whacka Sep 14 '15 at 2:44
  • $\begingroup$ I look forward to reading the updated post! $\endgroup$ – Trlyo Sep 14 '15 at 2:50
  • $\begingroup$ @Triyo Post updated. $\endgroup$ – whacka Sep 14 '15 at 3:11

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