that equals the right side of (1). These approaches give short proofs of (1), but they
both use a good deal of advanced mathematics. With a bit of work, we can also obtain
an elementary proof of (1) using only basic properties of the binomial coefficients and
mathematical induction.
The proof of (1) given below arose, not in a search for a new proof of this identity,
but as a result of some independent probability research . . . and a cluttered desk.
Being unable to find a probability calculation I had done the day before, I sought to
repeat the calculation—but obtained a different expression for the same quantity. After
some initial confusion, I realized that my computations gave a simple proof of the
identity (1).