A Request for a Proof of a Binomial Identity

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:

\displaystyle \sum_{k=1}^n \frac{1}{2k-1} \binom{2k}{k} \binom{2n-2k}{n-k} = \binom{2n}{n}.

(He told me later that he wanted it to help prove that the random walk on the integers with transition probability p = 1/2 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.

\displaystyle \binom{1/2}{k} = \frac{-1}{2k-1} \binom{-1/2}{k}.

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

\displaystyle \binom{1/2}{k} = \frac{(1/2)^{\underline{k}}}{k!} = \frac{(1/2) (-1/2)^{\underline{k}}}{(-1/2-k+1) k!} = \frac{(-1/2)^{\underline{k}}}{-(2k-1)) k!} = \frac{-1}{2k-1} \binom{-1/2}{k},

where in the second step we use properties of the falling factorial x^{\underline{k}}.

Next, we need the following generating function.

Lemma 2.

Proof.
\displaystyle - \sqrt{1-4x} = \sum_{k=0}^{\infty} \frac{1}{2k-1} \binom{2k}{k} x^k.

By Newton’s binomial series (Identity 18 in my book [1]),
\displaystyle  -\sqrt{1-4x} = -(1-4x)^{1/2} = -\sum_{k=0}^{\infty} \binom{1/2}{k} (-4x)^k \\ = -\sum_{k=0}^{\infty} \frac{-1}{2k-1} \binom{-1/2}{k} (-4x)^k, \text{ by Lemma 1} \\ = \sum_{k=0}^{\infty} \frac{1}{2k-1} \left(\frac{-1}{4}\right)^k \binom{2k}{k} (-4x)^k, \text{ by Identity 30 in [1]} \\ = \sum_{k=0}^{\infty} \frac{1}{2k-1} \binom{2k}{k} x^k.

Finally, we’re ready to prove the identity.

Identity 1.

\displaystyle \sum_{k=1}^n \frac{1}{2k-1} \binom{2k}{k} \binom{2n-2k}{n-k} = \binom{2n}{n}.

Proof.
Let a_k = \binom{2k}{k}/(2k-1), and let b_k = \binom{2k}{k}. Since the generating function for (a_k) is -\sqrt{1-4x} (Lemma 2), and the generating function for (b_k) is 1/\sqrt{1-4x} (Identity 150 in [1]), the generating function for their convolution,

\displaystyle c_n = \sum_{k=0}^n \frac{1}{2k-1} \binom{2k}{k} \binom{2n-2k}{n-k},

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

\displaystyle - \frac{\sqrt{1-4x}}{\sqrt{1-4x}} = -1.

Since -1 just generates the sequence -1, 0, 0, 0, \ldots, this means that

\displaystyle \sum_{k=0}^n \frac{1}{2k-1} \binom{2k}{k} \binom{2n-2k}{n-k} = \begin{cases} -1, & \: n = 0; \\ 0, & \: n \geq 1.\end{cases}

Therefore, when n \geq 1, we have
\displaystyle  \sum_{k=0}^n \frac{1}{2k-1} \binom{2k}{k} \binom{2n-2k}{n-k} = 0 \\ \implies \sum_{k=1}^n \frac{1}{2k-1} \binom{2k}{k} \binom{2n-2k}{n-k} - \binom{2n}{n} = 0 \\ \implies \sum_{k=1}^n \frac{1}{2k-1} \binom{2k}{k} \binom{2n-2k}{n-k} = \binom{2n}{n}.

References

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

This entry was posted in binomial coefficients, generating functions. Bookmark the permalink.

2 Responses to A Request for a Proof of a Binomial Identity

  1. 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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s