How to show $\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$

Question

How does one show that $$\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}=2^{n}$$ for each nonnegative integer $n$?

I tried using the Snake oil technique but I guess I am applying it incorrectly. With the snake oil technique we have $$F(x)= \sum_{n=0}^{\infty}\left\{\sum_{k=0}^{n}\binom{n+k}{k}\frac{1}{2^k}\right\}x^{n}.$$ I think I have to interchage the summation and do something. But I am not quite comfortable in interchanging the summation. Like after interchaging the summation will $$F(x)=\sum_{k=0}^{n}\sum_{n=0}^{\infty}\binom{n+k}{k}\frac{1}{2^k}x^{n}?$$ Even if I continue with this I am unable to get the correct answer.

• How does one prove this using the Snake oil technique?

• A combinatorial proof is also welcome, as are other kinds of proofs.

Answer 1

Let $S_n:=\sum\limits_{k=0}^n\,\binom{n+k}{k}\,\frac{1}{2^k}$ for every $n=0,1,2,\ldots$. Then, $$S_{n+1}=\sum_{k=0}^{n+1}\,\binom{(n+1)+k}{k}\,\frac{1}{2^k}=\sum_{k=0}^{n+1}\,\Biggl(\binom{n+k}{k}+\binom{n+k}{k-1}\Biggr)\,\frac{1}{2^k}\,.$$ Hence, $$S_{n+1}=\left(S_n+\binom{2n+1}{n+1}\frac{1}{2^{n+1}}\right)+\sum_{k=0}^n\,\binom{(n+1)+k}{k}\,\frac{1}{2^{k+1}}\,.$$ That is, $$S_{n+1}=S_n+\frac{S_{n+1}}{2}+\frac{1}{2^{n+2}}\,\Biggl(2\,\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\Biggr)\,.$$ As $$\binom{2n+2}{n+1}=\frac{2n+2}{n+1}\,\binom{2n+1}{n}=2\,\binom{2n+1}{n+1}\,,$$ we deduce that $S_{n+1}=S_n+\frac{S_{n+1}}{2}$, or $$S_{n+1}=2\,S_{n}$$ for all $n=0,1,2,\ldots$. Because $S_0=1$, the claim follows.

---

Combinatorial Argument

The number of binary strings of length $2n+1$ with at least $n+1$ ones is clearly $2^{2n}$. For $k=0,1,2,\ldots,n$, the number of such strings whose $(n+1)$-st one is at the $(n+k+1)$-st position is $\binom{n+k}{k}\,2^{n-k}$. The claim is now evident.

Answer 2

Here is a variation based upon the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series. We can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \sum_{k=0}^n\binom{n+k}{k}\frac{1}{2^k}&=\sum_{k=0}^n[x^k](1+x)^{n+k}\frac{1}{2^k}\tag{1}\\ &=[x^0](1+x)^n\sum_{k=0}^n\left(\frac{1+x}{2x}\right)^k\tag{2}\\ &=[x^0](1+x)^n\frac{1-\left(\frac{1+x}{2x}\right)^{n+1}}{1-\frac{1+x}{2x}}\tag{3}\\ &=[x^0](1+x)^n\frac{1}{(2x)^n}\frac{(2x)^{n+1}-(1+x)^{n+1}}{x-1}\tag{4}\\ &=\frac{1}{2^n}[x^n]\frac{(1+x)^{2n+1}}{1-x}\tag{5}\\ &=\frac{1}{2^n}[x^n]\sum_{k=0}^{2n+1}\binom{2n+1}{k}x^k\frac{1}{1-x}\tag{6}\\ &=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}[x^{n-k}]\frac{1}{1-x}\tag{7}\\ &=\frac{1}{2^n}\sum_{k=0}^{n}\binom{2n+1}{k}\tag{8}\\ &=\frac{1}{2^n}\cdot\frac{1}{2}2^{2n+1}\tag{9}\\ &=2^n \end{align*} and the claim follows.

Comment:

• In (1) we apply the coefficient of operator.

• In (2) we use the linearity of the coefficient of operator and the rule $$[x^{p+q}]A(x)=[x^p]x^{-q}A(x)$$

• In (3) we use the finite geometric series formula.

• In (4) we do some simplifications.

• In (5) we use again the rule stated in comment (2) and note that the term $(2x)^{n+1}$ can be ignored, since it does not contribute to the coefficient of $x^n$.

• In (6) we apply the binomial sum formula.

• In (7) we note that only index up to $k=n$ contributes to the coefficient of $x^n$.

• In (8) we recall the geometric series is $$\frac{1}{1-x}=1+x+x^2+\cdots$$ so that the contribution to the coefficient is always $1$.

• In (9) we use the symmetry of the binomial sum formula.

Answer 3

Suppose we seek to verify that

$$\sum_{k=0}^n {n+k\choose k} \frac{1}{2^k} = 2^n.$$

In the following we make an effort to use a different set of integrals from the answer by @MarkusScheuer, for variety's sake, even if this is not the simplest answer.

The difficulty here lies in the fact that the binomial coefficients on the LHS do not have an upper bound for the sum wired into them. We use an Iverson bracket to get around this:

$$[[0\le k\le n]] = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{w^k}{w^{n+1}} \frac{1}{1-w} \; dw.$$

Introduce furthermore

$${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{(1-z)^{k+1}} \; dz.$$

With the Iverson bracket in place we can let the sum range to infinity, getting

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \sum_{k\ge 0} \frac{w^k}{(1-z)^k} \frac{1}{2^k} \; dz\; dw.$$

This converges when $|w| < |2(1-z)|.$ We require $\gamma \lt 2(1-\epsilon)$ or $\epsilon \lt 1-\gamma/2.$ Simplifying we have

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \frac{1}{1-w/(1-z)/2} \; dz\; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z-w/2} \; dz\; dw.$$

The pole at $z=1-w/2$ is outside the contour due to the requirements on convergence, so we may use the negative of the residue there, getting

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \frac{1}{(1-w/2)^{n+1}} \; dw.$$

This could have been obtained by inspection, bypassing the Iverson bracket. Now put $w (1-w/2) = v$ so that $w = 1-\sqrt{1-2v}$ (this branch maps $w=0$ to $v=0$) to get (here we have $v=w-\cdots$ so the image of $|w|=\gamma$ makes one turn around the origin and may be deformed to a circle $|v|=\gamma'$)

$$\frac{1}{2\pi i} \int_{|v|=\gamma'} \frac{1}{v^{n+1}} \frac{1}{\sqrt{1-2v}} \frac{1}{\sqrt{1-2v}} \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\gamma'} \frac{1}{v^{n+1}} \frac{1}{1-2v} \; dv = 2^n.$$

This is the claim. Note that we may take $\gamma' \lt \gamma - \frac{1}{2} \gamma^2.$

Observe that

$$\mathrm{Res}_{z=\infty} \frac{1}{z^{n+1}} \frac{1}{1-z-w/2} = - \mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+1} \frac{1}{1-w/2-1/z} \\ = - \mathrm{Res}_{z=0} z^{n} \frac{1}{z(1-w/2)-1} = 0.$$

This was an interesting exercise showing how the choice of contour for convergence influences the computation. The branch of $\sqrt{1-2v}$ that was used has the branch cut on $[1/2, \infty).$

Answer 4

$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mrm}[1]{\,\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \mrm{f}_{n}\pars{x} & \equiv \sum_{k = 0}^{n}{n + k \choose k}x^{k} = \color{#f00}{{1 \over n!}\sum_{k = 0}^{n}{\pars{n + k}! \over k!}x^{k}} = \pars{n + 1} + {1 \over n!}\sum_{k = 1}^{n} {n + k \over k}{\pars{n + k - 1}! \over \pars{k - 1}!}x^{k} \\[5mm] & = n + 1 + {1 \over n!}\sum_{k = 0}^{n - 1} {n + k + 1 \over k + 1}{\pars{n + k}! \over k!}x^{k + 1} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + {n \over n!}\,x\sum_{k = 0}^{n} {1 \over k + 1}{\pars{n + k}! \over k!}x^{k} + x\color{#f00}{{1 \over n!}\sum_{k = 0}^{n} {\pars{n + k}! \over k!}x^{k}} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + {n \over n!}\,x\sum_{k = 0}^{n}x^{k} {\pars{n + k}! \over k!}\int_{0}^{1}y^{k}\,\dd y + x\mrm{f}_{n}\pars{x} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + nx\int_{0}^{1}\color{#f00}{{1 \over n!}\sum_{k = 0}^{n} {\pars{n + k}! \over k!}\pars{xy}^{k}}\,\dd y + x\mrm{f}_{n}\pars{x} \\[5mm] & = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + n\int_{0}^{1}\mrm{f}_{n}\pars{xy}\,x\,\dd y + x\mrm{f}_{n}\pars{x} \end{align}

---

$$ \imp\quad \begin{array}{|c|}\hline\mbox{}\\ \ds{\quad\mrm{f}_{n}\pars{x} = 1 - {2n + 1 \over n + 1}{2n \choose n}x^{n + 1} + n\int_{0}^{x}\mrm{f}_{n}\pars{y}\,\dd y + x\mrm{f}_{n}\pars{x} \quad} \\ \mbox{}\\ \hline \end{array} $$

---

Then, \begin{align} \mrm{f}_{n}'\pars{x} & = -\pars{2n + 1}{2n \choose n}x^{n} + n\mrm{f}_{n}\pars{x} + \mrm{f}_{n}\pars{x} + x\mrm{f}_{n}'\pars{x} \,,\quad\mrm{f}_{n}\pars{0} = 1 \end{align}

---

$$ \mrm{f}_{n}'\pars{x} - {n + 1 \over 1 - x}\,\mrm{f}_{n}\pars{x} = -\pars{2n + 1}{2n \choose n}{x^{n} \over 1 - x} $$

---

$$ \totald{\bracks{\pars{1 - x}^{n + 1}\mrm{f}_{n}\pars{x}}}{x} = -\pars{2n + 1}{2n \choose n}x^{n}\pars{1 - x}^{n} $$

---

$$ 2^{-n - 1}\,\,\mrm{f}_{n}\pars{\half} - 1 = -\pars{2n + 1}{2n \choose n}\int_{0}^{1/2}x^{n}\pars{1 - x}^{n}\,\dd x $$

---

\begin{align} \color{#f00}{\sum_{k = 0}^{n}{n + k \choose k}x^{k}} & = \mrm{f}_{n}\pars{\half} = 2^{n + 1}\ -\ \overbrace{% 2^{n + 1}\pars{2n + 1}{2n \choose n} \int_{0}^{1/2}\bracks{{1 \over 4} - \pars{x - \half}^{2}}^{n}\,\dd x} ^{\ds{2^{n}}} \\[5mm] & = \color{#f00}{2^{n}} \end{align}

Note that $$ \int_{0}^{1/2}\bracks{{1 \over 4} - \pars{x - \half}^{2}}^{n}\,\dd x = \half\,\ \overbrace{{\Gamma\pars{n + 1}\Gamma\pars{n + 1} \over \Gamma\pars{2n + 2}}} ^{\ds{\mrm{B}\pars{n + 1,n + 1}}}\ =\ {1 \over 2\pars{2n + 1}{2n \choose n}} $$ $\ds{\Gamma}$: Gamma Function. B: Beta Function.

Answer 5

Binomial coefficient is just $\binom{-(n-1)}{k} = (-1)^k \binom{n+k}{k}$ and take $x= -\frac{1}{2}$so you get $\sum_{k=0}^{\infty} \binom{-(n-1)}{k} x^k = \frac{1}{(1-x)^{n-1}}$

Answer 6

A proof by induction is possible, if a bit messy. For $n\in\Bbb N$ let $$s_n=\sum_{k=0}^n\binom{n+k}k\frac1{2^k}\;.$$ Clearly $s_0=1=2^0$. Suppose that $s_n=2^n$ for some $n\in\Bbb N$. Then

$$\begin{align*} s_{n+1}&=\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=1}^n\binom{n+k}{k-1}\frac1{2^k}\\\\ &=\binom{2n+2}{n+1}\frac1{2^{n+1}}+s_n+\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^{k+1}}\\\\ &=s_n+\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\left(\binom{2n+1}{n+1}+\binom{2n+1}n\right)\frac1{2^{n+1}}+\frac12\sum_{k=0}^{n-1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\binom{2n+1}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &\overset{(*)}=2^n+\frac12\binom{2n+2}{n+1}\frac1{2^{n+1}}+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12\sum_{k=0}^{n+1}\binom{n+1+k}k\frac1{2^k}\\\\ &=2^n+\frac12s_{n+1}\;, \end{align*}$$

where the step $(*)$ follows from the fact that

$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n=2\binom{2n+1}{n+1}\;.$$

Thus, $\frac12s_{n+1}=2^n$, and $s_{n+1}=2^{n+1}$, as desired.

Added: I just came up with a combinatorial argument as well. Flip a fair coin until either $n+1$ heads or $n+1$ tails have appeared. Let $k$ be the number of times the other face of the coin has appeared; clearly $0\le k\le n$. The last flip must result in the $(n+1)$-st instance of the majority face, but the other $n$ instances of that face and $k$ of the other can appear in any order.

Now imagine that after achieving the desired outcome we continue to flip the coin until we’ve flipped it $2n+1$ times. There are altogether

$$\binom{n+k}k2^{(2n+1)-(n+k)}=\binom{n+k}k2^{n+1-k}$$

sequences of $2n+1$ flips that decide the outcome at the $(n+k+1)$-st toss, so

$$\sum_{k=0}^n\binom{n+k}k2^{n+1-k}=2^{2n+1}\;,$$

and

$$\sum_{k=0}^n\binom{n+k}k\frac1{2^k}=2^n\;.$$

Answer 7

This one can also be done using complex variables.

Suppose we seek to show that $$\sum_{k=0}^{n} {n+k \choose k} \frac{1}{2^k} = 2^n.$$ Introduce the integral repesentation $${n+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz.$$

This gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \sum_{k=0}^n \frac{(1+z)^k}{(2z)^k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} \frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)/(2z)-1} \; dz \\ = \frac{2}{2\pi i} \int_{|z|=\epsilon} (1+z)^n \frac{(1+z)^{n+1}/(2z)^{n+1}-1}{(1+z)-2z} \; dz \\ = \frac{2}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{1-z} \left((1+z)^{n+1}/(2z)^{n+1}-1\right) \; dz.$$

The second component makes no contribution inside the contour, leaving just $$\frac{2^{-n}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{(1+z)^{2n+1}}{1-z} \; dz.$$ Extracting coefficients we get $$2^{-n} [z^n] \frac{(1+z)^{2n+1}}{1-z} = 2^{-n} \sum_{q=0}^n {2n+1\choose q} = 2^{-n}\times \frac{1}{2} \times 2^{2n+1} = 2^n.$$

Answer 8

Since $$ \binom{2n-1}{n}+\binom{2n-1}{n-1}=\binom{2n}{n}\quad\text{and}\quad\binom{2n-1}{n}=\binom{2n-1}{n-1}\tag{1} $$ we have $$ \binom{2n-1}{n}=\frac12\binom{2n}{n}\tag{2} $$ Therefore, if we define $$ \begin{align} A_n &=\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}\tag{3a}\\ &=\sum_{k=0}^n\left[\binom{n+k-1}{k}+\binom{n+k-1}{k-1}\right]\frac1{2^k}\tag{3b}\\ &=\sum_{k=0}^n\binom{n+k-1}{k}\frac1{2^k}\\ &+\sum_{k=0}^{n-1}\binom{n+k}{k}\frac1{2^{k+1}}\tag{3c}\\ &=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\binom{2n-1}{n}\frac1{2^n}\\ &+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}-\binom{2n}{n}\frac1{2^{n+1}}\tag{3d}\\ &=\sum_{k=0}^{n-1}\binom{n+k-1}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k}\frac1{2^{k+1}}\tag{3e}\\ &=A_{n-1}+\frac12A_n\tag{3f} \end{align} $$ Explanation:
$\text{(3a)}$: define $A_n$
$\text{(3b)}$: use Pascal's Triangle
$\text{(3c)}$: substitute $k\mapsto k+1$ in the second sum
$\text{(3d)}$: add and subtract the last term in each sum
$\text{(3e)}$: use $(2)$ to cancel the terms separated in $\text{(3d)}$
$\text{(3f)}$: use the definition of $A_n$

Thus, $\text{(3f)}$ implies that $$ A_n=2A_{n-1}\tag{4} $$ Since $A_0=1$, we get that $$ \bbox[5px,border:2px solid #C0A000]{A_n=2^n}\tag{5} $$

---

Possibly Interesting Observation

The sum becomes easier if we sum to infinity: $$ \begin{align} \sum_{k=0}^\infty\binom{n+k}{k}\frac1{2^k} &=\sum_{k=0}^\infty(-1)^k\binom{-n-1}{k}\frac1{2^k}\tag{6a}\\ &=\left(1-\frac12\right)^{-n-1}\tag{6b}\\[9pt] &=2^{n+1}\tag{6c} \end{align} $$ Explanation:
$\text{(6a):}$ negative binomial coefficient
$\text{(6b):}$ Binomial Theorem
$\text{(6c):}$ evaluate

So exactly half the infinite sum is contained in the first $n+1$ terms.

Answer 9

The required equality can be written as $$\sum_{k=0}^n \binom{n+k}{k} 2^{n-k} = 2^{2n}$$

Now, we have $$\sum\binom{n+k}{k} x^k = \frac{1}{(1-x)^{n+1}}$$

Therefore, our sum equals the coefficient of $x^n$ in the product $$[x^n]\frac{1}{(1-x)^{n+1}(1-2 x)}= [x^{-1}]\cdot \frac{1}{(1-2x)(x(1-x))^{n+1}} $$ Equivalently, we have to show that the residue at $x=0$ of $$\frac{2}{1-x} \cdot \left(\frac{1}{x(2-x)}\right)^{n+1} $$ is $1$, for all $n\ge 0$ (example with WA).

Now, let's recall the Lagrange–Bürmann formula. Consider $f(x)$ an analytic function $f(0) = 0$, $f'(0) \ne 0$, with inverse $g(x)$, $H$ an analytic function. Then we have
$$\operatorname{Res}_{x=0}\ H'(x) \cdot \frac{1}{f^n(x)}= n[x^n] H(g(x))$$ for all $n\ge 1$.

Now, $f(x) = x(2-x)$, with inverse $g(x) = 1 - \sqrt{1-x}$, $H'(x) = \frac{2}{1-x}$, $H(x) = \log\frac{1}{(1-x)^2}$. Now, $$H(g(x)) = \log\frac{1}{(1-(1-\sqrt{1-x}))^2}= \log\frac{1}{1-x}= \sum_{n\ge 1} \frac{x^n}{n}$$ We are done.