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