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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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