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.)


Now, what about (2)?

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.
  2. H. W. Gould, Combinatorial Identities, 2nd ed.  Published by the author, Morgantown, WV, 1972.  See also Gould’s web site.
  3. Tristan Needham, Visual Complex Analysis, Clarendon Press, Oxford, 1997.
  4. Michael Z. Spivey, “Combinatorial Sums and Finite Differences,” Discrete Mathematics, 307 (24): 3130-3146, 2007.
Advertisements
This entry was posted in binomial coefficients, combinatorics, complex numbers. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s