A few weeks ago I received an email from Professor Steve Drekic at the University of Waterloo. He asked if I knew of a way to prove the following binomial identity:
(He told me later that he wanted it to help prove that the random walk on the integers with transition probability is null recurrent.)
It’s an interesting binomial identity, in that it has a nontrivial but not overly complicated sum on the left side and a simple expression on the right. Yet I had not seen it before. I was able to find a proof that uses generating functions, and I thought I would reproduce it here.
By Identity 17 in my book The Art of Proving Binomial Identities ,
where in the second step we use properties of the falling factorial .
Next, we need the following generating function.
By Newton’s binomial series (Identity 18 in my book ),
Finally, we’re ready to prove the identity.
Let , and let . Since the generating function for is (Lemma 2), and the generating function for is (Identity 150 in ), the generating function for their convolution,
is, by the convolution property for generating functions (see Theorem 13 in ),
Since just generates the sequence , this means that
Therefore, when , we have
1. Michael Z. Spivey, The Art of Proving Binomial Identities, CRC Press, 2019.