One statement of the Binomial Theorem for negative exponents is
The combinatorial interpretation is that is the number of ways to place indistinguishable balls into numbered urns: expanding by choosing from the th factor corresponds to a placement having balls in urn .
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
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 and the Pascal recurrence to rewrite the right-hand side: if is the left-hand side, it follows in a few lines that , hence the result.
Replace with and multiply through by to get the equivalent form
Bijective proof. There is a well-known bijection between ways to place indistinguishable balls into numbered urns and binary sequences of length with exactly zeros and ones: the zeros correspond to balls, and the ones to urn walls after every right urn wall, and the left wall of urn number are deleted. For example, encodes the placement with two balls in urn , one ball in urn , no balls in urn , and one ball in urn . Let be the set of sequences of length obtained by extending each such sequence by a further bits.
This gives sequences of length , but as it stands, only sequences with at least 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 . It consists of all sequences of the form . Such a sequence lies in if and only if . More generally, if then a sequence lies in if and only if . Say that such sequences are –flippable. Let be the set of flippable sequences in and let be the set of sequences obtained by flipping the first positions of each sequence in . Note that the sequences in have their th zero in position , and at most ones. Set .
Let be a binary sequence of length .
- Suppose that has at most ones. Then has at least zeros, and we can hope to obtain by flipping. Suppose that the th zero is in position . By the previous remark and is in no other ; moreover, flipping the zeros and ones in positions up to of gives the corresponding -flippable sequence in .
- If has exactly ones then .
- Suppose that has at least ones, and that the th one is in position . Then and in no other . Moreover is not -flippable.
The three cases therefore give a bijection
The size of the left-hand side is , as required.