Of Combinatorics and Contours

Consider the contour integral

\frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n}}{z^{k + 1}} d z

where $C$ is a positively oriented circular contour centered at $z = 0$ . If we expand the term in the numerator using the binomial theorem, we see that the above integral is

\frac{1}{2 π i} \oint_{C} ((\binom{n}{0}) + \dots + (\binom{n}{k - 1}) z^{k - 1} + (\binom{n}{k}) z^{k} + (\binom{n}{k + 1}) z^{k + 1} + \dots + (\binom{n}{n}) z^{n}) \frac{1}{z^{k + 1}} d z .

The coeffcient of the $1 / z$ term is $(\binom{n}{k})$ , so it follows that

\frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n}}{z^{k + 1}} d z = (\binom{n}{k}) .

The use of this contour integral — and similar integrals — to prove combinatorial identities is known as the Egorychev method, and it can make quick work of difficult identities involving finitie and infinite sums of binomial coefficients. For example, we can easily evaluate the sum

\sum_{k = 0}^{n} {(\binom{n}{k})}^{2}

as follows

\begin{aligned} \sum_{k = 0}^{n} {(\binom{n}{k})}^{2} & = \frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n}}{z} \sum_{k = 0}^{n} (\binom{n}{k}) \frac{1}{z^{k}} d z \\ = \frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n}}{z} {(1 + \frac{1}{z})}^{n} d z \\ = \frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{2 n}}{z^{n + 1}} d z \\ = (\binom{2 n}{n}) . \end{aligned}

Hence we have

\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n}) .

Further examples

Lets prove that

\sum_{k = 0}^{n} k {(\binom{n}{k})}^{2} = n (\binom{2 n - 1}{n}) .

First note that by differentiating

(1 + x)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k}

we get

n (1 + x)^{n - 1} = \sum_{k = 0}^{n} k (\binom{n}{k}) x^{k - 1} .

Then multiplying each side by x yields

n x (1 + x)^{n - 1} = \sum_{k = 0}^{n} k (\binom{n}{k}) x^{k} .

Now let $n \geq 1$ ,

\begin{aligned} \sum_{k = 0}^{n} k {(\binom{n}{k})}^{2} & = \sum_{k = 0}^{n} \frac{k}{2 π i} (\binom{n}{k}) \oint_{C} \frac{(1 + z)^{n}}{z^{k + 1}} d z \\ = \frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n}}{z} \sum_{k = 0}^{n} k (\binom{n}{k}) \frac{1}{z^{k}} d z \\ = \frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n}}{z} \cdot \frac{n}{z} {(1 + \frac{1}{z})}^{n - 1} d z \\ = \frac{n}{2 π i} \oint_{C} \frac{(1 + z)^{2 n - 1}}{z^{n + 1}} d z \\ = n (\binom{2 n - 1}{n}) . \end{aligned}

A Fibonacci identity

In order to show that

\sum_{k = 0}^{n} (\binom{n + k}{2 k}) = F_{2 n + 1}

we may make use of

(\binom{n}{k}) = 0 if k > n

and Binet’s formula. Let $ϕ = (1 + \sqrt{5}) / 2$ and $\bar{ϕ} = (1 - \sqrt{5}) / 2$ , then

\begin{aligned} \sum_{k = 0}^{n} (\binom{n + k}{2 k}) & = \sum_{k = 0}^{\infty} (\binom{n + k}{2 k}) \\ = \sum_{k = 0}^{\infty} \frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n + k}}{z^{2 k + 1}} d z \\ = \frac{1}{2 π i} \oint_{C} \frac{(1 + z)^{n}}{z} \sum_{k = 0}^{\infty} {(\frac{1 + z}{z^{2}})}^{k} d z \\ = \frac{1}{2 π i} \oint_{C} \frac{z (1 + z)^{n}}{z^{2} - z - 1} d z, \\ where C encircles the poles at ϕ and \bar{ϕ} \\ = \frac{1}{2 π i} \oint_{C} \frac{z (1 + z)^{n}}{(z - ϕ) (z - \bar{ϕ})} d z \\ = \frac{ϕ (1 + ϕ)^{n}}{ϕ - \bar{ϕ}} + \frac{\bar{ϕ} (1 + \bar{ϕ})^{n}}{\bar{ϕ} - ϕ} \\ = \frac{ϕ (1 + ϕ)^{n} - \bar{ϕ} (1 + \bar{ϕ})^{n}}{\sqrt{5}} \\ = \frac{ϕ \cdot ϕ^{2 n} - \bar{ϕ} \cdot {\bar{ϕ}}^{2 n}}{\sqrt{5}} \\ = F_{2 n + 1} \end{aligned}

as was desired.

Of Combinatorics and Contours

Further examples

A Fibonacci identity

Further Reading

AMM12332

Integrals and the Jacobi Triple Product

A Double Sum with Fantastic Symmetry