## Binomial Coefficient Identities via Complex Numbers

Binomial coefficient identities are normally proved by combinatorial arguments, by manipulation of other known binomial coefficient identities, by generating functions, or even sometimes by finding the right integral representation.  This post is going to look at a couple of binomial identities that have nice proofs using complex numbers.  (Well, we’re going to use the binomial theorem, too, but that’s it.)

In my paper “Combinatorial Sums and Finite Differences” [4] I use the techniques presented therein to prove the (known) identities

$\displaystyle \sum_{k=0}^n \binom{n}{k} (-1)^k = [n=0],$ and $\displaystyle \sum_{k=0}^{n} \binom{2n}{2k} = 2^{2n}-1 + \frac{1}{2}[n=0].$

Two variations on these sums that I did not consider are

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

and

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

While the techniques used in my paper can be extended to handle these sums, both of them can be evaluated easily using complex numbers, too.

Let’s take (1) first. Since the binomial theorem applies to complex numbers, we have
$\displaystyle \sum_{k=0}^{2n} \binom{2n}{k} i^k = (1 + i)^{2n} = \left(\sqrt{2} e^{i\pi/4}\right)^{2n} = 2^n e^{i n \pi /2} = 2^n \left(\cos \left(\frac{n \pi}{2}\right) + i \sin \left(\frac{n \pi}{2}\right)\right)$.

Equating real and imaginary parts gives us not only a formula for (1) but also a bonus binomial coefficient identity:

$\displaystyle \sum_{k=0}^n \binom{2n}{2k} (-1)^k = 2^n \cos \left(\frac{n \pi}{2}\right)$
and
$\displaystyle \sum_{k=0}^{n-1} \binom{2n}{2k+1} (-1)^k = 2^n \sin \left(\frac{n \pi}{2}\right)$.

(Proving the latter identity via complex numbers is Problem 32 in Chapter 1 of Tristan Needham’s Visual Complex Analysis [3], which is a good read in its own right.)

Let $\omega$ be a primitive third root of unity, such as $e^{i 2\pi/3}$. Thus  $\omega^2 = e^{i 4\pi/3} = -(1+ \omega)$, and $\omega^3 = 1$.

Applying the binomial theorem, we have

$\displaystyle \sum_{k=0}^{3n} \binom{3n}{k} \omega^k = (1 + \omega)^{3n} = (-\omega^2)^{3n} = (-1)^{3n} (\omega^3)^{2n} = (-1)^n.$

and

$\displaystyle \sum_{k=0}^{3n} \binom{3n}{k} \left(\omega^2\right)^k = (1 + \omega^2)^{3n} = (-\omega)^{3n} = (-1)^n.$

Now, $1 + \omega^k + \omega^{2k}$ is either 0, if k is not divisible by 3, or is 3, if k is divisible by 3.  Thus

$\displaystyle \sum_{k=0}^n \binom{3n}{3k} = \frac{1}{3} \sum_{k=0}^{3n} \binom{3n}{k} \left(1 + \omega^k + (\omega^2)^k\right) = \frac{2^{3n} + 2(-1)^n}{3}.$

(In general, we have $\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$ with $\omega$ a primitive rth root of unity.  See, for example, Gould’s Combinatorial Identities [2] or the beautiful combinatorial proof in the recent paper [1] by Benjamin, Chen, and Kindred.  Also related is this math.SE question of Qiaochu Yuan’s.)

References

1. Arthur T. Benjamin, Bob Chen, and Kimberly Kindred, “Sums of Evenly Spaced Binomial Coefficients,” Mathematics Magazine 83 (5): 370-373, December 2010.