Gosper’s algorithm discovers integral identity


While playing around with Gosper’s algorithm, I discovered a very neat identity:

I’d like to show how to derive it.

The identity is not as deep as it first seems. It actually comes from linking two smaller identities together:

The first is entirely routine:

In [1]: import sympy as sp
In [2]: from sympy.concrete.gosper import gosper_sum
In [3]: from sympy.abc import n, k

In [4]: gosper_sum(sp.binomial(2 * k, k) / 4**k, (k, 0, n))
Out[4]: 4**(-n)*(2*n + 1)*binomial(2*n, n)

Hooray for Gosper’s algorithm!

The second identity is a little more challenging. Here’s one way to prove it: The generating function for the sequence


(Exchange the sum and integral, evaluate the resulting geometric sum, then rescale the remaining integral by $(1 - x)^{-1/2}$.) The generating function for $\binom{2n}{n}$ is

Therefore, doing some rescaling and equating of coefficients,

This gives us our identity!

A better identity

Applying Gosper’s algorithms to sums of the form $\sum_{k = 0}^n f(k)$ really undersells its power. When Gosper’s algorithm works, it gives much more.

Gosper’s algorithm really tells us that

which is a strictly better result.