In this section, we will learn an expansion formula of \((x+y)^n\) for any positive integer \(n\). For example, consider the fifth power of the binomial \(x+y\): \[(x+y)^5=(x+y)(x+y)(x+y)(x+y)(x+y).\] The terms in the expansion of the above are \(x^{5-k}y^k\) for \(k=0,1,2,3,4,5\). Now we have to figure out the coefficient of \(x^{5-k}y^k\) by counting the number of times it appears in the expansion. We get \(x^{5-k}y^k\) by choosing \(y\) from \(k\) factors (and \(x\) from the rest \(5-k\) factors) which can be done in \(\displaystyle\binom{5}{k}\) ways. Then the coefficient of \(x^{5-k}y^k\) in the expansion of \((x+y)^5\) is \(\displaystyle\binom{5}{k}\) which is called a binomial coefficient. Thus \[\begin{eqnarray*} (x+y)^5 &=& \binom{5}{0}x^5y^0+\binom{5}{1}x^{4}y^1+\binom{5}{2}x^3y^2+\binom{5}{3}x^2y^3+\binom{5}{4}x^1y^4+\binom{5}{5}x^0y^5\\ &=& x^5+5x^{4}y+10x^3y^2+10x^2y^3+5xy^4+y^5. \end{eqnarray*}\]

Theorem (The binomial theorem). Let \(n\) be a positive integer and \(x\) and \(y\) be variables. Then \[(x+y)^n=\sum_{k=0}^n \binom{n}{k}x^{n-k}y^k =\binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\binom{n}{2}x^{n-2}y^2+\cdots +\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n.\] Corollary. From the binomial theorem, we have the following:

1. \((1+x)^n=\displaystyle\sum_{k=0}^n \binom{n}{k}x^k\) (obtained by plugging \(x=1\) and \(y=x\)).


2. \(\displaystyle\sum_{k=0}^n \binom{n}{k}=2^n\) (obtained by plugging \(x=y=1\)).


3. \(\displaystyle\sum_{k=0}^n (-1)^k\binom{n}{k}=0\) (obtained by plugging \(x=1\) and \(y=-1\)).

Example.

1. How many terms are there in the expansion of \(\left(x^2-\frac{1}{x} \right)^{50}\)?


2. What is the coefficient of \(x^{11}\) in the expansion of \(\left(x^2-\frac{1}{x} \right)^{61}\)?

Solution.

1. By the binomial theorem, there are 51 terms in the expansion of \(\left(x^2-\frac{1}{x} \right)^{50}\).


2. Suppose the \((k+1)\)th term of the expansion of \(\left(x^2-\frac{1}{x} \right)^{61}\) contains \(x^{11}\). The \((k+1)\)th term is \[\binom{61}{k}(x^2)^{61-k}\left( -\frac{1}{x} \right)^k =(-1)^k \binom{61}{k} x^{122-3k}.\] Since the \((k+1)\)th term contains \(x^{11}\), \[ x^{122-3k}=x^{11} \implies 122-3k=11 \implies k=37.\] Thus the coefficient of \(x^{11}\) in the expansion of \(\left(x^2-\frac{1}{x} \right)^{61}\) is \[(-1)^{37} \binom{61}{37}=-\binom{61}{37}.\]

Definition (Combinatorial proof). A combinatorial proof is a proof of an identity by counting the same objects in two different ways.

Example. Let \(n\) be a positive integer. Provide a combinatorial proof of the following identity: \[\sum_{k=0}^n \binom{n}{k}=2^n\] Solution. Let \(S=\{x_1,x_2,\ldots,x_n\}\). We prove the identity by counting \(|\mathcal P(S)|\), the number of subsets of \(S\) in two different ways.
There are \(\displaystyle\binom{n}{k}\) subsets of \(S\) with \(k\) elements for \(k=0,1,2,\ldots,n\). Then \[|\mathcal P(S)|=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=\sum_{k=0}^n \binom{n}{k}.\] To count \(|\mathcal P(S)|\) differently, note that a subset \(T\) of \(S\) corresponds to bit string \((a_1,a_2,\ldots,a_n)\) such that \(a_i=1\) when \(x_i\in T\) and \(a_i=0\) when \(x_i\notin T\). For example, \((0,1,1,0,\ldots,0)\) corresponds to \(\{x_2,x_3\}\). Because of this one-to-one correspondence between subsets of \(S\) and bit strings of length \(n\), \[\begin{eqnarray*} |\mathcal P(S)|&=&|\{(a_1,a_2,\ldots,a_n)\;|\;a_i\in \{0,1\}\}|\\ &=&|\{0,1\}\times \{0,1\} \times\cdots\times \{0,1\}|\\ &=&|\{0,1\}|^n \; (\text{by the product rule})\\ &=&2^n. \end{eqnarray*}\] Thus \[\sum_{k=0}^n \binom{n}{k}=2^n.\] Example. Let \(n\) and \(k\) be positive integers and \(k\leq n\). Provide (a) a direct proof and (b) a combinatorial proof of the Pascal's identity: \[\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}\] Solution.

1. Direct proof. \[\begin{eqnarray*} \binom{n}{k-1}+\binom{n}{k}&=& \frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!} \\ &=& \frac{n!}{(k-1)!(n-k+1)\cdot (n-k)!}+\frac{n!}{k\cdot (k-1)!(n-k)!} \\ &=& \frac{n!}{(k-1)! (n-k)!}\left[ \frac{1}{n-k+1}+\frac{1}{k} \right] \\ &=& \frac{n!}{(k-1)! (n-k)!} \cdot\frac{n+1}{(n-k+1)k} \\ &=& \frac{(n+1)!}{k!(n-k+1)!} \\ &=& \binom{n+1}{k} \end{eqnarray*}\]
2. Combinatorial proof. Let \(S=\{a_1,a_2,\ldots,a_n,a_{n+1}\}\) and \(T=S\setminus \{a_{n+1}\}=\{a_1,a_2,\ldots,a_n\}\). We prove the identity by counting the number of subsets of \(S\) with \(k\) elements in two different ways. There are \(\displaystyle\binom{n+1}{k}\) subsets of \(S\) with \(k\) elements. To count it differently, note that there are two types of \(k\)-element subsets of \(S\):
   
   
   1. \(k\)-element subsets of \(S\) containing \(a_{n+1}\): These subsets consist of \(a_{n+1}\) and \(k-1\) elements from \(T=\{a_1,a_2,\ldots,a_n\}\). Since there \(\displaystyle\binom{n}{k-1}\) ways to choose \(k-1\) elements from \(T\), the number of these subsets is \(\displaystyle\binom{n}{k-1}\).
   
   
   2. \(k\)-element subsets of \(S\) not containing \(a_{n+1}\): These subsets consist of \(k\) elements from \(T=\{a_1,a_2,\ldots,a_n\}\). Since there \(\displaystyle\binom{n}{k}\) ways to choose \(k\) elements from \(T\), the number of these subsets is \(\displaystyle\binom{n}{k}\).
   Thus the number of \(k\)-element subsets of \(S\) is \(\displaystyle\binom{n}{k-1}+\binom{n}{k}\) and consequently \[\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}.\]

Two well-known identities involving binomial coefficients:

1. Vandermonde's identity: For any nonnegative integers \(m,n,r\) where \(r\leq m,n\), \[\binom{m+n}{r}=\sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}.\] Plugging \(m=r=n\) in Vandermonde's identity, we have \[\binom{2n}{n}=\sum_{k=0}^n \binom{n}{k}^2.\]


2. The hockey-stick or Christmas stocking identity: For any nonnegative integers \(m,n,r\) where \(r\leq n\), \[\binom{n+1}{r+1}=\sum_{k=r}^n \binom{k}{r}.\] The name of this identity makes sense from its visualization from Pascal's triangle.

Pascal's triangle: For each nonnegative integer \(n\), the \(n\)th row of Pascal's triangle is the following. \[\binom{n}{0}\;\;\binom{n}{1}\;\;\binom{n}{2}\cdots \binom{n}{n}\] Note that the top row (zeroth row) of Pascal's triangle consists of \(\displaystyle\binom{0}{0}\) which is defined to be \(1\). For \(n\geq 2\), the middle \(n-1\) entries of the \(n\)th row of Pascal's triangle can be obtained from \((n-1)\)th row using Pascal's identity. \[\begin{array}{lccccccccccc} n=0\hspace{12pt}& & & & & & 1 & & & & & \cr n=1& & & & & 1 & & 1 & & & & \cr n=2& & & & 1 & & 2 & & 1 & & & \cr n=3& & & 1 & & 3 & & 3 & & 1 & & \cr n=4& & 1 & & 4 & & 6 & & 4 & & 1 & \cr n=5& 1 & & 5 & & 10 & & 10 & & 5 & & 1 \cr \end{array}\] \[\hspace{48pt}\text{The first six rows of Pascal's triangle}\]

Last edited