12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Try induction. Note that $\binom{2n}n = 2\binom{2n-1}{n-1}$. $\endgroup$ – Ted Shifrin May 12 '13 at 4:41
7
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your "opposite direction" is a bit terse. Do I understand correctly that $\frac12 = \sum\limits_{k=0}^n 2^{-(n+k-1)} \binom{n+k}n$ gives the total probability that $A$ will win, as sum over the probabilities that she will win after $n+k+1$ votes, for $k=0,1,\ldots,n$? $\endgroup$ – Marc van Leeuwen May 13 '13 at 9:03
  • $\begingroup$ I think he means to say that the process has a probability 1 of stopping, and each summand is the probability the process stops at that specific time. $\endgroup$ – extremeaxe5 Oct 1 '14 at 2:11
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That looks like a very neat proof. For equation (3) how did you conclude that it equals 1? $\endgroup$ – hypergeometric Sep 7 '14 at 9:12
  • $\begingroup$ @hypergeometric: note that the first line in $(3)$ says that the sum for $n$ equals the sum for $n+1$. Setting $n=0$ gives the sum to be $1$. $\endgroup$ – robjohn Sep 7 '14 at 12:03
  • $\begingroup$ Thanks for your response. Very clever, this "built-in induction" $f(n+1)=f(n)$. $\endgroup$ – hypergeometric Sep 7 '14 at 14:33
  • $\begingroup$ I've added a line for $n=0$. Hopefully, that makes things a bit clearer. If not, perhaps I should add some desription around $(3)$. $\endgroup$ – robjohn Sep 7 '14 at 15:33
  • $\begingroup$ Yes, that certainly helps. I suppose those who cannot understand should ask, or read the comments first. $\endgroup$ – hypergeometric Sep 7 '14 at 16:02
2
$\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{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}} $$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Inspired by robjohn's answer I show a more general statement: for $x\in \mathbb{R}$ and $n\in\mathbb{N}$, $$\bbox[5px,border:2px solid #0000A0]{\sum_{k=0}^{n}\binom{n+k}{k}((1-x)^{n+1}x^k+x^{n+1}(1-x)^k)=1}$$ Such identity appears as equation 69 at this page (see hypergeometric's comment). OP's identity follows by setting $x=1/2$.

Let $$f_n(x)=\sum_{k=0}^{n}\binom{n+k}{k}x^k$$ then we have to show by induction that $$(1-x)^{n+1}f_n(x)+x^{n+1}f_n(x)=1.$$ Base case: for $n=0$ it is trivial.

\noindent Inductive step step. We note that \begin{align*} f_{n+1}(x) &=\sum_{k=0}^{n+1}\left(\binom{n+k}{k}+\binom{n+1+k-1}{k-1}\right)x^k\\ &=f_n(x)+\binom{2n+1}{n+1}x^{n+1}+xf_{n+1}(x)-\binom{2n+2}{n+1}x^{n+2}\\ &=f_n(x)+\binom{2n+1}{n}x^{n+1}+xf_{n+1}(x)-2\binom{2n+1}{n}x^{n+2} \end{align*} Therefore $$(1-x)f_{n+1}(x)=f_n(x)+\binom{2n+1}{n}x^{n+1}(1-2x)$$ Hence $$(1-x)^{n+2}f_{n+1}(x) =(1-x)^{n+1}f_n(x)+\binom{2n+1}{n}(1-x)^{n+1}x^{n+1}(1-2x)$$ and, by replacing $x$ with $(1-x)$, we get $$x^{n+2}f_{n+1}(1-x) =x^{n+1}f_n(1-x)-\binom{2n+1}{n}x^{n+1}(1-x)^{n+1}(1-2x).$$ Finally, by adding the last two equations we find $$(1-x)^{n+2}f_{n+1}(x)+x^{n+2}f_{n+1}(1-x)= x^{n+1}f_n(1-x)+(1-x)^{n+1}f_n(x)=1$$ and we are done.

$\endgroup$
0
$\begingroup$

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