Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

Question

I just found this identity but without any proof, could you just give me an hint how I could prove it? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$

I know that $$2^n = \sum\limits_{k=0}^n \binom{n}{k}$$ but that didn't help me

Answer 1

You can prove it by induction on $n$. Here’s a start. Let

$$f(n)=\sum_{k=0}^n2^{-k}\binom{n+k}k\;;$$

clearly $f(0)=1=2^0$. Assume that $f(n)=2^n$ for some $n\ge 0$. Then

$$\begin{align*} f(n+1)&=\sum_{k=0}^{n+1}2^{-k}\binom{n+1+k}k\\ &=\sum_{k=0}^{n+1}2^{-k}\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\\ &=\sum_{k=0}^{n+1}2^{-k}\binom{n+k}k+\sum_{k=1}^{n+1}2^{-k}\binom{n+k}{k-1}\\ &=2^{-(n+1)}\binom{2n+1}{n+1}+\sum_{k=0}^n2^{-k}\binom{n+k}k+\sum_{k=0}^n2^{-(k+1)}\binom{n+1+k}k\\ &=2^{-(n+1)}\binom{2n+1}{n+1}+2^n+\frac12\sum_{k=0}^n2^{-k}\binom{n+1+k}k\;, \end{align*}$$

and

$$f(n+1)=2^{-(n+1)}\binom{2n+2}{n+1}+\sum_{k=0}^n2^{-k}\binom{n+1+k}k\;.$$

Now combine these results and use the fact that

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

to complete the induction step.

Answer 2

Let's do this in lazy, stream of consciousness fashion, adjusting little details one by one until it looks like a recognizable enumeration.

First combinatorialize it by multiplying the whole thing by $2^n$, to

$$2^{2n} = \sum\limits_{k=0}^n 2^{n-k} \cdot \binom{n+k}{k}$$

This looks better, because $(n-k)$ and $(n+k)$ look like a decomposition of $2n$. The left side counts all subsets of a $2n$ element set, so maybe something about the larger and the smaller subset in the partition of $2n$ elements into a subset and its complement. Some fuzzy feeling about needing to break the symmetry when the sets are of equal size tells to multiply by $2$ and consider subsets of a $2n+1$ element set, which as a partition of the set has a larger and a smaller part. So,

$$2^{2n+1} = \sum\limits_{k=0}^n 2 \times 2^{n-k} \cdot \binom{n+k}{k}$$ or

$$2^{2n+1} = \sum\limits_{k=0}^n 2 \times 2^{n-k} \cdot \binom{n+k}{n}$$

Better! A subset of a size $2n+1$ set is equivalent to a partition into (larger set with more than $n$ elements) $\cup$ (smaller set with less than $n$ elements), and a choice (the $\times 2$) of which one is the subset. And we can pick the larger subset by first selecting its largest $n+1$ elements, then adding some random subset from the lower indexed elements (this is the $2^{n-k}$), and... ok, it is all clear now:

From the first $2n+1$ integers, select a subset by partitioning into a large and a small subset and picking ($\times 2$) one of them as the set. Determine the large subset, which has at least $n+1$ elements, by selecting an index $j$ from $1$ to $n+1$ as the location of the $(n+1)$th-largest element of the set, selecting the $n$ elements above $j$ (there are ${2n+1 - j} \choose {n}$ options) and adding any subset of the elements below $j$ (there are $2^{j-1}$ of those). This is the last sum with $k = n+1 - j$.

In the opposite direction, divide by $2^n$ to get

$$1 = \sum\limits_{k=0}^n 2^{-(n+k)} \cdot \binom{n+k}{n}$$

and look for a natural probability process that delivers this distribution. One answer:

Throw a coin to determine whether voters $1, 2, \ldots$ are supporting candidate $A$ or $B$ in an election, and stop the process when one candidate reaches $n+1$ votes. Stopping happens at a time $t$ between $n+1$ and $2n+1$ steps, and if $k=t-1-n$, the set of times at which the victorious candidate received votes before time $t$ is one of ${{t-1} \choose n} = {{n+k} \choose n}$ possibilities.

I think this process is essentially the same as what is sometimes called Banach's Matchbox Problem.

Answer 3

I tried to generalize, but equation $(2)$ shows why $x=\frac12$ is needed to make a simple equation.

Note that $$ \begin{align} \sum_{k=0}^{n+1}x^k\binom{n+k+1}{k} &=\sum_{k=0}^{n+1}x^k\left[\binom{n+k}{k}+\binom{n+k}{k-1}\right]\\ &=\sum_{k=0}^nx^k\binom{n+k}{k}+x^{n+1}\binom{2n+1}{n+1}\\ &+\sum_{k=0}^{n+1}x^{k+1}\binom{n+k+1}{k}-x^{n+2}\binom{2n+2}{n+1}\tag{1} \end{align} $$ Moving terms around and multiplying by $(1-x)^n$, we have $$ \begin{align} \hspace{-1cm}(1-x)^{n+1}\sum_{k=0}^{n+1}x^k\binom{n+k+1}{k} &=(1-x)^n\sum_{k=0}^nx^k\binom{n+k}{k}\\ &+(1-x)^n\left[x^{n+1}\binom{2n+1}{n}-x^{n+2}\binom{2n+2}{n+1}\right]\\ &=(1-x)^n\sum_{k=0}^nx^k\binom{n+k}{k}\\ &+(1-x)^n\left[\frac12x^{n+1}-x^{n+2}\right]\binom{2n+2}{n+1}\tag{2} \end{align} $$ since $\binom{2n+1}{n+1}=\binom{2n+1}{n}$ and $\binom{2n+1}{n+1}+\binom{2n+1}{n}=\binom{2n+2}{n+1}$.

Setting $x=\frac12$ in $(2)$ yields $$ \begin{align} 2^{-n-1}\sum_{k=0}^{n+1}2^{-k}\binom{n+k+1}{k} &=2^{-n}\sum_{k=0}^n2^{-k}\binom{n+k}{k}\\ &\vdots\\ &=2^{-0}\sum_{k=0}^02^{-k}\binom{0+k}{k}\\[9pt] &=1\tag{3} \end{align} $$ Therefore, $$ \sum_{k=0}^n2^{-k}\binom{n+k}{k}=2^n\tag{4} $$

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{\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{2^n = \sum_{k = 0}^{n}2^{-k}{n + k \choose k}:\ {\large ?}}$

$\ds{\tt\mbox{The following method is a straightforward one}}$.

Hereafter we'll use the identity $$\begin{array}{|c|}\hline\\ \ds{\quad{\,m \choose \ell\,}=\oint_{\verts{z}\ =\ b\ >\ 0} {\pars{1 + z}^{m} \over z^{\ell + 1}}\,{\dd z \over 2\pi\ic}\quad} \\ \\ \hline \end{array} $$

\begin{align}&\color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k}} =\sum_{k = -\infty}^{n}2^{-k}{n + k \choose n} =\sum_{k = \infty}^{-n}2^{k}{n - k \choose n} =\sum_{k = \infty}^{0}2^{k - n}{2n - k \choose n} \\[5mm]&=2^{-n}\sum_{k = 0}^{\infty}2^{k}{2n - k \choose n} =2^{-n}\sum_{k = 0}^{\infty}2^{k}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{2n - k} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} \\[5mm]&=2^{-n}\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}} \sum_{k = 0}^{\infty}\pars{2 \over 1 + z}^{k}\,{\dd z \over 2\pi\ic} \\[5mm]&=2^{-n}\oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{2n} \over z^{n + 1}} {1 \over 1 - 2/\pars{1 + z}}\,{\dd z \over 2\pi\ic} =2^{-n}\oint_{\verts{z}\ =\ a\ >\ 1} {\pars{1 + z}^{2n + 1} \over z^{n + 1}\pars{z - 1}}\,{\dd z \over 2\pi\ic} \\[5mm]&=2^{-n}\sum_{k = 0}^{\infty} \oint_{\verts{z}\ =\ a\ >\ 1}{\pars{1 + z}^{2n + 1} \over z^{n + 2 + k}}\,{\dd z \over 2\pi\ic} =2^{-n}\sum_{k = 0}^{\infty}{2n + 1 \choose n + k + 1} \end{align}

$$ \mbox{Then,}\quad\color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k}} =2^{-n}\color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}}\tag{1} $$

The $\ds{\color{#c00000}{\mbox{"red expression"}}}$ in $\pars{1}$ becomes: \begin{align} &\color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}} =\sum_{k = 0}^{-n}{2n + 1 \choose n + k} =\sum_{k = n}^{0}{2n + 1 \choose k} =\sum_{k = 0}^{2n + 1}{2n + 1 \choose k} -\sum_{k = n + 1}^{2n + 1}{2n + 1 \choose k} \\[3mm]&=2^{2n + 1} -\sum_{k = 0}^{n}{2n + 1 \choose k + n + 1} =2^{2n + 1} - \color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}}\ \imp\ \begin{array}{|c|}\hline\\ \quad\color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}} = 2^{2n}\quad \\ \\ \hline \end{array} \end{align}

We replace this result in expression $\pars{1}$: $$ \color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k} = 2^{n}} $$

Answer 5

Suppose we seek to verify that

$$S_n = \sum_{k=0}^n 2^{-k} {n+k\choose k} = 2^n.$$

We introduce the Iverson bracket

$$[[0\le k\le n]] = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \frac{1}{1-z} \; dz$$

so we may extend $k$ to infinity, getting

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

We evaluate this using the negative of the residues at $z=1, z=2$ and $z=\infty.$ We get for the residue at $z=1$

$$- \frac{1}{(1/2)^{n+1}} = - 2^{n+1}.$$

For the residue at $z=2$ we write

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

and we require the derivative

$$\frac{1}{n!} \left(\frac{1}{z^{n+1}} \frac{1}{1-z}\right)^{(n)} \\ = \frac{1}{n!} \sum_{q=0}^n {n\choose q} (-1)^q \frac{(n+q)!}{n!} \frac{1}{z^{n+1+q}} \frac{(n-q)!}{(1-z)^{n-q+1}}.$$

This simplifies to

$$\sum_{q=0}^n \frac{n!}{q! (n-q)!} \frac{1}{n!} \frac{(n+q)! (n-q)!}{n!} (-1)^q \frac{1}{z^{n+1+q}} \frac{1}{(1-z)^{n-q+1}} \\ = \sum_{q=0}^n {n+q\choose q} (-1)^q \frac{1}{z^{n+1+q}} \frac{1}{(1-z)^{n-q+1}}.$$

Evaluate at $z=2$ to get

$$\frac{1}{2^{n+1}} \sum_{q=0}^n {n+q\choose q} (-1)^q 2^{-q} (-1)^{n-q+1} \\ = \frac{(-1)^{n+1}}{2^{n+1}} \sum_{q=0}^n 2^{-q} {n+q\choose q}.$$

Therefore the residue at $z=2$ contributes

$$\sum_{q=0}^n 2^{-q} {n+q\choose q} = S_n.$$

Finally do the residue at $z=\infty$ getting

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

Using the fact that the residues sum to zero we thus obtain

$$S_n - 2^{n+1} + S_n = 0$$

which yields

$$\bbox[5px,border:2px solid #00A000]{ S_n = 2^n.}$$

Answer 6

This answer is based upon the Lagrange inversion formula. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^n]\frac{1}{1-2z}=[z^n]\sum_{j=0}^\infty 2^jz^j=2^n \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n2^{-k}\binom{n+k}{k}} &=\sum_{k=0}^n\binom{-n-1}{k}\left(-\frac{1}{2}\right)^k\tag{1}\\ &=[z^n]\frac{1}{\left(1-\frac{z}{2}\right)^{n+1}(1-z)}\tag{2}\\ &=[z^n]\left.\left(\frac{1}{\left(1-\frac{w}{2}\right)(1-w)}\cdot\frac{1}{1-\frac{w}{2}\cdot\frac{1}{1-\frac{w}{2}}}\right)\right|_{w=\frac{z}{1-\frac{w}{2}}}\tag{3}\\ &=[z^n]\left.\frac{1}{(1-w)^2}\right|_{w=1-\sqrt{1-2z}}\tag{4}\\ &=[z^n]\frac{1}{1-2z}\\ &\color{blue}{=2^n} \end{align*}

Comment:

• In (1) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ and $\binom{p}{q}=\binom{p}{p-q}$.

• In (2) we observe the sum is the coefficient of the convolution of two series \begin{align*} [z^n]\left(\sum_{k}a_kz^k\right)\left(\sum_{l}b_lz^l\right)=[z^n]\sum_{N}\left(\sum_{k=0}^Na_k b_{N-k}\right)z^N =\sum_{k=0}^na_k b_{n-k} \end{align*} Here with $a_k=\binom{-n-1}{k}\left(-\frac{1}{2}\right)^k$ and $b_k=1$.

• In (3) we use the Lagrange Inversion Formula in the form G6 stated in R. Sprugnolis (etal) paper Lagrange Inversion: when and how.

\begin{align*} [z^n]F(z)\Phi(z)^n=[z^n]\left.\frac{F(w)}{1-z\Phi'(w)}\right|_{w=z\Phi(w)} \end{align*}

Here with $\Phi(z)=\frac{1}{1-\frac{z}{2}}$ and $F(z)=\frac{1}{\left(1-\frac{z}{2}\right)(1-z)}$. It follows since $w=z\Phi(w)$: \begin{align*} z\Phi^{\prime}(w)=\frac{z}{2}\cdot\frac{1}{\left(1-\frac{w}{2}\right)^2} =\frac{z}{2}\Phi^2(w)=\frac{w}{2}\Phi(w)=\frac{w}{2}\cdot\frac{1}{1-\frac{w}{2}} \end{align*}

• In (4) we simplify the expression and we select the solution $w=w(z)$ from $w=\frac{z}{1-\frac{w}{2}}$ which can be expanded in a power series.