<s>[INST] 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
 [/INST] 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}
$$
</s>