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 ith 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 rflippable. 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 nth 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 nth 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 nth 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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: