Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$ I just found this identity but without any proof, could you just give me an hint how I could prove it?
$$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$
I know that $$2^n = \sum\limits_{k=0}^n \binom{n}{k}$$ but that didn't help me
 A: You can prove it by induction on $n$. Here’s a start. Let
$$f(n)=\sum_{k=0}^n2^{-k}\binom{n+k}k\;;$$
clearly $f(0)=1=2^0$. Assume that $f(n)=2^n$ for some $n\ge 0$. Then
$$\begin{align*}
f(n+1)&=\sum_{k=0}^{n+1}2^{-k}\binom{n+1+k}k\\
&=\sum_{k=0}^{n+1}2^{-k}\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\\
&=\sum_{k=0}^{n+1}2^{-k}\binom{n+k}k+\sum_{k=1}^{n+1}2^{-k}\binom{n+k}{k-1}\\
&=2^{-(n+1)}\binom{2n+1}{n+1}+\sum_{k=0}^n2^{-k}\binom{n+k}k+\sum_{k=0}^n2^{-(k+1)}\binom{n+1+k}k\\
&=2^{-(n+1)}\binom{2n+1}{n+1}+2^n+\frac12\sum_{k=0}^n2^{-k}\binom{n+1+k}k\;,
\end{align*}$$
and
$$f(n+1)=2^{-(n+1)}\binom{2n+2}{n+1}+\sum_{k=0}^n2^{-k}\binom{n+1+k}k\;.$$
Now combine these results and use the fact that
$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n=2\binom{2n+1}n$$
to complete the induction step.
A: I tried to generalize, but equation $(2)$ shows why $x=\frac12$ is needed to make a simple equation.
Note that
$$
\begin{align}
\sum_{k=0}^{n+1}x^k\binom{n+k+1}{k}
&=\sum_{k=0}^{n+1}x^k\left[\binom{n+k}{k}+\binom{n+k}{k-1}\right]\\
&=\sum_{k=0}^nx^k\binom{n+k}{k}+x^{n+1}\binom{2n+1}{n+1}\\
&+\sum_{k=0}^{n+1}x^{k+1}\binom{n+k+1}{k}-x^{n+2}\binom{2n+2}{n+1}\tag{1}
\end{align}
$$
Moving terms around and multiplying by $(1-x)^n$, we have
$$
\begin{align}
\hspace{-1cm}(1-x)^{n+1}\sum_{k=0}^{n+1}x^k\binom{n+k+1}{k}
&=(1-x)^n\sum_{k=0}^nx^k\binom{n+k}{k}\\
&+(1-x)^n\left[x^{n+1}\binom{2n+1}{n}-x^{n+2}\binom{2n+2}{n+1}\right]\\
&=(1-x)^n\sum_{k=0}^nx^k\binom{n+k}{k}\\
&+(1-x)^n\left[\frac12x^{n+1}-x^{n+2}\right]\binom{2n+2}{n+1}\tag{2}
\end{align}
$$
since $\binom{2n+1}{n+1}=\binom{2n+1}{n}$ and $\binom{2n+1}{n+1}+\binom{2n+1}{n}=\binom{2n+2}{n+1}$.
Setting $x=\frac12$ in $(2)$ yields
$$
\begin{align}
2^{-n-1}\sum_{k=0}^{n+1}2^{-k}\binom{n+k+1}{k}
&=2^{-n}\sum_{k=0}^n2^{-k}\binom{n+k}{k}\\
&\vdots\\
&=2^{-0}\sum_{k=0}^02^{-k}\binom{0+k}{k}\\[9pt]
&=1\tag{3}
\end{align}
$$
Therefore,
$$
\sum_{k=0}^n2^{-k}\binom{n+k}{k}=2^n\tag{4}
$$
A: Suppose we seek to verify that
$$S_n = \sum_{k=0}^n 2^{-k} {n+k\choose k} = 2^n.$$
We introduce the Iverson bracket
$$[[k\le n]] =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \frac{1}{1-z}
\; dz$$
so we may extend $k$ to infinity, getting
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z}
\sum_{k\ge 0} 2^{-k} {n+k\choose n} z^k
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z}
\frac{1}{(1-z/2)^{n+1}}
\; dz.$$
We evaluate this using the negative  of the residues at $z=1, z=2$ and
$z=\infty.$ Here the contour does not include the other two finite poles
which also ensures that the geometric series converges. We could choose
$\epsilon = 1/2.$ We get for the residue at $z=1$
$$- \frac{1}{(1/2)^{n+1}} = - 2^{n+1}.$$
For the residue at $z=2$ we write
$$(-1)^{n+1} \mathrm{Res}_{z=2}
\frac{1}{z^{n+1}} \frac{1}{1-z}
\frac{1}{(z/2-1)^{n+1}}
\\ = (-1)^{n+1} 2^{n+1} \mathrm{Res}_{z=2}
\frac{1}{z^{n+1}} \frac{1}{1-z}
\frac{1}{(z-2)^{n+1}}
\\ = (-1)^{n} 2^{n+1} \mathrm{Res}_{z=2}
\frac{1}{(2+(z-2))^{n+1}} \frac{1}{1+(z-2)}
\frac{1}{(z-2)^{n+1}}
\\ = (-1)^{n} \mathrm{Res}_{z=2}
\frac{1}{(1+(z-2)/2)^{n+1}} \frac{1}{1+(z-2)}
\frac{1}{(z-2)^{n+1}}.$$
This is
$$(-1)^n \sum_{q=0}^n (-1)^q {n+q\choose q} 2^{-q} (-1)^{n-q}
= \sum_{q=0}^n {n+q\choose q} 2^{-q} = S_n.$$
Finally do the residue at $z=\infty$ getting (this also follows by
inspection having degree zero in the numerator and degree $2n+3$ in the
denominator)
$$\mathrm{Res}_{z=\infty} \frac{1}{z^{n+1}} \frac{1}{1-z}
\frac{1}{(1-z/2)^{n+1}}
\\ = - \mathrm{Res}_{z=0} \frac{1}{z^2}
z^{n+1} \frac{1}{1-1/z} \frac{1}{(1-1/2/z)^{n+1}}
\\ = - \mathrm{Res}_{z=0} \frac{1}{z}
z^{n+1} \frac{1}{z-1} \frac{z^{n+1}}{(z-1/2)^{n+1}}
\\ = - \mathrm{Res}_{z=0} z^{2n+1}
\frac{1}{z-1} \frac{1}{(z-1/2)^{n+1}} = 0.$$
Using the fact that the residues sum to zero we thus obtain
$$S_n - 2^{n+1} + S_n = 0$$
which yields
$$\bbox[5px,border:2px solid #00A000]{
S_n = 2^n.}$$
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{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{2^n = \sum_{k = 0}^{n}2^{-k}{n + k \choose k}:\ {\large ?}}$

$\ds{\tt\mbox{The following method is a straightforward one}}$.
  

Hereafter we'll use the identity
$$\begin{array}{|c|}\hline\\
\ds{\quad{\,m \choose \ell\,}=\oint_{\verts{z}\ =\ b\ >\ 0}
{\pars{1 + z}^{m} \over z^{\ell + 1}}\,{\dd z \over 2\pi\ic}\quad}
\\ \\ \hline
\end{array}
$$

\begin{align}&\color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k}}
=\sum_{k = -\infty}^{n}2^{-k}{n + k \choose n}
=\sum_{k = \infty}^{-n}2^{k}{n - k \choose n}
=\sum_{k = \infty}^{0}2^{k - n}{2n - k \choose n}
\\[5mm]&=2^{-n}\sum_{k = 0}^{\infty}2^{k}{2n - k \choose n}
=2^{-n}\sum_{k = 0}^{\infty}2^{k}\oint_{\verts{z}\ =\ a\ >\ 1}
{\pars{1 + z}^{2n - k} \over z^{n + 1}}
\,{\dd z \over 2\pi\ic}
\\[5mm]&=2^{-n}\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}}
\sum_{k = 0}^{\infty}\pars{2 \over 1 + z}^{k}\,{\dd z \over 2\pi\ic}
\\[5mm]&=2^{-n}\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}}
{1 \over 1 - 2/\pars{1 + z}}\,{\dd z \over 2\pi\ic}
=2^{-n}\oint_{\verts{z}\ =\ a\ >\ 1}
{\pars{1 + z}^{2n + 1} \over z^{n + 1}\pars{z - 1}}\,{\dd z \over 2\pi\ic}
\\[5mm]&=2^{-n}\sum_{k = 0}^{\infty}
\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{2n + 1} \over z^{n + 2 + k}}\,{\dd z \over 2\pi\ic}
=2^{-n}\sum_{k = 0}^{\infty}{2n + 1 \choose n + k + 1}
\end{align}

$$
\mbox{Then,}\quad\color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k}}
=2^{-n}\color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}}\tag{1}
$$

The $\ds{\color{#c00000}{\mbox{"red expression"}}}$ in $\pars{1}$
  becomes:
  \begin{align}
&\color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}}
=\sum_{k = 0}^{-n}{2n + 1 \choose n + k}
=\sum_{k = n}^{0}{2n + 1 \choose k}
=\sum_{k = 0}^{2n + 1}{2n + 1 \choose k}
-\sum_{k = n + 1}^{2n + 1}{2n + 1 \choose k}
\\[3mm]&=2^{2n + 1} -\sum_{k = 0}^{n}{2n + 1 \choose k + n + 1}
=2^{2n + 1} - \color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}}\ \imp\
\begin{array}{|c|}\hline\\
\quad\color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}} = 2^{2n}\quad
\\ \\ \hline
\end{array}
\end{align}

We replace this result in expression $\pars{1}$:
$$
\color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k} = 2^{n}}
$$
A: Inspired by robjohn's answer I show a more general statement: for $x\in \mathbb{R}$ and $n\in\mathbb{N}$,
$$\bbox[5px,border:2px solid #0000A0]{\sum_{k=0}^{n}\binom{n+k}{k}((1-x)^{n+1}x^k+x^{n+1}(1-x)^k)=1}$$
Such identity appears as equation 69 at this page (see hypergeometric's comment).  OP's identity follows by setting $x=1/2$.
Let 
$$f_n(x)=\sum_{k=0}^{n}\binom{n+k}{k}x^k$$
then we have to show by induction that
$$(1-x)^{n+1}f_n(x)+x^{n+1}f_n(x)=1.$$
Base case: for $n=0$  it is trivial. 
\noindent Inductive step step. We note that
\begin{align*}
f_{n+1}(x)
&=\sum_{k=0}^{n+1}\left(\binom{n+k}{k}+\binom{n+1+k-1}{k-1}\right)x^k\\
&=f_n(x)+\binom{2n+1}{n+1}x^{n+1}+xf_{n+1}(x)-\binom{2n+2}{n+1}x^{n+2}\\
&=f_n(x)+\binom{2n+1}{n}x^{n+1}+xf_{n+1}(x)-2\binom{2n+1}{n}x^{n+2}
\end{align*}
Therefore
$$(1-x)f_{n+1}(x)=f_n(x)+\binom{2n+1}{n}x^{n+1}(1-2x)$$
Hence
$$(1-x)^{n+2}f_{n+1}(x)
=(1-x)^{n+1}f_n(x)+\binom{2n+1}{n}(1-x)^{n+1}x^{n+1}(1-2x)$$
and, by replacing $x$ with $(1-x)$, we get
$$x^{n+2}f_{n+1}(1-x)
=x^{n+1}f_n(1-x)-\binom{2n+1}{n}x^{n+1}(1-x)^{n+1}(1-2x).$$
Finally, by adding the last two equations we find
$$(1-x)^{n+2}f_{n+1}(x)+x^{n+2}f_{n+1}(1-x)=
x^{n+1}f_n(1-x)+(1-x)^{n+1}f_n(x)=1$$
and we are done.
A: $$\sum\limits_{k=0}^{n}\binom{k+m}{m}z^k=\frac{1}{(1-z)^{m+1}}-\frac{z^{n+1}}{(1-z)^{m+1}}\sum\limits_{k=0}^{m}\binom{n+k}{k}(1-z)^k$$
$$n=m, z=\frac{1}{2}$$
$$\sum\limits_{k=0}^{n}\binom{k+n}{n}\frac{1}{2^k}=\frac{1}{\frac{1}{2^{n+1}}}-\frac{\frac{1}{2^{n+1}}}{\frac{1}{2^{n+1}}}\sum\limits_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}$$
$$S=2^{n+1}-S, 2S = 2^{n+1}, S=2^n$$
A: Let's do this in lazy, stream of consciousness fashion, adjusting little details one by one until it looks like a recognizable enumeration.
First combinatorialize it by multiplying the whole thing by $2^n$, to
$$2^{2n} = \sum\limits_{k=0}^n 2^{n-k} \cdot \binom{n+k}{k}$$
This looks better, because $(n-k)$ and $(n+k)$ look like a decomposition of $2n$.  The left side counts all subsets of a $2n$ element set, so maybe something about the larger and the smaller subset in the partition of $2n$ elements into a subset and its complement.  Some fuzzy feeling about needing to break the symmetry when the sets are of equal size tells to multiply by $2$ and consider subsets of a $2n+1$ element set, which as a partition of the set has a larger and a smaller part.  So,
$$2^{2n+1} = \sum\limits_{k=0}^n 2 \times 2^{n-k} \cdot \binom{n+k}{k}$$  or
$$2^{2n+1} = \sum\limits_{k=0}^n 2 \times 2^{n-k} \cdot \binom{n+k}{n}$$ 
Better!  A subset of a size $2n+1$ set is equivalent to a partition into (larger set with more than $n$ elements) $\cup$ (smaller set with less than $n$ elements), and a choice (the $\times 2$) of which one is the subset.  And we can pick the larger subset by first selecting its largest $n+1$ elements, then adding some random subset from the lower indexed elements (this is the $2^{n-k}$), and... ok, it is all clear now:

From the first $2n+1$ integers, select a subset by partitioning into a large and a small subset and picking ($\times 2$) one of them as the set.  Determine the large subset, which has at least $n+1$ elements, by selecting an index $j$ from $1$ to $n+1$ as the location of the $(n+1)$th-largest element of the set, selecting the $n$ elements above $j$ (there are ${2n+1 - j} \choose {n}$ options) and adding any subset of the elements below $j$ (there are $2^{j-1}$ of those).  This is the last sum with $k = n+1 - j$.    

In the opposite direction, divide by $2^n$ to get
$$1 = \sum\limits_{k=0}^n 2^{-(n+k)} \cdot \binom{n+k}{n}$$
and look for a natural probability process that delivers this distribution. One answer: 

Throw a coin to determine whether voters $1, 2, \ldots$ are supporting candidate $A$ or $B$ in an election, and stop the process when one candidate reaches $n+1$ votes.  Stopping happens at a time $t$ between $n+1$ and $2n+1$ steps, and if $k=t-1-n$, the set of times at which the victorious candidate received votes before time $t$ is one of ${{t-1} \choose n} = {{n+k} \choose n}$ possibilities. 

I think this process is essentially the same as what is sometimes called Banach's Matchbox Problem.
A: This answer is based upon the Lagrange inversion formula. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance
\begin{align*}
[z^n]\frac{1}{1-2z}=[z^n]\sum_{j=0}^\infty 2^jz^j=2^n
\end{align*}

We obtain
  \begin{align*}
\color{blue}{\sum_{k=0}^n2^{-k}\binom{n+k}{k}}
&=\sum_{k=0}^n\binom{-n-1}{k}\left(-\frac{1}{2}\right)^k\tag{1}\\
&=[z^n]\frac{1}{\left(1-\frac{z}{2}\right)^{n+1}(1-z)}\tag{2}\\
&=[z^n]\left.\left(\frac{1}{\left(1-\frac{w}{2}\right)(1-w)}\cdot\frac{1}{1-\frac{w}{2}\cdot\frac{1}{1-\frac{w}{2}}}\right)\right|_{w=\frac{z}{1-\frac{w}{2}}}\tag{3}\\
&=[z^n]\left.\frac{1}{(1-w)^2}\right|_{w=1-\sqrt{1-2z}}\tag{4}\\
&=[z^n]\frac{1}{1-2z}\\
&\color{blue}{=2^n}
\end{align*}

Comment:


*

*In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ and $\binom{p}{q}=\binom{p}{p-q}$.

*In (2) we observe the sum is the coefficient of the convolution of two series
\begin{align*}
[z^n]\left(\sum_{k}a_kz^k\right)\left(\sum_{l}b_lz^l\right)=[z^n]\sum_{N}\left(\sum_{k=0}^Na_k b_{N-k}\right)z^N
=\sum_{k=0}^na_k b_{n-k}
\end{align*}
Here with $a_k=\binom{-n-1}{k}\left(-\frac{1}{2}\right)^k$ and $b_k=1$.

*In (3) we use the Lagrange Inversion Formula in the form G6 stated in R. Sprugnolis (etal) paper Lagrange Inversion: when and how. 
\begin{align*}
[z^n]F(z)\Phi(z)^n=[z^n]\left.\frac{F(w)}{1-z\Phi'(w)}\right|_{w=z\Phi(w)}
\end{align*}
Here with $\Phi(z)=\frac{1}{1-\frac{z}{2}}$ and $F(z)=\frac{1}{\left(1-\frac{z}{2}\right)(1-z)}$. It follows since $w=z\Phi(w)$:
\begin{align*}
z\Phi^{\prime}(w)=\frac{z}{2}\cdot\frac{1}{\left(1-\frac{w}{2}\right)^2}
=\frac{z}{2}\Phi^2(w)=\frac{w}{2}\Phi(w)=\frac{w}{2}\cdot\frac{1}{1-\frac{w}{2}}
\end{align*}


*

*In (4) we simplify the expression and we select the solution $w=w(z)$ from $w=\frac{z}{1-\frac{w}{2}}$ which can be expanded in a power series.

