How prove this $\sum_{k=0}^{n} \frac{\binom{2n-k}{n}}{2^{2n-k}}=1 $ Show that
$$\sum_{k=0}^{n}\dfrac{\binom{2n-k}{n}}{2^{2n-k}}=1$$
I think this problem can be solved with nice methods, such as algebraic ones. Or can I use probability methods? Thank you 
 A: It is to be shown that: 

$\sum_{k=0}^{n}\left({2n-k\atop n}\right)2^{-k}=2^{2n}$.

Here $\sum_{k=0}^{n}\left({2n-k\atop n}\right)2^{-k}=\sum_{k=0}^{n}\left({2n-k\atop n-k}\right)2^{-k}=2^{n}\sum_{k=0}^{n}\left({n+k\atop k}\right)2^{-k}$.
(the last equality by 'counting backwards')
So it is enough to prove that: 

$s_{n}:=\sum_{k=0}^{n}\left({n+k\atop k}\right)2^{-k}=2^{n}$.

This can be done by induction on $n$. Clearly $s_{0}=1$, and the summation of $s_{n+1}$ worked out with the relation $\left({n+k+1\atop k+1}\right)=\left({n+k\atop k}\right)+\left({n+k\atop k+1}\right)$
leads to: $s_{n+1}=2^{-1}s_{n+1}+s_{n}$, i.e. 

$s_{n+1}=2s_{n}$. 

Now
we are ready.
A: Suppose we seek to show that
$$\sum_{k=0}^{n} {2n-k\choose n} 2^k = 2^{2n}.$$
Introduce
$${2n-k\choose n}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n-k}}{z^{n+1}} \; dz.$$
This gives for the sum that
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} 
\sum_{k=0}^n \frac{2^k}{(1+z)^k}\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} 
\frac{1-2^{n+1}/(1+z)^{n+1}}{1-2/(1+z)} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} 
\frac{1+z-2^{n+1}/(1+z)^{n}}{1+z-2} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} 
\frac{1+z-2^{n+1}/(1+z)^{n}}{z-1} \; dz.$$
The difference here yields two pieces, the first is
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} 
\frac{2^{n+1}/(1+z)^{n}}{1-z} \; dz
\\ = \frac{2^{n+1}}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} 
\frac{1}{1-z} \; dz.$$
This yields
$$2^{n+1} \sum_{q=0}^n {n\choose q} = 2^{2n+1}.$$
The second piece is
$$- \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} 
\frac{1+z}{1-z} \; dz
\\ = - \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{2n+1}}{z^{n+1}} 
\frac{1}{1-z} \; dz.$$
This is
$$-\sum_{q=0}^{n} {2n+1\choose q}
= -\frac{1}{2} 2^{2n+1} = - 2^{2n}.$$
Combining the two pieces we have
$$2^{2n+1} - 2^{2n} = 2^{2n}$$
as claimed.
A: Things may be more clear if we let $k=n-i$. Then our sum (reversed) is
$$\sum_{i=0}^n \frac{\binom{n+i}{n}}{2^{n+i}}.$$
Imagine tossing a fair coin until we get $n+1$ heads or $n+1$ tails.
The number of tosses is $n+i+1$ if (i) we get exactly $n$ heads in the first $n+i$ tosses, and then a head, or (ii) we get $n$ tails in the first $n+i$ tosses and then a tail.
The probability of (i) is $\frac{\binom{n+i}{n}}{2^{n+i}}\cdot \frac{1}{2}$, and the probability of (ii) is the same. For sure the number of tosses will be one of $n+1$ to $2n+1$. 
A: Take the set of paths from $0$ to $2n$, and break it up 
by the smallest $k$ where the path  hits $|y|=2n-x$. This gives
$$\sum_{k=0}^n {2n-k\choose n-k} 2^k=4^n,$$ which is the same as your formula.

