# Help with a Binomial Identity: $\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = 2^{n+1}$

The following is a problem from the 5th edition of Niven's An Introduction to the Theory of Numbers:

Problem 23 of Section 1.4 asks us to prove that

$$\sum_{k=0}^{\infty} \binom{n+k}{k}2^{-k} = 2^{n+1}.$$

I believe I proved it using generating functions, but I would love to have my proof verified and if possible, could someone provide a hint to an alternative proof of the fact. Generating functions have not been covered in this section yet, so I would prefer to figure out how to prove this identity with slightly less powerful tools (if that makes sense).

PROOF The right hand side is the coefficient $[x^n]$ of the generating function $$\frac{2}{1-2x}.$$

On the left hand side, we have that the corresponding generating function of the sequence is \begin{align*} \sum_{k=0}^{\infty}\sum_{n=0}^{\infty}\binom{k+n}{n}\frac{1}{2^k}x^n &= \sum_{k=0}^{\infty}\frac{1}{2^k}\sum_{n=0}^{\infty}\binom{n+k}{n}x^n\\ &=\sum_{k=0}^{\infty}\frac{1}{2^k}\frac{1}{(1-x)^{k+1}}\\ &= \frac{1}{1-x}\sum_{k=0}^{\infty}\frac{1}{(2-2x)^k}\\ &= \frac{1}{1-x}\frac{1}{1-\frac{1}{2-2x}}\\ &=\frac{2}{1-2x} = RHS \end{align*}

• You can also solve problem 7 in that section and get this one as corollary. – Zircht May 2 '14 at 8:16
• I did use problem 7 (at least "formally") when working with the generating function of $\left\{\binom{n+k}{n}\right\}_{n}$. Oh, I think I see what you mean. Evaluating $z=\frac{1}{2}$ and $\alpha=n$. Very clever, thank you. – Pavelshu May 2 '14 at 8:20

## 3 Answers

An alternative proof is to use a simple induction on $n$. You have

$$x = \sum_{k=0}^\infty \binom{n+1+k}{k}2^{-k}=1+\sum_{k=1}^\infty\binom{n+1+k}{k}2^{-k}=1+\sum_{k=1}^\infty \binom{n+k}{k}2^{-k}+\sum_{k=0}^\infty \binom{n+k+1}{k}2^{-k-1}=\sum_{k=0}^\infty\binom{n+k}{k}2^{-k}+\frac{x}{2}$$

so that applying the IH and solving leads to

$x=2\cdot 2^{n+1}=2^{n+2}$.

• I like this answer. Thank you for the response. – Pavelshu May 2 '14 at 8:14


\begin{align}&\color{#66f}{\large\sum_{k = 0}^{\infty}{n+k \choose k}2^{-k}} =\sum_{k = 0}^{\infty}\pars{-1}^{k}{-n - 1 \choose k}2^{-k} =\sum_{k = 0}^{\infty}{-n - 1 \choose k}\pars{-\,\half}^{k} \\[3mm]&=\bracks{1 + \pars{-\,\half}}^{-n - 1}=\pars{\half}^{-n - 1} =\color{#66f}{\Large 2^{n + 1}} \end{align}

• Nice answer. Very clever use of Upper Negation. Would you be able to use this method (or a variant of it) if the summation is taken only to $n$ instead of $\infty$? The result is $2^n$ instead of $2^{n+1}$. Thought that problem has been posted on MSE before but could not locate it. – hypergeometric Sep 6 '14 at 8:10
• @hypergeometric I'll check your new question tomorrow because it's too late over here. Thanks. – Felix Marin Sep 6 '14 at 9:01
• @hypergeometric I remembered I already solved over here. The above 'trick' doesn't work in that case because we need to keep the $k$ variable unchanged in ${\cdots \choose k}$ in order to rebuild the Newton binomial. You can write $$\sum_{k = 0}^{n}{n + k \choose k}2^{-k} = \sum_{k = 0}^{\infty}{n + k \choose k}2^{-k} -2^{-n - 1} \sum_{k = 0}^{\infty}{2n + k + 1 \choose k + n + 1}2^{-k}$$ You can see that the lower index in the second term combinatoric is not $k$ anymore. Thanks. – Felix Marin Sep 6 '14 at 19:46
• Thanks, @Felix_Marin. That was very helpful. – hypergeometric Sep 7 '14 at 9:11

This is the same proof provided by @mathse above, expanded for more detail.