Lecture 12: The Binomial Theorem
\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \)The midterm will be in class, Wednesday of 6th week, February 13. If you have an examination accommodation, please make the necessary arrangements with Student Disability Services to schedule your exam, and please choose a time that substantially overlaps with the in-class final.
The lecture will cover material through Lecture 13, inclusive.
We can imagine a product of sums as a kind of circuit, e.g., $(a+b) \mult (c+d) \mult (e+f)$ can be envisioned thus:
Evaluation of the product amounts to summing the value of all the paths through the circuit, where the value of a path is the product of the values it contains: add in parallel, multiply in series. Thus, for example, the term $acf$ in the product corresponds to the path indicated in red below:
Example 12.1 We can apply this evaluation trick to evaluating powers of binomials, e.g., $(x+y)^5$, obtaining $2^5=32$ terms, e.g., $xxyxy$. Of course, we've been taught to gather together identical factors and express the resulting term like this: $x^3y^2$, and we can easily see that all of the terms we'll get will have the form $x^{5-i}y^i$ for some $0\leq i \leq 5$. The next thing we want to do is gather together like terms. How many times does $x^3y^2$ occur in the full expansion of $(x+y)^5$? If we consider this from the point of view of the $y$'s, we see that we have five binary choices, and we'll get two $y$'s if we choose the $y$ path exactly two times out of five. So the coefficient of $x^3y^2$ must be $C(5,3)$.
An alternative way of visualizing this, and one that's useful because you will encounter problems that take this form, is to consider the following map of one-way streets:
We establish a one-to-one correspondence between paths through the grid and $3$-element subsets of a $5$-element set: any path involves five steps, each of which much be either follow either an $x$-arrow or a $y$-arrow. The elements of the subset correspond to choices to follow the $x$-arrow. E.g., if our five element set is $\{1,2,3,4,5\}$, and our subset is $\{2,4,5\}$, this corresponds to the path
Thus, the number of paths from the upper left-hand corner of this grid to the lower right hand corner is $C(2+3,3) = C(5,3)$.
At this point, we'll introduce a new notation, ${n \choose r} = C(n,r)$, and by applying this argument to each monomial of the form $x^{5-i}y^i$, we get
\begin{equation*} (x+y)^5 = {5 \choose 0} \, x^5 y^0 + {5 \choose 1} \, x^4 y^1 + {5 \choose 2} \, x^3 y^2 + {5 \choose 3} \, x^2 y^3 + {5 \choose 4} \, x^1 y^4 + {5 \choose 5} \, x^0 y^5 \end{equation*}Generalizing this to arbitrary values of $5$, we get
Theorem 12.2 (The Binomial Theorem) For all natural numbers $n \gt 0$,
\begin{equation*} (x+y)^n = \sum_{i=0}^n {n \choose i} \, x^{n-i}y^i. \end{equation*}Example 12.3 What is the coefficient of $x^{20}y^3$ in $(x+y)^{23}$? Ans: ${23 \choose 20} = {23 \choose 3} = {23 \mult 22 \mult 21 \over 1 \mult 2 \mult 3} = 1,771$.
Example 12.4 What is the coefficient of $x^{10}y^4$ in $(x+2y)^{14}$? This is a bit different. If we apply the binomial theorem directly, we'll see that the $11$-th term will be ${14 \choose 10} x^{10} (2y)^4 = 2^4 {14 \choose 4} x^{10} y^4$ so the coefficient will be $2^4 {14 \choose 4} = 16,016$.
Binomial coefficients participate in an absurd number of identities, e.g.,
Theorem 12.5 For all natural numbers $n > 0$,
\begin{equation*} \sum_{i=0}^n {n \choose i} = 2^n. \end{equation*}Proof Consider the binomial $(1+1)^n$. We can evaluate this two different ways. If we use the binomial theorem, we get
\begin{equation*} \sum_{i=0}^n {n \choose i}1^{n-i}1^{i} = \sum_{i=0}^n {n \choose i} \end{equation*}whereas, if we simply compute use $1+1=2$, we can evaluate it as $2^n$. Equating these two values gives the desired result.
$\Box$ Theorem 12.5
We can apply much the same trick to evaluate the alternating sum of binomial coefficients:
Theorem 12.6 For all natural numbers $n \gt 0$,
\begin{equation*} \sum_{i=0}^n (-1)^i {n \choose i} = 0. \end{equation*}Proof In this case, consider $(1-1)^n$. Expanding this via the binomial theorem gives $\sum_{i=0}^n (-1)^i {n \choose i}$, whereas, using $1-1=0$, we get $0^n = 0$.
$\Box$ Theorem 12.6
Example 12.7 Theorem 12.6 isn't especially interesting in the case of odd $n$, cf., $n=3$ where we have
\begin{align*} {3 \choose 0} - {3 \choose 1} + {3 \choose 2} - {3 \choose 3} \\ &= 1 - 3 + 3 - 1 \\ &= 0 \end{align*}as we get to $0$ through the cancellation of equal binomial coefficients via ${n \choose i} - {n \choose n-i} = {n \choose i} - {n \choose i} = 0$, but it is more interesting the case of even $n$, cf.,
\begin{align*} {4 \choose 0} - {4 \choose 1} + {4 \choose 2} - {4 \choose 3} + {4 \choose 4} &= 1 - 4 + 6 - 4 + 1 \\ &= 8-8\\ &= 0 \end{align*}Indeed, building on this, we can use the binomial theorem to evaluate expressions like this:
Corollary 12.8 For all natural numbers $n \gt 0$,
\begin{equation*} \sum_{i=0}^n 2^i {n \choose i} = 3^n. \end{equation*}Proof Apply the binomial theorem, as before, to $(1+2)^n$.
$\Box$ Corollary 12.8
Exercise 12.9 Come up with a general formula for $\sum_{i=0}^n r^i {n \choose i}$, and check it in the specific cases $r = 3$, $n = 4$, and $r= -2$, $n=4$.
*Exercise 12.10 The binomial theorem doesn't require that $x$ and $y$ be integers. Indeed, it doesn't require that they even be real numbers. We can use Euler's Theorem ($e^{i \theta} = \cos \theta + i \sin \theta)$, where $e$ is the base of the natural logarithms, and $i = \sqrt{-1}$, together with the binomial theorem as above, to derive a number of trigonometric identities. E.g., if we consider $(e^{i \theta})^2$, we can evaluate it two different ways. First, we can multiply exponents, obtaining $e^{i \cdot 2 \theta}$ and then applying Euler's formula to get $\cos (2\theta) + i \sin (2\theta)$, or we can apply Euler's formula to the inside, obtaining $(\cos \theta + i \sin \theta)^2$, which we then evaluate via the binomial theorem:
\begin{align*} \cos (2\theta) + i \sin (2\theta) &= (\cos \theta + i \sin \theta)^2\\ &= \cos^2 \theta + 2 i \cos \theta \sin \theta + i^2 sin^2 \theta\\ &= \cos^2 \theta + 2 i \cos \theta \sin \theta - sin^2 \theta\\ \end{align*}Equating real and imaginary parts gives us
\begin{align*} \cos (2\theta) = \cos^2 \theta - \sin^2 \theta \\ \sin (2\theta) = 2 \cos \theta \sin \theta \end{align*}We can then rewrite the first of these identities, using $1 = \sin^2 \theta + \cos^2 \theta$ to get $\cos^2 \theta = 1 - \sin^2 \theta$, whence the familiar
\begin{align*} \cos (2\theta) = 1 - 2 \sin^2 \theta \\ \end{align*}Use this same approach to show $cos(3\theta) = 4 \cos^3 \theta - 3 \cos \theta$.
Perhaps the best known binomial coefficient identity is the following:
Theorem 12.11 (Pascal's identity) For all natural numbers $n \geq k \gt 0$,
\begin{align*} {n+1 \choose k} &= {n \choose k-1} + {n \choose k} \end{align*}Proof We give a combinatorial proof. Consider an $n+1$ element set $A$, a designated element $a$ of $A$, and a $k$-element subset $B$ of $A$. There are two disjoint possibilities: either $a \in B$, or $a\not\in B$. In the former case, $k-1$ elements of $B$ occur in $A \setminus \set{a}$; and in the latter, $k$ elements of $B$ occur in $A \setminus \set{a}$. This gives us two distinct ways to count $k$-elements subsets of $A$, either directly, obtaining $n+1 \choose k$, or indirectly, counting separately the $n \choose k-1$ elements that contain $a$, and the $n \choose k$ that don't.
$\Box$ Theorem 12.11
Theorem 12.11 is the basis of Pascal's Triangle, a celebrated arrangement of the binomial coefficients in rows:
Pascal's triangle is useful computationally as a way to compute an entire series of binomial coefficients for modest $n$.
Exercise 12.12 Give a direct algebraic proof of Theorem 12.11, using ${n \choose r} = {n! \over r! (n-r)!}$.
Exercise 12.13 Use Theorem 12.11 to give an inductive proof of the Binomial Theorem.
The following is a useful generalization of Pascal's identity:
Theorem 12.14 (Vandermonde's Identity) For all $n, m \geq r \gt 0$,
\begin{align*} {m+n \choose r} = \sum_{k=0}^r {m \choose r-k} {n \choose k}. \end{align*}Proof Let $A$ and $B$ be disjoint sets of cardinality $m$ and $n$ respectively. We can count the number of $r$ element subsets of $A \union B$ directly, obtaining $m+n\choose r$, or we can consider, for distinct $0 \leq k \leq r$ the number of ways to select $r-k$ elements from $A$, and $k$ elements from $B$.
$\Box$ Theorem 12.14
Vandermonde's Identity has a surprising special case:
Corollary 12.15 For all $n \gt 0$,
\begin{equation*} {2n \choose n} = \sum_{k=0}^n {n \choose k}^2 \end{equation*}Proof Set $m = r = n$ in Vandermonde's Identity to obtain
\begin{align*} {2n \choose n} = \sum_{k=0}^n {n \choose n-k} {n \choose k}. \end{align*}and then apply the identity
\begin{align*} {n \choose n-k} = {n \choose k}. \end{align*}$\Box$ Corollary 12.15
We will do one final binomial identity:
Theorem 12.16 Let $n \geq r \gt 0$. Then
\begin{align*} {n+1 \choose r+1} = \sum_{j = r}^n {j \choose r} \end{align*}Proof Again, a combinatorial interpretation gives an easy proof. Consider an $n+1$ element set $A$, upon which we impose an order, so that $a_1 \lt a_2 \lt \cdots \lt a_{n+1}$. Consider the $r+1$-element subsets $B$ of $A$. We can divide these into disjoint categories based on the index of the largest element they contain. The identity follows.
$\Box$ Theorem 12.16
Exercise 12.17 Give a combinatorial proof that, for all $r \leq k \leq n$,
\begin{equation*} {n \choose k} {k \choose r} = {n \choose r} {n-r \choose k-r}. \end{equation*}