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*}

  • 2
    $\begingroup$ You can also solve problem 7 in that section and get this one as corollary. $\endgroup$ – Zircht May 2 '14 at 8:16
  • $\begingroup$ 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. $\endgroup$ – Pavelshu May 2 '14 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}$.

  • 1
    $\begingroup$ I like this answer. Thank you for the response. $\endgroup$ – Pavelshu May 2 '14 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}

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

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

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.