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.

**Lemma 1**.

.

*Proof.*

By Identity 17 in my book *The Art of Proving Binomial Identities* [1],

where in the second step we use properties of the falling factorial .

Next, we need the following generating function.

**Lemma 2.**

*Proof.*

By Newton’s binomial series (Identity 18 in my book [1]),

Finally, we’re ready to prove the identity.

**Identity 1.**

*Proof.*

Let , and let . Since the generating function for is (Lemma 2), and the generating function for is (Identity 150 in [1]), the generating function for their convolution,

is, by the convolution property for generating functions (see Theorem 13 in [1]),

Since just generates the sequence , this means that

Therefore, when , we have

**References**

1. Michael Z. Spivey, *The Art of Proving Binomial Identities*, CRC Press, 2019.

### Like this:

Like Loading...

*Related*

Interesting problem! Another way to prove this is to note that the right-hand side counts lattice paths from (0,0) to (n,n) directly, while the left-hand side groups the paths by the first point (k,k) where the path intersects the diagonal. The C(2n-2k,n-k) factor counts unrestricted ways to “continue” the path from (k,k) to (n,n), and C(2k,k)/(2k-1) is (via a little algebraic manipulation) the k-1st Catalan number times 2– that is, we can either go above the diagonal from (0,1) to (k-1,k), or below it from (1,0) to (k,k-1).

Very nice! I’m not surprised there’s a lattice-paths argument as well – thanks for providing it!