Expected Value of the Maximum of Two Quantities

We let $n = 1009$ , and $Y = \max \{ 0, X - n\}$ . It is clear that $\mathbb{E}[Y] = \frac{\sum_{k = 0}^n k \binom{2n}{n+k}}{2^{2n}}.$ But, observe that from Cauchy's Residue Theorem, $\binom{2n}{n+k} = \frac{1}{2\pi i} \oint \frac{dz}{(1-z)^{n+k+1} z^{n-k+1}}$ where we integrate along $|z| = \varepsilon$ . Summing this for all $k \geq 0$ , we get $\begin{aligned} \sum_{k = 0}^n k \binom{2n}{n+k} & = \frac{1}{2\pi i} \oint \frac{1}{(1-z)^{n+1}z^{n+1}} \cdot \sum_{k = 0}^\infty \frac{kz^k}{(1-z)^k} dz \\ & = \frac{1}{2\pi i} \oint \frac{1}{(1-z)^{n+1}z^{n+1}} \cdot \frac{z/(1-z)}{(1 - z/(1-z))^2} dz \\ & = \frac{1}{2\pi i} \oint \frac{dz}{(1-z)^n z^n (1-2z)^2} \end{aligned}$ For $\varepsilon$ sufficiently small, the image of $|z| =\varepsilon$ under $z \to z(1-z)$ forms a nice closed path around $0$ . So, let $w = z(1-z)$ , which means that $z = (1 - \sqrt{1 - 4w})/2$ and $(1-2z)^2 = 1-4w$ . So, changing our variable of integration to be $w$ , our sum becomes $\frac{1}{2\pi i} \oint \frac{dw}{w^n (1-4w)^{3/2}} = [w^{n-1}] (1-4w)^{-3/2} = (-4)^{n-1} \binom{-3/2}{n-1} = \frac{n}{2} \binom{2n}{n}.$ So, $\mathbb{E}[Y] = \frac{n}{2^{2n+1}} \binom{2n}{n}$ . We can check that $\binom{2n}{n}$ has $7$ factors of $2$ . So the answer is $2n+1 = \boxed{2019}$ .

Remark We could've have gotten the sum in the following quicker but more boring way $\begin{aligned} \sum_{k = 0}^n k \binom{2n}{n+k} & = \sum_{k = 0}^n (n+k) \binom{2n}{n+k} - n \sum_{k = 0}^n \binom{2n}{k} \\ & = 2n \sum_{k =0 }^n \binom{2n-1}{n+k-1} - n \left ( \frac{1}{2} \binom{2n}{n} + 2^{2n-1} \right )\\ & = 2n \left ( \binom{2n-1}{n} + 2^{2n-2} \right ) - n \left ( \frac{1}{2} \binom{2n}{n} + 2^{2n-1} \right ) \\ & = \frac{n}{2} \binom{2n}{n}. \end{aligned}$