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

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.

