<s>[INST] Sum of combinations - convergence I am trying to evaluate the sum of combinations for a specific probability problem, but I am kind of stuck.
Let A have toss a coin $n+1$ times and B toss another coin $n$ times. What is the probability that A has more heads than B. (the probability of heads is $P = 1/2$). All experiments are independent. 
Now, let $X$ denote the numbers of heads A has and $Y$ the number of heads B has. So: 
$$ \begin{eqnarray} P(X>Y) &= \sum_{y=0}^{n}P(X>y|Y=y) P(Y=y) \\
&= \sum_{y=0}^{n} P(X>y|Y=y) {n \choose y} \left(\frac{1}{2}\right)^n \\ 
&= \sum_{y=0}^{n} \sum_{x=y+1}^{n+1} {n+1 \choose x} {n \choose y} \left(\frac{1}{2}\right)^{2n+1} \\
&= \left(\frac{1}{2}\right)^{2n+1} \sum_{y=0}^{n} \sum_{x=y+1}^{n+1} {n+1 \choose x} {n \choose y} \end{eqnarray} $$
I know this sum must result $2^{2n}$, because the probability must be $1/2$. Yet I am stuck. Any advices?
Thanks! :) 
 [/INST] 
On the one hand we obtain
\begin{align*}
\color{blue}{\sum_{y=0}^n\sum_{x=y+1}^{n+1}\binom{n+1}{x}\binom{n}{y}}
&=\sum_{y=0}^n\left(2^{n+1}-\sum_{x=0}^y\binom{n+1}{x}\right)\binom{n}{y}\tag{1}\\
&\,\,\color{blue}{=2^{2n+1}-\sum_{y=0}^n\sum_{x=0}^y\binom{n+1}{x}\binom{n}{y}}\tag{2}
\end{align*}
on  the other hand we obtain
\begin{align*}
\color{blue}{\sum_{y=0}^n\sum_{x=y+1}^{n+1}\binom{n+1}{x}\binom{n}{y}}
&=\sum_{y=0}^n\sum_{x=n+1-y}^{n+1}\binom{n+1}{x}\binom{n}{y}\tag{3}\\
&=\sum_{y=0}^n\sum_{x=-y}^0\binom{n+1}{x+n+1}\binom{n}{y}\tag{4}\\
&=\sum_{y=0}^n\sum_{x=0}^y\binom{n+1}{n+1-x}\binom{n}{y}\tag{5}\\
&\,\,\color{blue}{=\sum_{y=0}^n\sum_{x=0}^y\binom{n+1}{x}\binom{n}{y}}\tag{6}\\
\end{align*}
Comparing  (2)  and (6) we observe
\begin{align*}
2^{2n+1}-\sum_{y=0}^n\sum_{x=0}^y\binom{n+1}{x}\binom{n}{y}&=\sum_{y=0}^n\sum_{x=0}^y\binom{n+1}{x}\binom{n}{y}\\
\color{blue}{\sum_{y=0}^n\sum_{x=0}^y\binom{n+1}{x}\binom{n}{y}}&\color{blue}{=2^{2n}}
\end{align*}
and    the claim follows.

Comment:


*

*In (1) and (2) we use $\sum_{j=0}^n\binom{n}{j}=2^n$.

*In (3) we change the order of summation $y\to n-y$ and we use $\binom{p}{q}=\binom{p}{p-q}$.

*In (4) we shift the index $x$ by $n+1$.

*In (5) we substitute $x$ with $-x$.

*In (6) we use again $\binom{p}{q}=\binom{p}{p-q}$.
</s>