How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $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.
Best Answer
A proof by induction is possible, if a bit messy. For $n\in\Bbb N$ let $$s_n=\sum_{k=0}^n\binom{n+k}k\frac1{2^k}\;.$$ Clearly $s_0=1=2^0$. Suppose that $s_n=2^n$ for some $n\in\Bbb N$. Then
$$\begin{align*} s_{n+1}&=\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=1}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+s_n+\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^{k+1}}\\\\ &=s_n+\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\left(\binom{2n+1}{n+1}+\binom{2n+1}n\right)\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\binom{2n+1}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &\overset{(*)}=2^n+\frac12\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12s_{n+1}\;, \end{align*}$$
where the step $(*)$ follows from the fact that
$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n=2\binom{2n+1}{n+1}\;.$$
Thus, $\frac12s_{n+1}=2^n$, and $s_{n+1}=2^{n+1}$, as desired.
Added: I just came up with a combinatorial argument as well. Flip a fair coin until either $n+1$ heads or $n+1$ tails have appeared. Let $k$ be the number of times the other face of the coin has appeared; clearly $0\le k\le n$. The last flip must result in the $(n+1)$-st instance of the majority face, but the other $n$ instances of that face and $k$ of the other can appear in any order.
Now imagine that after achieving the desired outcome we continue to flip the coin until we’ve flipped it $2n+1$ times. There are altogether
$$\binom{n+k}k2^{(2n+1)-(n+k)}=\binom{n+k}k2^{n+1-k}$$
sequences of $2n+1$ flips that decide the outcome at the $(n+k+1)$-st toss, so
$$\sum_{k=0}^n\binom{n+k}k2^{n+1-k}=2^{2n+1}\;,$$
and
$$\sum_{k=0}^n\binom{n+k}k\frac1{2^k}=2^n\;.$$