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

Solution 1:

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.

Solution 2:

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.