4
$\begingroup$

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}$.

$\endgroup$

3 Answers 3

5
$\begingroup$

For $N=1010$ or others \begin{equation} S_N\equiv \sum_{r=0}^N\binom{N}{r}\sum_{k=2r+1}^{2N+1}\binom{2N+1}{k} = \end{equation} \begin{equation} \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} \end{equation} \begin{equation} = \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} \end{equation} \begin{equation} = \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} \end{equation} \begin{equation} = 2^N 2^{2N+1} - \sum_{r=0}^N\binom{N}{r}\sum_{k=0}^{2r}\binom{2N+1}{k} \end{equation} \begin{equation} = 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} \end{equation} substituing $r'=N-r$ \begin{equation} = 2^{3N+1} - \sum_{r'=N}^{0}\sum_{k=0}^{2N-2r'} \binom{N}{N-r'}\binom{2N+1}{k} \end{equation} and substituting $k'=2N+1-k$ \begin{equation} = 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'} \end{equation} \begin{equation} = 2^{3N+1} - \sum_{r'=N}^{0}\sum_{k'=2N+1}^{1+2r'} \binom{N}{r'}\binom{2N+1}{k'} \end{equation} \begin{equation} = 2^{3N+1} - \sum_{r'=0}^{N}\sum_{k'=2N+1}^{1+2r'} \binom{N}{r'}\binom{2N+1}{k'} = 2^{3N+1}-S. \end{equation} Adding $S$ to both sides gives $2S=2^{3N+1}$, therefore \begin{equation} S=2^{3N}. \end{equation}

$\endgroup$
5
$\begingroup$

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.

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

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*}

$\endgroup$
1
  • 1
    $\begingroup$ +1 Symmetry is great! $\endgroup$
    – drhab
    Aug 11, 2022 at 6:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .