3
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

Hint:

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

$\endgroup$
4
$\begingroup$

Hint:

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Student Dec 24 '18 at 17:58
1
$\begingroup$

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.

$\endgroup$

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.