Olympiad Maths Prep

Track / Stage 6 / 172 of 400 #1172 of 2000

Problem 1172

National olympiad, first round
Combinatorics Difficulty 6.3 Find the answer

Find k=049(1)k(992k)\displaystyle \sum_{k=0}^{49}(-1)^k\binom{99}{2k}, where (nj)=n!j!(nj)!\binom{n}{j}=\frac{n!}{j!(n-j)!}.

(A) 250(B) 249(C) 0(D) 249(E) 250 \textbf{(A)}\ -2^{50} \qquad\textbf{(B)}\ -2^{49} \qquad\textbf{(C)}\ 0 \qquad\textbf{(D)}\ 2^{49} \qquad\textbf{(E)}\ 2^{50}

Official solution

To solve the problem, we need to find the sum k=049(1)k(992k)\sum_{k=0}^{49}(-1)^k \binom{99}{2k}. We can use complex numbers and De Moivre's theorem to simplify the computation.

1. Define the function:
Let f(x)=(x+i)99 f(x) = (x + i)^{99} . Expanding this using the binomial theorem, we get:
f(x)=k=099(99k)x99kik f(x) = \sum_{k=0}^{99} \binom{99}{k} x^{99-k} i^k
We are interested in the real part of f(1) f(1) , which is (1+i)99 (1 + i)^{99} .

2. **Express 1+i 1 + i in polar form:**
1+i=2(cosπ4+isinπ4) 1 + i = \sqrt{2} \left( \cos \frac{\pi}{4} + i \sin \frac{\pi}{4} \right)
Using De Moivre's theorem, we can write:
(1+i)99=(2)99(cos99π4+isin99π4) (1 + i)^{99} = \left( \sqrt{2} \right)^{99} \left( \cos \frac{99\pi}{4} + i \sin \frac{99\pi}{4} \right)

3. Simplify the expression:
(2)99=249.5 \left( \sqrt{2} \right)^{99} = 2^{49.5}
Next, we need to find cos99π4\cos \frac{99\pi}{4} and sin99π4\sin \frac{99\pi}{4}. Note that:
99π4=24π+3π4 \frac{99\pi}{4} = 24\pi + \frac{3\pi}{4}
Since cos\cos and sin\sin are periodic with period 2π2\pi, we have:
cos99π4=cos3π4=22 \cos \frac{99\pi}{4} = \cos \frac{3\pi}{4} = -\frac{\sqrt{2}}{2}
sin99π4=sin3π4=22 \sin \frac{99\pi}{4} = \sin \frac{3\pi}{4} = \frac{\sqrt{2}}{2}

4. Compute the real part:
(1+i)99=249.5(22+i22) (1 + i)^{99} = 2^{49.5} \left( -\frac{\sqrt{2}}{2} + i \frac{\sqrt{2}}{2} \right)
The real part of this expression is:
249.522=249.522=249 2^{49.5} \cdot -\frac{\sqrt{2}}{2} = -2^{49.5} \cdot \frac{\sqrt{2}}{2} = -2^{49}

Thus, the sum k=049(1)k(992k)\sum_{k=0}^{49}(-1)^k \binom{99}{2k} is 249-2^{49}.

The final answer is 249\boxed{-2^{49}}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.