<s>[INST] How to show $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$ 
How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $n$?

I tried using the Snake oil technique but I guess I am applying it incorrectly. With the snake oil technique we have $$F(x)= \sum_{n=0}^{\infty}\left\{\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}\right\}x^{n}.$$ I think I have to interchage the summation and do something. But I am not quite comfortable in interchanging the summation. Like after interchaging the summation will $$F(x)=\sum_{k=0}^{n}\sum_{n=0}^{\infty}\binom{n+k}{k}\frac{1}{2^k}x^{n}?$$ Even if I continue with this I am unable to get the correct answer.

*

*How does one prove this using the Snake oil technique?


*A combinatorial proof is also welcome, as are other kinds of proofs.
 [/INST] Suppose we seek to verify that
$$\sum_{k=0}^n {n+k\choose k} \frac{1}{2^k} = 2^n.$$
In the following we make an effort to use a different set of integrals
from the answer by @MarkusScheuer, for variety's sake, even if this is
not the simplest answer.
The difficulty here lies in the fact that the binomial coefficients on
the LHS do not have an upper bound for the sum wired into them. We use
an Iverson bracket to get around this:
$$[[0\le k\le n]]
= \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{w^k}{w^{n+1}} \frac{1}{1-w} \; dw.$$
Introduce furthermore
$${n+k\choose k} = 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{1}{(1-z)^{k+1}}  \; dz.$$
With  the  Iverson bracket  in  place  we can  let  the  sum range  to
infinity, getting
$$\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{1}{1-z}
\sum_{k\ge 0} \frac{w^k}{(1-z)^k} \frac{1}{2^k}
\; dz\; dw.$$
This converges  when $|w| <  |2(1-z)|.$ We require $\gamma \lt 2(1-\epsilon)$ or $\epsilon \lt 1-\gamma/2.$ Simplifying we have
$$\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{1}{1-z}
\frac{1}{1-w/(1-z)/2}
\; dz\; dw
\\ = \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{1}{1-z-w/2}
\; dz\; dw.$$
The pole at  $z=1-w/2$ is outside the contour  due to the requirements
on  convergence, so  we may  use the  negative of  the  residue there,
getting
$$\frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{1}{(1-w/2)^{n+1}} \; dw.$$
This  could have been  obtained by  inspection, bypassing  the Iverson
bracket.  Now  put $w (1-w/2) =  v$ so that $w  = 1-\sqrt{1-2v}$ (this
branch maps $w=0$ to $v=0$) to get (here we have $v=w-\cdots$ so the image of $|w|=\gamma$ makes one turn around the origin and may be deformed to a circle $|v|=\gamma'$)
$$\frac{1}{2\pi i}
\int_{|v|=\gamma'} \frac{1}{v^{n+1}}
\frac{1}{\sqrt{1-2v}} \frac{1}{\sqrt{1-2v}} \; dv
\\ = \frac{1}{2\pi i}
\int_{|v|=\gamma'} \frac{1}{v^{n+1}}
\frac{1}{1-2v} \; dv = 2^n.$$
This is the claim. Note that we may take $\gamma' \lt \gamma - \frac{1}{2} \gamma^2.$
 Observe that
$$\mathrm{Res}_{z=\infty} \frac{1}{z^{n+1}} \frac{1}{1-z-w/2}
= - \mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+1} \frac{1}{1-w/2-1/z}
\\ = - \mathrm{Res}_{z=0} z^{n} \frac{1}{z(1-w/2)-1} = 0.$$
This was an interesting exercise showing how the choice of contour for
convergence  influences the computation.  The branch  of $\sqrt{1-2v}$
that was used has the branch cut on $[1/2, \infty).$
</s>