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.
 A: Here is a probabilistic proof of your equality, which I will write as
$$
\sum_{k=0}^n\binom{n+k}{k}2^{-(n+k)}=1
$$
Consider a rectangular lattice of $(n+2)^2$ points, where the lower left point is $(0,0)$ and the upper right is $(n+1,n+1)$. An ant starts at $(0,0)$, and once per second, randomly chooses to take a step upwards or to the right. Furthermore, imagine the topmost row $\{(x,n+1):0\le x\le n\}$ and rightmost column $\{(n+1,y):0\le y\le n\}$ are covered in glue, so the ant stops moving once it reaches one of these points.
Eventually, the ant will get stuck. You can show that the probability the ant gets stuck at $(k,n+1)$ is equal to $\binom{n+k}{k}2^{-(n+k)}\cdot\frac12$ by considering all the possible paths that bring it to that point. Therefore, the probability the ant gets stuck at either $(k,n+1)$ or $(n+1,k)$ is equal to
$$
\binom{n+k}{k}2^{-(n+k)}
$$
Since the ant gets stuck at exactly one of these point, the sum of these probabilities must equal $1$.
A: This one can also be done using complex variables.

Suppose we seek to show that
$$\sum_{k=0}^{n} {n+k \choose k} \frac{1}{2^k} = 2^n.$$
Introduce the integral repesentation
$${n+k\choose k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz.$$
This gives for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z}
\sum_{k=0}^n \frac{(1+z)^k}{(2z)^k} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z}
\frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)/(2z)-1} \; dz
\\ = \frac{2}{2\pi i}
\int_{|z|=\epsilon} (1+z)^n
\frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)-2z} \; dz
\\ = \frac{2}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^n}{1-z}
\left((1+z)^{n+1}/(2z)^{n+1}-1\right) \; dz.$$
The second component makes no contribution inside the contour, leaving
just
$$\frac{2^{-n}}{2\pi i}
\int_{|z|=\epsilon} 
\frac{1}{z^{n+1}}
\frac{(1+z)^{2n+1}}{1-z}
 \; dz.$$
Extracting coefficients we get
$$2^{-n} [z^n] \frac{(1+z)^{2n+1}}{1-z} =
2^{-n} \sum_{q=0}^n {2n+1\choose q}
= 2^{-n}\times \frac{1}{2} \times 2^{2n+1} = 2^n.$$
A: Binomial coefficient is just $\binom{-(n-1)}{k} = (-1)^k \binom{n+k}{k}$ and take $x= -\frac{1}{2}$so you get $\sum_{k=0}^{\infty} \binom{-(n-1)}{k} x^k = \frac{1}{(1-x)^{n-1}}$
A: While this answer is basically the same as the one by Mike Earnest, and as the added interpretation in the answer by Brian Scott, let me phrase it slightly differently, as this comes close to a game already considered by Blaise Pascal (before probability theory even existed). Also I believe there is an essential invocation of symmetry here, which I could not find clearly stated in those answers.
Let two players play "best of $2n+1$" for repeatedly (fairly) tossing a fair coin: the first who gets $n+1$ favourable outcomes wins. By symmetry each has $\frac12$ chance of winning. On the other hand, let us count the winning possibilities for the player A, out of the $2^{2n+1}$ possible sequences (I imagine the coin to be tossed $2n+1$ times, even if the winner is determined earlier). The toss that wins for A (if it happens) has precisely $n$ outcomes favourable for A coming before it, and some number $k$ of unfavourable outcomes, with $0\leq k\leq n$; there then remain $n-k$ tosses after A has already won. For a given $k$ the number of possibilities is $\binom{n+k}k\times2^{n-k}$, the first factor counting the possibilities before the decisive toss and the second factor those after it. All in all we should get half of all $2^{2n+1}$ possibilities, so
$$
  \sum_{k=0}^n\binom{n+k}k\times2^{n-k}=2^{2n}
$$
from which the stated identity follows after division by $2^n$.
To add a bit about the Pascal reference, what he really considers is the question of how to fairly split the stakes (taking into account their chances to eventually win) when prematurely ending such a game when players A and B need a different number of favourable outcomes to the finish line. If A still has $a$ wins to go and B needs $b$ wins, he establishes the that the stakes should be divided as the proportion of the sum of the first $b$ to the sum of the remaining $a$ entries in the line of Pascal's triangle that has length $a+b$ (to Pascal that was the "base" with "exposant $a+b$" of the triangle; to us it is line $a+b-1$). The case considered here is the easy one with $a=b$, so the proportion clearly becomes $1:1$. In the general case, counting as done above leads to the interesting identity
$$
  \sum_{k=0}^{b-1}\binom{a+b-1}k = \sum_{k=0}^{b-1}\binom{a-1+k}k\times2^{b-1-k},
$$
or putting $n=b-1$:
$$
  \sum_{k=0}^n\binom{a+n}k = \sum_{k=0}^n\binom{a-1+k}k\times2^{n-k},
$$
This is fairly easy to prove by induction on $n$. Note that taking (also) $a=n+1$ one gets the formula of this question, as the LHS then gives $2^{2n+1}/2=2^{2n}$.
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}}
 \newcommand{\mrm}[1]{\,\mathrm{#1}}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\mrm{f}_{n}\pars{x} & \equiv \sum_{k = 0}^{n}{n + k \choose k}x^{k} =
\color{#f00}{{1 \over n!}\sum_{k = 0}^{n}{\pars{n + k}! \over  k!}x^{k}} =
\pars{n + 1} + {1 \over n!}\sum_{k = 1}^{n}
{n + k \over k}{\pars{n + k - 1}! \over  \pars{k - 1}!}x^{k}
\\[5mm] & =
n + 1 + {1 \over n!}\sum_{k = 0}^{n - 1}
{n + k + 1 \over k + 1}{\pars{n + k}! \over  k!}x^{k + 1}
\\[5mm] & =
1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} +
{n \over n!}\,x\sum_{k = 0}^{n}
{1  \over k + 1}{\pars{n + k}! \over  k!}x^{k} +
x\color{#f00}{{1 \over n!}\sum_{k = 0}^{n}
{\pars{n + k}! \over  k!}x^{k}}
\\[5mm] & =
1  - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + {n \over n!}\,x\sum_{k = 0}^{n}x^{k}
{\pars{n + k}! \over  k!}\int_{0}^{1}y^{k}\,\dd y +
x\mrm{f}_{n}\pars{x}
\\[5mm] & =
1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + nx\int_{0}^{1}\color{#f00}{{1 \over n!}\sum_{k = 0}^{n}
{\pars{n + k}! \over  k!}\pars{xy}^{k}}\,\dd y +
x\mrm{f}_{n}\pars{x}
\\[5mm] & =
1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + n\int_{0}^{1}\mrm{f}_{n}\pars{xy}\,x\,\dd y +
x\mrm{f}_{n}\pars{x}
\end{align}

$$
\imp\quad
\begin{array}{|c|}\hline\mbox{}\\
\ds{\quad\mrm{f}_{n}\pars{x} =
1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + n\int_{0}^{x}\mrm{f}_{n}\pars{y}\,\dd y + x\mrm{f}_{n}\pars{x}
\quad}
\\ \mbox{}\\ \hline
\end{array}
$$

Then,
\begin{align}
\mrm{f}_{n}'\pars{x} & =
-\pars{2n + 1}{2n \choose n}x^{n} +
n\mrm{f}_{n}\pars{x} + \mrm{f}_{n}\pars{x} +
x\mrm{f}_{n}'\pars{x}
\,,\quad\mrm{f}_{n}\pars{0} = 1
\end{align}

$$
\mrm{f}_{n}'\pars{x} - {n + 1 \over 1 - x}\,\mrm{f}_{n}\pars{x} =
-\pars{2n + 1}{2n \choose n}{x^{n} \over 1 - x}
$$

$$
\totald{\bracks{\pars{1 - x}^{n + 1}\mrm{f}_{n}\pars{x}}}{x} =
-\pars{2n + 1}{2n \choose n}x^{n}\pars{1 - x}^{n}
$$

$$
2^{-n - 1}\,\,\mrm{f}_{n}\pars{\half} - 1 =
-\pars{2n + 1}{2n \choose n}\int_{0}^{1/2}x^{n}\pars{1 - x}^{n}\,\dd x
$$

\begin{align}
\color{#f00}{\sum_{k = 0}^{n}{n + k \choose k}x^{k}} & =
\mrm{f}_{n}\pars{\half} =
2^{n + 1}\ -\ \overbrace{%
2^{n + 1}\pars{2n + 1}{2n \choose n}
\int_{0}^{1/2}\bracks{{1 \over 4} - \pars{x - \half}^{2}}^{n}\,\dd x}
^{\ds{2^{n}}}
\\[5mm] & = \color{#f00}{2^{n}}
\end{align}


Note that
  $$
\int_{0}^{1/2}\bracks{{1 \over 4} - \pars{x - \half}^{2}}^{n}\,\dd x =
\half\,\
\overbrace{{\Gamma\pars{n + 1}\Gamma\pars{n + 1} \over \Gamma\pars{2n + 2}}}
^{\ds{\mrm{B}\pars{n + 1,n + 1}}}\ =\
{1 \over 2\pars{2n + 1}{2n \choose n}}
$$
  $\ds{\Gamma}$: Gamma Function. B: Beta Function.

A: $$\begin{align}
\sum_{k=0}^n \binom {n+k}k\frac 1{2^k}
&=\frac 1{2^n}\sum_{k=0}^n \color{blue}{2^{n-k}}\binom {n+k}n\\
&=\frac 1{2^n}\sum_{k=0}^n\color{blue}{\sum_{r=0}^{n-k}\binom {n-k}r}\binom{n+k}r\\
&=\frac 1{2^n}\sum_{s=0}^n\sum_{r=0}^s\binom  sr\binom {2n-s}n
&&\scriptsize (\text{Putting  } s=n-k)\\
&=\frac 1{2^n}\sum_{r=0}^n\sum_{s=r}^n \binom s{s-r}\binom{2n-s}{n-s}\\
&=\frac 1{2^n}\sum_{r=0}^n\sum_{s=r}^n(-1)^{s-r}\binom {-r-1}{s-r}(-1)^{n-s}\binom {-n-1}{n-s}
&&\scriptsize(\text{Upper Negation})\\
&=\frac 1{2^n}\sum_{r=0}^n(-1)^{n-r}
\color{magenta}{\sum_{s=r}^n\binom {-r-1}{s-r}\binom{-n-1}{n-s}}\\
&=\frac 1{2^n}\sum_{r=0}^n(-1)^{n-r}\color{magenta}{\binom {-n-r-2}{n-r}}&&\scriptsize(\text{Vandermonde})\\
&=\frac 1{2^n}\sum_{r=0}^n(-1)^{n-r}(-1)^{n-r}\binom {2n+1}{n-r}&&\scriptsize(\text{Upper Negation})\\
&=\frac 1{2^n}\sum_{r=0}^n\binom{2n+1}{n-r}\\
&=\frac 1{2^n}\cdot \frac 12 \sum_{r=0}^n \binom {2n+1}{n-r}+\binom {2n+1}{n+r+1}
&&\scriptsize(\text{both summands are equal})\\
&=\frac 1{2^{n+1}}\sum_{r=0}^{2n+1}\binom {2n+1}r\\
&=\frac 1{2^{n+1}}\cdot 2^{2n+1}\\\\
&=2^n\qquad \blacksquare
\end{align}$$
A: Let
$$
S_n:=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}}
$$
Obviously $S_0=1$. Assume that equality
$$S_{n-1}=1\tag1$$ 
is valid for some $n$. Then it is valid for $n+1$ as well:
$$
\begin{align}
S_n
&=\sum_{k=0}^n\frac{\binom{n+k}{k}}{2^{n+k}}\\
&=\sum_{k=0}^n\frac{\binom{n+k-1}{k-1}+\binom{n-1+k}{k}}{2^{n+k}}\\
&=\frac12\sum_{k=0}^{n-1}\frac{\binom{n+k}{k}}{2^{n+k}}+\frac12\sum_{k=0}^n\frac{\binom{n-1+k}{k}}{2^{n-1+k}}\\
&=\frac12S_n-\frac{\binom{2n}{n}}{2^{2n+1}}+\frac12S_{n-1}+\frac{\binom{2n-1}{n}}{2^{2n}}\\
&=\frac12S_n+\frac12S_{n-1}\implies S_n=S_{n-1}\stackrel{I.H.}=1.
\end{align}
$$
Thus, by induction the equality $(1)$ is valid for all integer $n\ge0$.
A: This is a nice case where induction loading (the technique of deliberately strengthening what is to be proved for the purpose of making proofs by induction easier) is handy. For motivation see my other answer. Generalise the statement to the claim
$$
  \sum_{k=0}^n\binom{m+n+1}k =\sum_{k=0}^n\binom{m+k}k\times2^{n-k}, \tag1
$$
knowing that for $m=n$ the first sum gives $\sum_{k=0}^{n}\binom{2n+1}k=\frac12\sum_{k=0}^{2n+1}\binom{2n+1}k=2^{2n}$, and one can divide both sides by $2^n$.
Proof of $(1)$ by induction on $n$. For $n=0$ one gets $\binom {m+1}0=1=\binom m0$, so this is fine. So suppose $n>0$ and the result established for $n-1$. We can write $\binom{m+n+1}k=\binom{m+n}k+\binom{m+n}{k-1}$ by Pascal's recurrence (with the convention $\binom a{-1}=0$ for any $a$) so the left hand side is
$$
  \sum_{k=0}^n\left(\binom{m+n}k+\binom{m+n}{k-1}\right)
 =\sum_{k=0}^n\binom{m+n}k+\sum_{l=-1}^{n-1}\binom{m+n}l
\\ =2\sum_{k=0}^{n-1}\binom{m+n}k+\binom{m+n}n.
$$
Now we can apply the induction hypothesis to the summation, and get
$$
  2\sum_{k=0}^{n-1}\binom{m+k}k\times2^{n-1-k}+\binom{m+n}n
=\sum_{k=0}^n\binom{m+k}k\times2^{n-k}
$$
as desired.
A: Another probabilistic interpretation/proof
Consider the following problem: Flip a fair coin for $2n+1$ times sequentially, along the way, how many times do we have exactly $n+1$ heads or tails occur in the sequence on expectation?
Clearly, the solution is only 1 time (by just a little bit logically reasoning.
On the other hand, the expression $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^{n+k}}$ is the expectation as well (by using expectation definition).
These two answers must be equal, so, the equality is proved.
A: A proof by induction is possible, if a bit messy. For $n\in\Bbb N$ let $$s_n=\sum_{k=0}^n\binom{n+k}k\frac1{2^k}\;.$$ Clearly $s_0=1=2^0$. Suppose that $s_n=2^n$ for some $n\in\Bbb N$. Then
$$\begin{align*}
s_{n+1}&=\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\
&=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\frac1{2^k}\\\\
&=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}\\\\
&=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=1}^n\binom{n+k}{k-1}\frac1{2^k}\\\\
&=\binom{2n+2}{n+1}\frac1{2^{n+1}}+s_n+\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^{k+1}}\\\\
&=s_n+\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\
&=2^n+\left(\binom{2n+1}{n+1}+\binom{2n+1}n\right)\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\
&=2^n+\binom{2n+1}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\
&\overset{(*)}=2^n+\frac12\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\
&=2^n+\frac12\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\
&=2^n+\frac12s_{n+1}\;,
\end{align*}$$
where the step $(*)$ follows from the fact that 
$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n=2\binom{2n+1}{n+1}\;.$$
Thus, $\frac12s_{n+1}=2^n$, and $s_{n+1}=2^{n+1}$, as desired.
Added: I just came up with a combinatorial argument as well. Flip a fair coin until either $n+1$ heads or $n+1$ tails have appeared. Let $k$ be the number of times the other face of the coin has appeared; clearly $0\le k\le n$. The last flip must result in the $(n+1)$-st instance of the majority face, but the other $n$ instances of that face and $k$ of the other can appear in any order. 
Now imagine that after achieving the desired outcome we continue to flip the coin until we’ve flipped it $2n+1$ times. There are altogether
$$\binom{n+k}k2^{(2n+1)-(n+k)}=\binom{n+k}k2^{n+1-k}$$
sequences of $2n+1$ flips that decide the outcome at the $(n+k+1)$-st toss, so
$$\sum_{k=0}^n\binom{n+k}k2^{n+1-k}=2^{2n+1}\;,$$
and
$$\sum_{k=0}^n\binom{n+k}k\frac1{2^k}=2^n\;.$$
A: Let $S_n:=\sum\limits_{k=0}^n\,\binom{n+k}{k}\,\frac{1}{2^k}$ for every $n=0,1,2,\ldots$.  Then, $$S_{n+1}=\sum_{k=0}^{n+1}\,\binom{(n+1)+k}{k}\,\frac{1}{2^k}=\sum_{k=0}^{n+1}\,\Biggl(\binom{n+k}{k}+\binom{n+k}{k-1}\Biggr)\,\frac{1}{2^k}\,.$$
Hence,
$$S_{n+1}=\left(S_n+\binom{2n+1}{n+1}\frac{1}{2^{n+1}}\right)+\sum_{k=0}^n\,\binom{(n+1)+k}{k}\,\frac{1}{2^{k+1}}\,.$$
That is,
$$S_{n+1}=S_n+\frac{S_{n+1}}{2}+\frac{1}{2^{n+2}}\,\Biggl(2\,\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\Biggr)\,.$$
As $$\binom{2n+2}{n+1}=\frac{2n+2}{n+1}\,\binom{2n+1}{n}=2\,\binom{2n+1}{n+1}\,,$$
we deduce that $S_{n+1}=S_n+\frac{S_{n+1}}{2}$, or
$$S_{n+1}=2\,S_{n}$$
for all $n=0,1,2,\ldots$.  Because $S_0=1$, the claim follows.

Combinatorial Argument
The number of binary strings of length $2n+1$ with at least $n+1$ ones is clearly $2^{2n}$.  For $k=0,1,2,\ldots,n$, the number of such strings whose $(n+1)$-st one is at the $(n+k+1)$-st position is $\binom{n+k}{k}\,2^{n-k}$.  The claim is now evident.
A: Here is a variation based upon the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series. We can write e.g.
\begin{align*}
[x^k](1+x)^n=\binom{n}{k}
\end{align*}

We obtain
  \begin{align*}
\sum_{k=0}^n\binom{n+k}{k}\frac{1}{2^k}&=\sum_{k=0}^n[x^k](1+x)^{n+k}\frac{1}{2^k}\tag{1}\\
&=[x^0](1+x)^n\sum_{k=0}^n\left(\frac{1+x}{2x}\right)^k\tag{2}\\
&=[x^0](1+x)^n\frac{1-\left(\frac{1+x}{2x}\right)^{n+1}}{1-\frac{1+x}{2x}}\tag{3}\\
&=[x^0](1+x)^n\frac{1}{(2x)^n}\frac{(2x)^{n+1}-(1+x)^{n+1}}{x-1}\tag{4}\\
&=\frac{1}{2^n}[x^n]\frac{(1+x)^{2n+1}}{1-x}\tag{5}\\
&=\frac{1}{2^n}[x^n]\sum_{k=0}^{2n+1}\binom{2n+1}{k}x^k\frac{1}{1-x}\tag{6}\\
&=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}[x^{n-k}]\frac{1}{1-x}\tag{7}\\
&=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}\tag{8}\\
&=\frac{1}{2^n}\cdot\frac{1}{2}2^{2n+1}\tag{9}\\
&=2^n
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we apply the coefficient of operator.

*In (2) we use the linearity of the coefficient of operator and the rule
$$[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$$

*In (3) we use the finite geometric series formula.

*In (4) we do some simplifications.

*In (5) we use again the rule stated in comment (2) and note that the term $(2x)^{n+1}$ can be ignored, since it does not contribute to the coefficient of $x^n$.

*In (6) we apply the binomial sum formula.

*In (7) we note that only index up to $k=n$ contributes to the coefficient of $x^n$.

*In (8) we recall the geometric series is
$$\frac{1}{1-x}=1+x+x^2+\cdots$$
so that the contribution to the coefficient is always $1$.

*In (9) we use the symmetry of the binomial sum formula.
A: Since
$$
\binom{2n-1}{n}+\binom{2n-1}{n-1}=\binom{2n}{n}\quad\text{and}\quad\binom{2n-1}{n}=\binom{2n-1}{n-1}\tag{1}
$$
we have
$$
\binom{2n-1}{n}=\frac12\binom{2n}{n}\tag{2}
$$
Therefore, if we define
$$
\begin{align}
A_n
&=\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}\tag{3a}\\
&=\sum_{k=0}^n\left[\binom{n+k-1}{k}+\binom{n+k-1}{k-1}\right]\frac1{2^k}\tag{3b}\\
&=\sum_{k=0}^n\binom{n+k-1}{k}\frac1{2^k}\\
&+\sum_{k=0}^{n-1}\binom{n+k}{k}\frac1{2^{k+1}}\tag{3c}\\
&=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\binom{2n-1}{n}\frac1{2^n}\\
&+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}-\binom{2n}{n}\frac1{2^{n+1}}\tag{3d}\\
&=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}\tag{3e}\\
&=A_{n-1}+\frac12A_n\tag{3f}
\end{align}
$$
Explanation:
$\text{(3a)}$: define $A_n$
$\text{(3b)}$: use Pascal's Triangle
$\text{(3c)}$: substitute $k\mapsto k+1$ in the second sum
$\text{(3d)}$: add and subtract the last term in each sum
$\text{(3e)}$: use $(2)$ to cancel the terms separated in $\text{(3d)}$
$\text{(3f)}$: use the definition of $A_n$
Thus, $\text{(3f)}$ implies that
$$
A_n=2A_{n-1}\tag{4}
$$
Since $A_0=1$, we get that
$$
A_n=2^n\tag{5}
$$
A: 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).$
A: The required equality can be written as
$$\sum_{k=0}^n \binom{n+k}{k} 2^{n-k} = 2^{2n}$$
Now, we have
$$\sum\binom{n+k}{k} x^k = \frac{1}{(1-x)^{n+1}}$$
Therefore, our sum equals the coefficient of $x^n$ in the product
$$[x^n]\frac{1}{(1-x)^{n+1}(1-2 x)}= [x^{-1}]\cdot \frac{1}{(1-2x)(x(1-x))^{n+1}} $$
Equivalently, we have to show that the residue at $x=0$ of
$$\frac{2}{1-x} \cdot \left(\frac{1}{x(2-x)}\right)^{n+1} $$
is $1$, for all $n\ge 0$ (example with WA).
Now, let's recall the Lagrange–Bürmann formula. Consider $f(x)$ an analytic function $f(0) = 0$, $f'(0) \ne 0$, with inverse $g(x)$,  $H$ an analytic function. Then we have
$$\operatorname{Res}_{x=0}\  H'(x) \cdot \frac{1}{f^n(x)}= n[x^n] H(g(x))$$
for all $n\ge 1$.
Now, $f(x) = x(2-x)$, with inverse $g(x) = 1 - \sqrt{1-x}$, $H'(x) = \frac{2}{1-x}$, $H(x) = \log\frac{1}{(1-x)^2}$. Now,
$$H(g(x)) = \log\frac{1}{(1-(1-\sqrt{1-x}))^2}= \log\frac{1}{1-x}= \sum_{n\ge 1} \frac{x^n}{n}$$
We are done.
