The Binomial Theorem

The Binomial Theorem is an extremely important and general (and totally sweet) result in the field of combinatorics (which is the branch of mathematics about counting things). Without further ado, here it is:

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

Wait! Don’t let all the fancy symbols and variables scare you; it’s actually not too complicated. Go back and read it again, carefully, and then let’s break it down a bit. It says that the nth power of the binomial x+y (whence the theorem gets its name) can be found by a sum (\Sigma) which starts with \binom{n}{0} x^n y^0, and each subsequent term of the sum is composed of the next binomial coefficient, one fewer x, and one more y. For example:

\begin{array}{rcl} (x+y)^3 & = & \binom{3}{0}x^3 + \binom{3}{1}x^2 y + \binom{3}{2} x y^2 + \binom{3}{3} y^3 \\ & = & x^3 + 3x^2 y + 3xy^2 + y^3. \end{array}

(Recall that anything to the zero power is 1.) Make sense? Another way to think about it is that (x+y)^n, when expanded, consists of a number of terms of the form x^a y^b, where a and b always add up to n; the coefficients of the terms are determined by the entries in a row of Pascal’s Triangle. Why is this true? Expand out (x+y)^n without collecting like terms; for example:

(x+y)^2 = xx + xy + yx + yy

(x+y)^3 = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy

In general you get a total of 2^n terms, one corresponding to each possible way to choose a string of n x’s and y’s. Every term with exactly k x’s (and therefore (n-k) y’s) can be combined, since, for example, xxy = xyx = yxx = x^2 y; the number of such terms is the number of ways to choose k x’s out of n letters. Thus, the Binomial Theorem!

Now, why is the BT so sweet? Here are a few reasons, in the form of problems for you to try:

  1. Prove the binomial coefficient sum equation from last time in yet another way (hint: expand (1+1)^n using the Binomial Theorem).
  2. Prove another interesting binomial coefficient identity by expanding (1-1)^n.
  3. Compute 11^0, 11^1, 11^2, 11^3, 11^4. Notice anything interesting? Why does that happen? (Hint: 11 = 10 + 1.) What happens when you compute 11^5? Can you think of a way to “fix” it?
  4. According to the BT, what is (a+b)^2? Does that look familiar?
  5. If you know some calculus, use the BT and the definition of the derivative

    \displaystyle\frac{d}{dx} f(x) = \lim_{h \to 0} \frac{f(x+h)-f(x)}{h}

    to prove the power rule for derivatives:

    \displaystyle\frac{d}{dx} x^n = nx^{n-1}.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in counting, pascal's triangle, pattern. Bookmark the permalink.