A small binomial sum

Published:

I recently came across an interesting binomial sum in this Math.SE question. As usual, Zeilberger’s algorithm makes short work of it, but the “human” approach reveals a small miracle.

We want to evaluate

Our first step is to use the identity ${2k \choose k} = (-4)^k {-1/2 \choose k}$ and write

There might be a nice, direct way to evaluate this sum, but I don’t know it. Instead, let’s apply the snake oil method. Let $R(x) = \sum_{n \geq 0} R_n(z) x^k$. By expanding $R_n(z)$ and interchanging the order of summation, it is easy to show that

The radicand in the denominator is a quadratic polynomial in $x$ with discriminant $16z(z - 1)$. The square root disappears precisely when $z = 0$ or $z = 1$! If $z = 0$ the sum is trivially $1$, and if $z = 1$ we get

so

In other words, the sum given has a nice, exponential solution in only the case the Math.SE question asked. Remarkable!

Reflections

Zeilberger’s produces a recurrence for $R_n(z)$ straight away. Running ZeilbergerRecurrence(f, n, k, R, 0..n) assuming n::posint where $f$ is the summand of $R_n(z)$ yields

So, in general, $R_n(z)$ is holonomic in $n$ and needs no more than three terms in its defining recurrence. Of course, if $z = 1$, then ZeilbergerRecurrence instead yields

so it sometimes simplifies. Maple fails to solve the general recurrence when $z$ is symbolic.

If we were good enough with complex functions, then we could work out asymptotics, but in any event this is another avenue to explore.