Proving this binomial identity $\sum_{k=0}^n {n+k \choose k} \frac{1}{2^{k}}= 2^{n}$ [duplicate]

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.

Solution 1:

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\;.$$

Solution 2:

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.

Solution 3:

Here is a variation based upon the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series. We can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \sum_{k=0}^n\binom{n+k}{k}\frac{1}{2^k}&=\sum_{k=0}^n[x^k](1+x)^{n+k}\frac{1}{2^k}\tag{1}\\ &=[x^0](1+x)^n\sum_{k=0}^n\left(\frac{1+x}{2x}\right)^k\tag{2}\\ &=[x^0](1+x)^n\frac{1-\left(\frac{1+x}{2x}\right)^{n+1}}{1-\frac{1+x}{2x}}\tag{3}\\ &=[x^0](1+x)^n\frac{1}{(2x)^n}\frac{(2x)^{n+1}-(1+x)^{n+1}}{x-1}\tag{4}\\ &=\frac{1}{2^n}[x^n]\frac{(1+x)^{2n+1}}{1-x}\tag{5}\\ &=\frac{1}{2^n}[x^n]\sum_{k=0}^{2n+1}\binom{2n+1}{k}x^k\frac{1}{1-x}\tag{6}\\ &=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}[x^{n-k}]\frac{1}{1-x}\tag{7}\\ &=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}\tag{8}\\ &=\frac{1}{2^n}\cdot\frac{1}{2}2^{2n+1}\tag{9}\\ &=2^n \end{align*} and the claim follows.

Comment:

• In (1) we apply the coefficient of operator.

• In (2) we use the linearity of the coefficient of operator and the rule $$[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$$

• In (3) we use the finite geometric series formula.

• In (4) we do some simplifications.

• In (5) we use again the rule stated in comment (2) and note that the term $(2x)^{n+1}$ can be ignored, since it does not contribute to the coefficient of $x^n$.

• In (6) we apply the binomial sum formula.

• In (7) we note that only index up to $k=n$ contributes to the coefficient of $x^n$.

• In (8) we recall the geometric series is $$\frac{1}{1-x}=1+x+x^2+\cdots$$ so that the contribution to the coefficient is always $1$.

• In (9) we use the symmetry of the binomial sum formula.