# 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