6
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ You can also solve problem 7 in that section and get this one as corollary. $\endgroup$
    – user121880
    May 2, 2014 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, 2014 at 8:20

3 Answers 3

7
$\begingroup$

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}$.

$\endgroup$
1
  • 1
    $\begingroup$ I like this answer. Thank you for the response. $\endgroup$
    – Pavelshu
    May 2, 2014 at 8:14
1
$\begingroup$

$\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}

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

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

enter image description here

$\endgroup$

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.