# Gosper’s algorithm discovers integral identity

Published:

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

$$$\sum_{k = 0}^n\frac{\binom{2k}{k}}{4^k} = \frac{2n + 1}{\pi} \int_{-\infty}^\infty \frac{x^{2n}}{(x^2 + 1)^{n + 1}}\ dx.$$$

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:

\begin{align} \sum_{k = 0}^n \frac{\binom{2k}{k}}{4^k} &= \frac{2n + 1}{4^n} \binom{2n}{n} \\ \int_{-\infty}^\infty \frac{x^{2n}}{(x^2 + 1)^{n + 1}}\ dx &= \frac{\pi}{4^n} \binom{2n}{n}. \end{align}

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

$I(n) = \int_{-\infty}^\infty \frac{x^{2n}}{(x^2 + 1)^{n + 1}}\ dx$

is

$\frac{\pi}{\sqrt{1 - x}}.$

(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

$\frac{1}{\sqrt{1 - 4x}}.$

Therefore, doing some rescaling and equating of coefficients,

$\frac{\pi}{4^n} \binom{2n}{n} = \int_{-\infty}^\infty \frac{x^{2n}}{(x^2 + 1)^{n + 1}}\ dx.$

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

$\Delta \frac{2n + 1}{\pi} \int_{-\infty}^\infty \frac{x^{2n}}{(x^2 + 1)^{n + 1}}\ dx = \Delta \frac{2n + 1}{4^n} \binom{2n}{n} = \frac{\binom{2n}{n}}{4^n},$

which is a strictly better result.

Tags: