3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\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
5
$\begingroup$

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.

$\endgroup$
  • $\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.