Binomial Theorem

The Binomial Theorem states that the binomial coefficients \(C(n,k)\) serve as coefficients in the expansion of the powers of the binomial \(1+x\):

\(\displaystyle (1+x)^{n}=\sum_{k=0}^{n}C(n,k)x^{k}.\)

(Let me note in passing that there are multiple notations for the binomial coefficients: \(C(n,k)\), \(C_{k}^{n}\), \(^{n}C_{k}\), \(_{n}C_{k}\), \({n \choose k}\). For historical reasons, I choose \(C(n,m)\). I believe these are the notations that are used most consistently throughout this site.)

Observe that one of the interpretations of the Binomial Theorem is that \((1+x)^n\) is the generating function of the sequence \(C(n,k) ,\space k=0,1,\ldots ,n\).

Combinatorial Proof 1

\((1+x)^n\) is just a shorthand for the product of \(n\) monomials:

\((1+x)^{n}=(1+x)(1+x)\cdot\ldots\cdot (1+x).\)

On the right there is a polynomial, say \(P\), of degree \(n\). To obtain this polynomial we have to perform \(2^{n}\) multiplications each time choosing either \(1\) or \(x\) in each of the factors. The coefficient \([x^{k}]P\) by the term \(x^k\) is the number of ways to choose \(k\) \(x\)'s and, therefore, \(n-k\) \(1\)'s. This is exactly \(C(n,k)\).

Inductive Proof

There is nothing to proof for \(n=1\). Assume the theorem holds for \(n = m\) and let \(n=m+1\). As is common, I shall assume \(C(a,b)=0\), for \(b\lt 0\) and for \(b\gt n\). Using Pascal's Identity \(C(m+1,k)=C(m,k-1)+C(m,k)\),

\( \displaystyle \begin{array}{2,4} \sum_{k=0}^{m+1}C(m+1,k)x^{k} &= \sum_{k=0}^{m+1}(C(m,k-1)+C(m,k))x^{k} \\ &= x\sum_{k=0}^{m}C(m,k-1)x^{k-1}+\sum_{k=0}^{m}C(m,k)x^{k} \\ &= x(1+x)^{m} + (1+x)^{m} \\ &= (1+x)^{m+1}. \end{array} \)

Note that what we just shown admits a slightly different interpretation. If we denote \(\displaystyle S_{n}=\sum_{k=0}^{n}C(n,k)x^{k}\) then the above gives a recurrence relation for \(S_n\): \(S_{m+1}=xS_{m}+S_{m}=(1+x)S_{m}\), which leads to the same conclusion.

Combinatorial Proof 2

To prove that the two polynomials of degree \(n\) whose identity is asserted by the theorem, it will suffice to prove that they coincide at \(n\) distinct points. We shall actually show that they coincide for all \(x\in\mathbb{N}\).

Suppose that \(x\) is a positive integer, and let \(A\) be the set of all functions \(f:\space\{1,2,\ldots , n\}\rightarrow\{1,2,\ldots ,x,x+1\}\).

By the Product Rule of counting, the cardinality of \(A\) is \(|A|=(1+x)^n\).

Now count the elements of \(A\) in a different way. For \(0\le k\le n\), let \(A_k\) be the set of all functions that map exactly \(n-k\) elements onto the number \(x+1\); i.e.,

\(A_{k}=\{f\in A:\space |f^{-1}(x+1)|=n-k\}.\)

Then \(\displaystyle A=\cup_{k=0}^{n}A_{k}\), and the union is disjoint, so that \(\displaystyle |A|=\sum_{k=0}^{n}|A_{k}|\).

To count the elements of \(A_k\), choose a set \(Y\) of \(k\) elements from \(\{1,2,\ldots , n\}\) in \(C(n,k)\) ways. There are \(x^k\) functions \(Y\rightarrow \{1,2,\ldots , x\}\), and each such function gives an element of \(A_k\), by defining \(f(i)=x+1\), for \(i\in\{1,2,\ldots ,n\}\setminus Y\). Hence, \(|A_{k}|=C(n,k)x^k\), and the proof is complete.

Corollary

\(\displaystyle\sum_{k=0}^{n}C(n,k)=2^n\)

\(\displaystyle\sum_{k=0}^{n}(-1)^{k}C(n,k)=0\)

Proof

Substitute \(x=1\) and \(x=-1\) into \(\displaystyle (1+x)^{n}=\sum_{k=0}^{n}C(n,k)x^{k}.\)

Note that the second identity can be rewritten as \(\displaystyle\sum_{k=0}C(n,2k)=\sum_{k=0}C(n,2k+1)\).

References

  1. P. Hilton, D. Holton, J. Pederson, Mathematical Reflections, Springer Verlag, 1997
  2. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
  3. V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012

Pascal's Triangle and the Binomial Coefficients

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71492341