Is this a combinatorial identity: $ \sum_{k=1}^{n+1}\binom{n+1}{k} \sum_{i=0}^{k-1}\binom{n}{i} = 2^{2n} $?

Question

$$ \sum_{k=1}^{n+1}\left(\binom{n+1}{k} \sum_{i=0}^{k-1}\binom{n}{i}\right) = 2^{2n} $$ This is my first question, please feel free to correct/guide me. While solving a probability problem from a text book l reduced the problem to the above LHS. I couldn't reduce it any further. I tried a few values of n and it holds. I gave a half hearted attempt at induction before I gave up. Does this hold? Is there a combinatorial proof to it(assuming it holds) i.e count something one way and count the same thing other way and then equate them. Is there a name to it? Most importantly how to Google such questions?

To provide further context, the problem is as follows:- Alice and Bob have a total of $2n+1$ fair coins. Bob tosses $n+1$ coins while Alice tosses $n$ coins. Tosses are independent. What is the probability that Bob tossed more heads than Alice? It is from a standard textbook "Introduction to Probability" by Dmitri and N John.

Answer 1

The combinatorial interpretation provided by Lord Shark is really nice and elementary, but there also is a brute-force way to proving such identity. $$ \sum_{k=1}^{n+1}\left[\binom{n+1}{k}\sum_{i=0}^{k-1}\binom{n}{i}\right]=\sum_{a=0}^{n}\left[\binom{n+1}{a+1}\sum_{b=0}^{a}\binom{n}{b}\right]=\sum_{0\leq b\leq a\leq n}\binom{n+1}{a+1}\binom{n}{b}. $$ Let $T_a=\sum_{b=0}^{a}\binom{n}{b}$. From $(1+x)^n = \sum_{b\geq 0}\binom{n}{b}x^b$ we get $$ \frac{(1+x)^n}{1-x} = T_0+T_1 x+ \ldots + T_{n-1} x^{n-1} + 2^n x^n + 2^n x^{n+1} + 2^{n} x^{n+2}+\ldots $$ hence $$ \frac{(1+x)^n-2^n x^{n+1}}{1-x} = \sum_{a=0}^{n} T_a x^a $$ $$ \frac{\left(1+\frac{1}{x}\right)^n-\frac{2^n}{ x^{n+1}}}{x-1} = \sum_{a=0}^{n} T_a x^{-(a+1)} $$ $$ (1+x)^{n+1}\frac{\left(1+\frac{1}{x}\right)^n-\frac{2^n}{ x^{n+1}}}{x-1} = \sum_{a=0}^{n} T_a x^{-(a+1)}(1+x)^{n+1} $$ and $$ \sum_{a=0}^{n}\binom{n+1}{a+1}T_a =\operatorname*{Res}_{x=0}\frac{(x+1)^{n+1}}{x}\cdot\frac{x(x+1)^n-2^n}{x^{n+1}(x-1)}.$$ On the other hand,

$$ \operatorname*{Res}_{x=0}\frac{2^n(x+1)^{n+1}}{x^{n+2}(x-1)}=-\operatorname*{Res}_{x=1}\frac{2^n(x+1)^{n+1}}{x^{n+2}(x-1)}=-2^{2n+1}$$ and $$\begin{eqnarray*} \operatorname*{Res}_{x=0}\frac{(x+1)^{2n+1}}{x^{n+1}(x-1)}&=&-\operatorname*{Res}_{x=0}\frac{(x+1)^{2n+1}}{x^{n+1}}-\operatorname*{Res}_{x=0}\frac{(x+1)^{2n+1}}{x^{n}}-\ldots-\operatorname*{Res}_{x=0}\frac{(x+1)^{2n+1}}{x}\\&=&-\binom{2n+1}{n}-\binom{2n+1}{n-1}-\ldots-\binom{2n+1}{0}=-2^{2n}\end{eqnarray*}$$ so $$\sum_{a=0}^{n}\binom{n+1}{a+1}T_a = 2^{2n+1}-2^{2n} = \color{red}{2^{2n}}$$ as wanted.

Answer 2

Starting from

$$\sum_{k=1}^{n+1} {n+1\choose k} \sum_{q=0}^{k-1} {n\choose q} = \sum_{k=1}^{n+1} {n+1\choose k} \sum_{q=0}^{k-1} {n\choose k-1-q}$$

we have by formal power series the equivalent representation

$$\sum_{k=1}^{n+1} {n+1\choose k} \sum_{q=0}^{k-1} [z^{k-1-q}] (1+z)^n = \sum_{k=1}^{n+1} {n+1\choose k} [z^{k-1}] (1+z)^n \sum_{q=0}^{k-1} z^q .$$

Now we may extend $q$ beyond $k-1$ to infinity because the inner sum term does not contribute to $[z^{k-1}]$ in that case, getting

$$\sum_{k=1}^{n+1} {n+1\choose k} [z^{k-1}] (1+z)^n \sum_{q\ge 0} z^q = \sum_{k=1}^{n+1} {n+1\choose k} [z^{k-1}] \frac{1}{1-z} (1+z)^n \\ = \sum_{k=0}^{n} {n+1\choose n+1-k} [z^{(n+1-k)-1}] \frac{1}{1-z} (1+z)^n \\ = [z^n] \frac{1}{1-z} (1+z)^n \sum_{k=0}^{n} {n+1\choose k} z^k.$$

Once more the term for $k=n+1$ does not contribute to the coefficient extractor $[z^n]$ so we may include it, getting

$$[z^n] \frac{1}{1-z} (1+z)^n \sum_{k=0}^{n+1} {n+1\choose k} z^k = [z^n] \frac{1}{1-z} (1+z)^{2n+1}.$$

This is

$$\sum_{q=0}^n {2n+1\choose q} = \frac{1}{2} 2^{2n+1} = 2^{2n}$$

as claimed.

Answer 3

The probability is the same that Bob tosses more tails than Alice tosses heads. Bob tosses more tails than Alice tosses heads iff between them Alice and Bob toss $n$ or fewer heads. As they toss $2n+1$ coins, this is the same as probability that Alice and Bob toss $n+1$ or more heads. So this probability is $1/2$.