# Prove that $\sum_{k = 0}^{49}(-1)^k\binom{99}{2k} = -2^{49}$

I am preparing a class on the binomial of Newton. One of the exercises at the end of the chapter turns out to be very hard for me:

Prove that $$\sum_{k = 0}^{49}(-1)^k\binom{99}{2k} = -2^{49}$$

I tried to use a clever way of rewriting the binomial coefficients and also tried to use the binomial of Newton to rewrite $$2^{49}$$ as $$\sum_{k = 0}^{49}\binom{49}{k}$$, but with no result.

I also tried to use a proof by induction, but got stuck also.

Any hint would be appreciated.

Hint:

It is the real part of $$(1+i)^{99}=\Bigl(\sqrt 2\,\mathrm{e}^{\tfrac{i\pi}4}\Bigr)^{99}.$$

Hint:

$$(a+b)^{2k+1}+(a-b)^{2k+1}=?$$

Set $$a=1,b=i,b^2=-1$$

• I tried working this out using the binomial theorem and got to $a\sum_{k = 0}^{n}(a^2)^{n-k}(b^2)^k$. Can I take this further? – Student Dec 24 '18 at 17:58

The sum $$\sum_{k=0}^{49}(-1)^k\binom{99}{2k}\tag1$$ counts even subsets of the set $$N=\{1,2,\dots,99\}$$, except that subsets whose sizes are a multiple of four are counted positively, and those whose size is not a multiple of four (but still even) are counted negatively.

Given an even size subset $$S$$ of $$N$$, consider the size of the intersection of $$S$$ with each of the sets $$\{1,2\},\{3,4\},\dots,\{97,98\}$$ We define the following involution $$f$$ on even subsets of $$N$$. Given $$S$$, find the smallest $$k$$ for which $$S$$ contains either both or neither of $$\{2k+1,2k+2\}$$. If $$S$$ contains neither, then $$f(S)$$ is obtained by adding $$2k+1$$ and $$2k+2$$ is $$S$$. If $$S$$ contains both, then $$f(S)$$ is obtained by removing these two elements. Note $$f(S)$$ still has an even number of elements.

Note that almost all of the even subsets of $$N$$ are divided into pairs $$\{S,f(S)\}$$. In each pair, one set has size which is a multiple of four, and the other does not. Therefore, the pair $$\{S,f(S)\}$$ cancels itself out in the summation in $$(1)$$, so can be ignored.

However, $$f$$ is not actually defined for all elements of $$S$$. If $$S$$ contains exactly one of $$\{2k+1,2k+2\}$$ for all $$k=0,1,2,\dots,48$$, then you cannot compute $$f(S)$$. The number of such expectational sets is $$2^{49}$$ (for each $$k$$, choose if $$S$$ has $$2k+1$$ or $$2k+2$$), and these are all counted negatively in $$(1)$$, as their size is $$50$$. As argued before, this is the only thing which contributes to the sum, so we are done.