Prove using combinatorics $\sum\limits_{r=0}^n2^{n-r}*\binom{n+r}{n}=2^{2n}$ Prove using combinatorics $\sum\limits_{r=0}^n2^{n-r}*\binom{n+r}{n}=2^{2n}$
The right side is choosing some persons from $2n$ people  but I can't find a way to explain the left side it has both combination and power of $2$.Any hints?
 A: Consider the set $S$ of all possible bitstrings of length $2n$.  Given a bitstring $s \in S$, define $k$-prefix of $s$ as the shortest prefix bitstring of $s$ with either exactly $k$ $0$s or exactly $k$ $1$s.  Since we are considering the shortest prefix, a $k$-prefix with exactly $k$ 1s ends with bit $1$; a $k$-prefix with exactly $k$ 0s ends with bit $0$.  
Now, consider $(n+1)$-prefixes.  Any $(n+1)$-prefix must be of length at least $n+1$ and at most $2n$.  For a given length $n+1+r$ of $(n+1)$-prefixes ($0 \le r \le n-1$), there are $2 \cdot {{n+r}\choose{n}}$ possible such $(n+1)$-prefixes.  Each $s \in S$ has a unique $(n+1)$-prefix, unless $s$ has exactly $n$ 0s and $n$ 1s.  There are $2^{n-r-1}$ bitstrings in $S$ that share a given $(n+1)$-prefix of length $n+1+r$.  The total number of bitstrings in $S$ is therefore:
$$
 {{2n}\choose{n}} + \sum_{r=0}^{n-1}2{{n+r}\choose{n}}\cdot 2^{n-r-1} = \sum_{r=0}^{n}{{n+r}\choose{n}}\cdot 2^{n-r}
$$
A: Hint:
Consider monotonic lattice paths from $(0,0)$ to the line $y=2n-x$ that pass through the line $\smash{x=n+\frac{1}{2}}$ and that pass through the line $\smash{y=n+\frac{1}{2}}$ and those directly to the point $(n,n)$.
