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

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.}$$
