Is this a combinatorial identity: $ \sum_{k=1}^{n+1}\binom{n+1}{k} \sum_{i=0}^{k-1}\binom{n}{i} = 2^{2n} $? $$
\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.
 A: 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.
A: 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.
A: 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$.
