# 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.
– user121880
May 2, 2014 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. May 2, 2014 at 8:20

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. May 2, 2014 at 8:14

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum_{k = 0}^{\infty}{n+k \choose k}2^{-k} = 2^{n+1}:\ {\large ?}}$

\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. Sep 6, 2014 at 8:10
• @hypergeometric I'll check your new question tomorrow because it's too late over here. Thanks. Sep 6, 2014 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. Sep 6, 2014 at 19:46
• Thanks, @Felix_Marin. That was very helpful. Sep 7, 2014 at 9:11

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

Let $$F(n,k)=\sum_{k=0}^{\infty}\binom{n+k}{k}2^{-k}=2^{n+1}$$ Assume result is true for $$n=m$$, i.e. $$F(m,k)=\sum_{k=0}^{\infty}\binom{m+k}{k}2^{-k}=2^{m+1}$$ For $$n=m+1$$, \begin{align} F(m+1,k) &=\sum_{k=0}^{\infty}\binom{m+1+k}{k}2^{-k}\\ &=1+\sum_{k=1}^{\infty}\binom{m+1+k}{k}2^{-k}\\ &=1+\sum_{k=1}^{\infty}\left[\binom{m+k}{k}+\binom{m+k}{k-1}\right]2^{-k}\\ &=1+\sum_{k=1}^{\infty}\binom{m+k}{k}2^{-k}+\sum_{k=0}^{\infty}\binom{m+k+1}{k}2^{-(k+1)}\\ &=\sum_{k=0}^{\infty}\binom{m+k}{k}2^{-k}+\frac{1}{2}\sum_{k=0}^{\infty}\binom{m+k+1}{k}2^{-k}\\ &=F(m,k)+\frac{1}{2}F(m+1,k)\\ &=2^{m+1}+\frac{1}{2}F(m+1,k)\\ \frac{1}{2}F(m+1,k)&=2^{m+1}\\ F(m+1,k)&=2\cdot 2^{m+1}=2^{m+2}=2^{\overline{m+1}+1} \end{align} i.e. also true for $$n=m+1$$.

For $$n=0$$, $$\text{LHS}=\sum_{k=0}^{\infty}\binom{k}{k}2^{-k}=\sum_{k=0}^{\infty}\frac{1}{2^k}=\frac{1}{1-\frac{1}{2}}=2=\text{RHS}$$ i.e. true for $$n=0$$.

Hence, by induction, $$F(n,k)=2^{n+1}$$ is true for all integers $$n\geq 0$$.

(see the original image)