combinatorics - How to show $sum_{k=0}^{n}binom{n+k}{k}frac{1}{2^k}=2^{n}$

How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}?$$ I tried using the Snake oil technique but I guess I am applying it incorrectly. With the snake oil technique we have $$F(x)= \sum_{n=0}^{\infty}\left\{\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}\right\}x^{n}.$$ I think I have to interchage the summation and do something. But I am not quite comfortable in interchanging the summation. Like after interchaging the summation will $$F(x)=\sum_{k=0}^{n}\sum_{n=0}^{\infty}\binom{n+k}{k}\frac{1}{2^k}x^{n}?$$ Even if I continue with this I am unable to get the correct answer.

• How does one prove this using the Snake oil technique?




• A combinatorial proof is also welcome, as are other kinds of proofs.

Answer

Let $S_n:=\sum\limits_{k=0}^n\,\binom{n+k}{k}\,\frac{1}{2^k}$ for every $n=0,1,2,\ldots$. Then, $$S_{n+1}=\sum_{k=0}^{n+1}\,\binom{(n+1)+k}{k}\,\frac{1}{2^k}=\sum_{k=0}^{n+1}\,\Biggl(\binom{n+k}{k}+\binom{n+k}{k-1}\Biggr)\,\frac{1}{2^k}\,.$$
Hence,

$$S_{n+1}=\left(S_n+\binom{2n+1}{n+1}\frac{1}{2^{n+1}}\right)+\sum_{k=0}^n\,\binom{(n+1)+k}{k}\,\frac{1}{2^{k+1}}\,.$$
That is,
$$S_{n+1}=S_n+\frac{S_{n+1}}{2}+\frac{1}{2^{n+2}}\,\Biggl(2\,\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\Biggr)\,.$$
As $$\binom{2n+2}{n+1}=\frac{2n+2}{n+1}\,\binom{2n+1}{n}=2\,\binom{2n+1}{n+1}\,,$$
we deduce that $S_{n+1}=S_n+\frac{S_{n+1}}{2}$, or
$$S_{n+1}=2\,S_{n}$$
for all $n=0,1,2,\ldots$. Because $S_0=1$, the claim follows.

---

Combinatorial Argument

The number of binary strings of length $2n+1$ with at least $n+1$ ones is clearly $2^{2n}$. For $k=0,1,2,\ldots,n$, the number of such strings whose $(n+1)$-st one is at the $(n+k+1)$-st position is $\binom{n+k}{k}\,2^{n-k}$. The claim is now evident.