## A finite negative binomial identity

One statement of the Binomial Theorem for negative exponents is

$\sum_{m=0}^\infty \binom{m+k-1}{m} x^m = \frac{1}{(1-x)^k}$

The combinatorial interpretation is that $\binom{m+k-1}{m}$ is the number of ways to place $m$ indistinguishable balls into $k$ numbered urns: expanding $1/(1-x)^k = (1+x+x^2 + \cdots + )^k$ by choosing $x^{m_i}$ from the $i$th factor corresponds to a placement having $m_i$ balls in urn $i$.

Identity (1.16) in Volume 2 of Gould’s Tables is introduced as a finite version of the Binomial Theorem for negative exponents. It states that

$\sum_{r=0}^n \binom{n+r}{r} \frac{1}{2^r} = 2^n$.

This identity is not of the most basic kind, but the most obvious proof works (although maybe not in the most obvious way). Use induction on $n$ and the Pascal recurrence $\binom{n+r}{r} = \binom{n+r-1}{r} + \binom{n+r-1}{r-1}$ to rewrite the right-hand side: if $L$ is the left-hand side, it follows in a few lines that $L = 2^{n-1} + L/2$, hence the result.

Replace $n$ with $n-1$ and multiply through by $2^{n-1}$ to get the equivalent form

$\sum_{r=0}^{n-1} \binom{n+r-1}{r} 2^{n-1-r} = 2^{2(n-1)}.$

Bijective proof. There is a well-known bijection between ways to place $r$ indistinguishable balls into $n$ numbered urns and binary sequences of length $n+r-1$ with exactly $r$ zeros and $n-1$ ones: the zeros correspond to balls, and the ones to urn walls after every right urn wall, and the left wall of urn number $1$ are deleted. For example, $0010110$ encodes the placement with two balls in urn $1$, one ball in urn $2$, no balls in urn $3$, and one ball in urn $4$. Let $S_r$ be the set of sequences of length $2(n-1)$ obtained by extending each such sequence by a further $n-r-1$ bits.

This gives sequences of length $2(n-1)$, but as it stands, only sequences with at least $n-1$ ones appear. So some sequences appear several times as extended ball-and-urn sequences, while others never appear. This can be corrected as follows.

First consider $S_0$. It consists of all sequences of the form $1\ldots 1s_n s_{n+1} \ldots s_{2(n-1)}$. Such a sequence lies in $S_1$ if and only if $s_n=0$. More generally, if $r < n-1$ then a sequence $s \in S_r$ lies in $S_{r+1}$ if and only if $s_{n+r}=0$. Say that such sequences are $r$flippable. Let $F_r$ be the set of flippable sequences in $S_r$ and let $T_r$ be the set of sequences obtained by flipping the first $n+r-1$ positions of each sequence in $F_r$. Note that the sequences in $T_r$ have their $n$th zero in position $n+r$, and at most $n-2$ ones. Set $T_{n-1} = \varnothing$.

Let $s$ be a binary sequence of length $2(n-1)$.

• Suppose that $s$ has at most $n-2$ ones. Then $s$ has at least $n$ zeros, and we can hope to obtain $s$ by flipping. Suppose that the $n$th zero is in position $n+r$. By the previous remark $s \in T_r$ and $s$ is in no other $T_t$; moreover, flipping the $n-1$ zeros and $r$ ones in positions $1$ up to $n+r-1$ of $s$ gives the corresponding $r$-flippable sequence in $F_r$.
• If $s$ has exactly $n-1$ ones then $s \in S_{n-1}$.
• Suppose that $s$ has at least $n$ ones, and that the $n$th one is in position $n+q$. Then $s \in S_q$ and in no other $S_t$. Moreover $s$ is not $r$-flippable.

The three cases therefore give a bijection

$\displaystyle \bigcup_{r=0}^{n-1} F_r \cup (S_r \backslash F_r) \longleftrightarrow \bigcup_{r=0}^{n-1} T_r \cup (S_r \backslash F_r) = \{0,1\}^{2(n-1)}.$

The size of the left-hand side is $\sum_{r=0}^{n-1} \binom{n+r-1}{r} 2^{n-1-r}$, as required.