# 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

\[R_n(z) = \sum_k (-1)^k {2k \choose k} {k \choose n - k} z^k.\]Our first step is to use the identity ${2k \choose k} = (-4)^k {-1/2 \choose k}$ and write

\[R_n(z) = \sum_k {-1/2 \choose k} {k \choose n - k} (4z)^k.\]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

\[R(x) = \frac{1}{1 + 2x},\]so

\[R_n(1) = \sum_k 4^k {-1/2 \choose k} {k \choose n - k} = (-2)^n.\]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.