There are two binomial coefficient identities in *Concrete Mathematics* that have bothered me for years: They look they should have combinatorial proofs, but I couldn’t for the life of me think of what those might be. (In *Concrete Mathematics* they are proved with generating functions.) Well, I just recently found those combinatorial proofs I was looking for.

Here are the identities. [2, p. 202]

(1) .

(2) .

The key idea I didn’t have before is the g*eneral ballot theorem*, which states that the number of lattice paths from to , that never touch the line after is given by . This can be proved combinatorially; see, for example, Renault’s paper [5].

Identity (1) counts the number of lattice paths from to . The right-hand side is straightforward, since counts the number of lattice paths from to . For the left side, condition on the number of right steps *k* a lattice path takes *after* touching the line for the last time. By the general ballot theorem, the number of paths from to that never touch the line after the initial point is . (This is because there are *k* right steps and up steps.) Also, the number of lattice paths from to is . Summing over all possible values of *k* gives the left side of Identity (1).

Identity (2) is similar, although it counts the number of lattice paths from to that never touch the line after . The right side follows from the general ballot theorem. For the left side, condition on the last place a lattice path touches the line . By the general ballot theorem, there are paths from to that never touch the line after . Also by the general ballot theorem, there are lattice paths from to that never touch the line after the initial point. Multiplying these together and summing over all values of *k* gives the left side.

I don’t think these proofs are new; for example, Chu [1] mentions lattice path proofs of these identities in books by Mohanty [3] and Narayana [4].

**References**

- Wenchang Chu, “Elementary Proofs for Convolution Identities of Abel and Hagen-Rothe,”
*Electronic Journal of Combinatorics*17, Note #N24, 2010. - Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.
*Concrete Mathematics*, 2nd ed., Addison-Wesley, 1994. - S. G. Mohanty,
*Lattice Path Counting and Applications*, Academic Press, 1979. - T. V. Narayana,
*Lattice Path Combinatorics with Statistical Applications*, Univ. of Toronto Press, 1979. - Marc Renault, “Lost (and Found) in Translation: André’s
*Actual*Method and Its Application to the Generalized Ballot Problem,”*American Mathematical Monthly*115 (4), 2008, pp. 358-363.