# Evaluating $\sum_{r=0}^{1010} \binom{1010}r \sum_{k=2r+1}^{2021}\binom{2021}k$

I need to find the summation $$S=\sum_{r=0}^{1010} \binom{1010}r \sum_{k=2r+1}^{2021}\binom{2021}k$$

I tried various things like replacing $$k$$ by $$2021-k$$ and trying to add the 2 summations to a pattern but was unable to find a solution. For more insights into the question, this was essential to solve a probability question wherein there were 2 players, A and B. A rolls a dice $$2021$$ times, and B rolls it $$1010$$ times. We had to find the probability of A having number of odd numbers more than twice of B. So if B had $$r$$ odd numbers, A could have odd numbers from $$2r+1$$ to $$2021$$, hence the summation. I can get the required probability by dividing this by $$2^{2021+1010}$$.

For $$N=1010$$ or others $$$$S_N\equiv \sum_{r=0}^N\binom{N}{r}\sum_{k=2r+1}^{2N+1}\binom{2N+1}{k} =$$$$ $$$$\sum_{r=0}^N\binom{N}{r}\sum_{k=2r+1}^{2N+1}\binom{2N+1}{k} + \sum_{r=0}^N\binom{N}{r}\sum_{k=0}^{2r}\binom{2N+1}{k} - \sum_{r=0}^N\binom{N}{r}\sum_{k=0}^{2r}\binom{2N+1}{k}$$$$ $$$$= \sum_{r=0}^N\binom{N}{r}\sum_{k=0}^{2N+1}\binom{2N+1}{k} - \sum_{r=0}^N\binom{N}{r}\sum_{k=0}^{2r}\binom{2N+1}{k}$$$$ $$$$= \sum_{r=0}^N\binom{N}{r}2^{2N+1} - \sum_{r=0}^N\binom{N}{r}\sum_{k=0}^{2r}\binom{2N+1}{k}$$$$ $$$$= 2^N 2^{2N+1} - \sum_{r=0}^N\binom{N}{r}\sum_{k=0}^{2r}\binom{2N+1}{k}$$$$ $$$$= 2^{3N+1} - % \sum_{k=0}^{2N}\sum_{r=k}^{N} \sum_{r=0}^{N}\sum_{k=0}^{2r} \binom{N}{r}\binom{2N+1}{k}$$$$ substituing $$r'=N-r$$ $$$$= 2^{3N+1} - \sum_{r'=N}^{0}\sum_{k=0}^{2N-2r'} \binom{N}{N-r'}\binom{2N+1}{k}$$$$ and substituting $$k'=2N+1-k$$ $$$$= 2^{3N+1} - \sum_{r'=N}^{0}\sum_{k'=2N+1}^{2N+1-(2N-2r')} \binom{N}{N-r'}\binom{2N+1}{2N+1-k'}$$$$ $$$$= 2^{3N+1} - \sum_{r'=N}^{0}\sum_{k'=2N+1}^{1+2r'} \binom{N}{r'}\binom{2N+1}{k'}$$$$ $$$$= 2^{3N+1} - \sum_{r'=0}^{N}\sum_{k'=2N+1}^{1+2r'} \binom{N}{r'}\binom{2N+1}{k'} = 2^{3N+1}-S.$$$$ Adding $$S$$ to both sides gives $$2S=2^{3N+1}$$, therefore $$$$S=2^{3N}.$$$$

Finding that summation...., too lazy for that. But solving that puzzle you gave in your description is tempting enough to give it a try.

First a modulation.

Let it be that $$B$$ throws $$n$$ dice and $$A$$ throws $$2n$$ dice.

If $$O_B$$ and $$O_A$$ denote the number of odds thrown by $$B$$ and $$A$$ respectively then it can be shown that: $$P(O_A>2O_B)=P(O_A<2O_B)\tag1$$ I will prove this assertion below but let us first look at the consequences of $$(1)$$.

Suppose that $$A$$ and $$B$$ want to avoid a draw and agree that after the $$3n$$ throws player $$A$$ always throws a die that is decisive in the case that there is indeed a draw. It has no impact if there is no draw but if there is one then $$A$$ wins iff this final throw results in an odd number.

If $$(1)$$ is true then evidently this agreement provides equal chances for $$A$$ and $$B$$ to win.

But this agreement also boils down to:

$$B$$ throws $$n$$ dice and $$A$$ throws $$2n+1$$ dice and $$A$$ wins if he throws a number of odds more than twice as $$B$$.

which is exactly the game you describe in your question.

So if $$(1)$$ is correct then we can conclude that $$A$$ will win the game with probability $$\frac12$$ or equivalently that:$$\sum_{r=0}^n\binom{n}r\sum_{k=2r+1}^{2n+1}\binom{2n+1}k=2^{3n}$$

Now a proof of $$(1)$$ which is surprisingly simple.

Let $$E_B$$ and $$E_A$$ denote the number of evens thrown by $$B$$ and $$A$$ respectively.

Then by symmetry we find:$$P(O_A>2O_B)=P(E_A>2E_B)=P\left(2n-O_A>2(n-O_B)\right)=P(O_A<2O_B)$$and we are ready.

• Instructive approach. (+1) Aug 11, 2022 at 7:20

A variation. We obtain \begin{align*} \color{blue}{S_n}&=\sum_{r=0}^{n}\binom{n}{r}\sum_{k=2r+1}^{2n+1}\binom{2n+1}{k}\\ &\,\,\color{blue}{=\sum_{r=0}^n\binom{n}{r}\sum_{k=2n-2r+1}^{2n+1}\binom{2n+1}{k}}\tag{r\to\ n-r, (1)}\\ \\ \color{blue}{S_n}&=\sum_{r=0}^{n}\binom{n}{r}\sum_{k=2r+1}^{2n+1}\binom{2n+1}{k}\\ &=\sum_{r=0}^n\binom{n}{r}\sum_{k=0}^{2n-2r}\binom{2n+1}{2r+1+k}\tag{index k starts with 0}\\ &=\sum_{r=0}^n\binom{n}{r}\sum_{k=0}^{2n-2r}\binom{2n+1}{2n+1-k}\tag{k\to 2n-2r-k}\\ &\,\,\color{blue}{=\sum_{r=0}^n\binom{n}{r}\sum_{k=0}^{2n-2r}\binom{2n+1}{k}}\tag{2}\\ \end{align*}

Adding (1) and (2) and division by two gives \begin{align*} \color{blue}{S_n}&=\frac{1}{2}\sum_{r=0}^n\binom{n}{r}\sum_{k=0}^{2n+1}\binom{2n+1}{k}\\ &=\frac{1}{2}\cdot 2^{n}\cdot 2^{2n+1}\\ &\,\,\color{blue}{=2^{3n}} \end{align*}

• +1 Symmetry is great! Aug 11, 2022 at 6:19