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

• mzspivey says:

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