Prove a binomial identity $\sum^{n}_{k=0}\binom{n+k}{k}2^{-k} = 2^n$ I was asked to show that 
$\sum^{n}_{k=0}\binom{n+k}{k}2^{-k} = 2^n$ using pascal identity. I don't know how to do it. Whenever I was trying to use $\binom{n+k+1}{k} = \binom{n+k}{k}+\binom{n+k}{k-1}$, my index is always off by 1.
 A: $\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,}
 \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{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#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{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
a_{n} & \equiv \sum_{k = 0}^{n}{n + k \choose k}2^{-k} =
\sum_{k = 0}^{n}{n + k - 1 \choose k}2^{-k} +
\sum_{k = 1}^{n}{n + k -1 \choose k - 1}2^{-k}
\\[5mm] &=
\sum_{k = 0}^{n}{n + k - 1 \choose k}2^{-k} +
\sum_{k = 0}^{n - 1}{n + k \choose k}2^{-k - 1}
\\[5mm] &=
\bracks{\underbrace{\sum_{k = 0}^{n - 1}{n + k - 1 \choose k}2^{-k}}
_{a_{n - 1}} + {2n - 1 \choose n}2^{-n}} +
{1 \over 2}\bracks{\underbrace{\sum_{k = 0}^{n}{n + k \choose k}2^{-k}}
_{\ds{a_{n}}} - {2n \choose n}2^{-n}}
\end{align}

\begin{align}
a_{n} & =
2a_{n - 1} + {2n - 1 \choose n}2^{-n + 1} - {2n \choose n}2^{-n}
\\[5mm] & =
2a_{n - 1} + {2n - 1 \choose n}2^{-n + 1} - \bracks{{2n - 1 \choose n} +
{2n - 1 \choose n - 1}}2^{-n}
\\[5mm] & =
2a_{n - 1} + {2n - 1 \choose n}2^{-n} - {2n - 1 \choose n - 1}2^{-n} =
2a_{n - 1} + {2n - 1 \choose n}2^{-n} - {2n - 1 \choose n}2^{-n}
\\[5mm] \implies & \bbx{\ds{a_{n} = 2a_{n - 1}}}
\end{align}

$$
a_{n} \equiv \sum_{k = 0}^{n}{n + k \choose k}2^{-k} =
2a_{n - 1} = 2^{2}a_{n - 2} = 2^{3}a_{n - 3} = \cdots = 2^{n}a_{0} =
\bbx{\ds{2^{n}}}\quad\mbox{because}\quad a_{0} = 1
$$
A: Pascal distribution
Let $f$ be the probability mass function of the Pascal distribution with $r=n+1$ and $p=1-p=\frac 1 2$, $$f(k;n+1,\frac 1 2)=\Pr(X=k)={\binom {k+n}{k}}p^{k}(1-p)^{r}\quad {\text{for }}k \in \Bbb N$$then
$$
\Pr(X\leq n)= \sum^{n}_{k=0}\binom{n+k}{k}(\frac 1 2)^k(\frac 1 2)^{n+1}
$$
Since $\Pr(X\leq n)=I_{\frac 1 2}(n+1,n+1)$, and
$$
I_{\frac 1 2}(n+1,n+1)={\frac {\mathrm {B} ({\frac 1 2};\,n+1,n+1)}{\mathrm {B} (n+1,n+1)}}=\frac 1 2
$$
we have $$\Pr(X\leq n)=\sum^{n}_{k=0}\binom{n+k}{k}(\frac 1 2)^k(\frac 1 2)^{n+1}=\frac 1 2$$
thus,
$$\sum^{n}_{k=0}\binom{n+k}{k}(\frac 1 2)^k=2^{n+1}\frac 1 2=2^n$$
