Two persons $A$ and $B$ flip two fair coins $n$ and $n+1$ times, respectively.
Let $X\sim\text{Bin}(n,1/2)$, $Y\sim\text{Bin}(n+1,1/2)$ be the number of Heads for $A$ and $B$, respectively. How do I find $P(X<Y)$ ?
Here is my attempt for the above question.
Encode the ‘Heads’ with $1$ and the ‘Tails’ with $0$.
Let $\Omega_1$ and $\Omega_2$ be the sample spaces for $A$ and $B$, respectively. Thus, $\Omega_1=\{(a_i)_{1\le i\le n}:a_i\in\{0,1\}\}$ and $\Omega_2=\{(b_j)_{1\le j\le n+1}:b_j\in\{0,1\}\}$.
Since $X$ and $Y$ are defined on different spaces, to compute $P(X<Y)$ define the product space $\Omega=\Omega_1\times\Omega_2=\{(\omega_1,\omega_2):\omega_1\in\Omega_1,\omega_2\in\Omega_2\}$.
We can define $X$ and $Y$ equivalently as follows. For any $\omega\in\Omega$, we can write $\omega=(\omega_1,\omega_2)$. Define $X(\omega)=X(\omega_1)$ and $Y(\omega)=Y(\omega_2)$.
We thus have $P(X<Y)=P(E)$ where $E=\{\omega\in\Omega:X(\omega)<Y(\omega)\}$.
Therefore $P(X<Y)=\displaystyle\sum_{k=1}^{n+1}\displaystyle\sum_{j=0}^{k-1}P(X=j,Y=k)$.
But since $X$ is independent of $Y$, we can write $P(X=j,Y=k)=P(X=j)P(Y=k)$, and hence
$P(X<Y)=\displaystyle\sum_{k=1}^{n+1}\displaystyle\sum_{j=0}^{k-1}P(X=j)P(Y=k)$
$=\displaystyle\sum_{k=1}^{n+1}\displaystyle\sum_{j=0}^{k-1}\dbinom{n}{j}\dfrac{1}{2^j}\dfrac{1}{2^{n-j}}\dbinom{n+1}{k}\dfrac{1}{2^k}\dfrac{1}{2^{n+1-k}}$
$=\left(\displaystyle\sum_{k=1}^{n+1}\dbinom{n+1}{k}\dfrac{1}{2^k}\dfrac{1}{2^{n+1-k}}\right)\left(\displaystyle\sum_{j=0}^{k-1}\dbinom{n}{j}\dfrac{1}{2^j}\dfrac{1}{2^{n-j}}\right)$.
I am supposed to get the answer as $1/2$, but I do not know how the above sum collapses to $1/2$.
The grouping of the two sums with parentheses is misleading because the second summation still has $k$ dependence, so it should be
$$P = \sum_{k = 1}^{n + 1} \dbinom{n+1}{k} \frac{1}{2^{n + 1}} \sum_{j = 0}^k \dbinom{n}{j} \frac{1}{2^n} = \frac{1}{2^{2n + 1}}\sum_{k = 1}^{n + 1} \dbinom{n+1}{k} \sum_{j = 1}^{k} \dbinom{n}{j}$$
Now we do some case work. If $n$ is even, then $n = 2m$ for some $m$ so that
$$\sum_{k = 1}^{n + 1} \dbinom{n+1}{k} \sum_{j = 1}^{k} \dbinom{n}{j} = \left(\sum_{k = 1}^{m} \left[\dbinom{n + 1}{k} \sum_{j = 0}^{k} \dbinom{n}{j} \right] + \left[\dbinom{n + 1}{n + 1 - k} \sum_{j = 0}^{n + 1 - k} \dbinom{n}{j} \right] \right) + \dbinom{n + 1}{n + 1} \sum_{j = 0}^n \dbinom{n}{j}$$
The extra term on the end is equal to $2^n$. Now using the fact that
$$\dbinom{n}{k} = \dbinom{n}{n - k}$$
for any $n$ and $k$ such that $n > k \geq 0$, we get
$$\left[\dbinom{n + 1}{k} \sum_{j = 0}^{k} \dbinom{n}{j} \right] + \left[\dbinom{n + 1}{n + 1 - k} \sum_{j = 0}^{n + 1 - k} \dbinom{n}{j} \right]$$ $$ = \dbinom{n + 1}{k} \left[\sum_{j = 0}^k \dbinom{n}{n - j} + \sum_{j = 0}^{n + 1 - k} \dbinom{n}{j}\right] = \dbinom{n + 1}{k} \sum_{j = 0}^{n + 1} \dbinom{n + 1}{j} = \dbinom{n + 1}{k} 2^n$$
Thus the final sum is
$$P = \frac{1}{2^{2n + 1}} \left[2^n + \sum_{k = 1}^m \dbinom{n + 1}{k} 2^n\right] = \frac{1}{2^{n + 1}} \sum_{k = 0}^m \dbinom{n + 1}{k}$$
Note that I first factored out the $2^n$ and then added an extra term to the summation by making use of the stray $1$ after the factoring. From here, we know by symmetry that
$$\sum_{k = 0}^{m} \dbinom{n + 1}{k} = \sum_{k = 0}^m \dbinom{n + 1}{n + 1 - k} = \sum_{k = m + 1}^{n + 1} \dbinom{n + 1}{k}$$ $$\implies \sum_{k = 0}^{m} \dbinom{n + 1}{k} = \frac{1}{2} \sum_{k = 0}^{n + 1} \dbinom{n + 1}{k} = \frac{1}{2} 2^{n + 1} = 2^n$$
So that finally
$$P = \frac{1}{2^{n + 1}} 2^n = \frac{1}{2}$$
I'll leave the case for when $n$ is odd to you, which is very similar.