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.

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.
