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.

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.
