# binomial theorem, proof of

###### Proposition.

Let a and b be commuting elements of some rig. Then

 $(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k},$

where the $\binom{n}{k}$ are binomial coefficients.

###### Proof.

Each term in the expansion of $(a+b)^{n}$ is obtained by making n decisions of whether to use a or b as a factor. Moreover, any sequence of n such decisions yields a term in the expansion. So the expandsion of $(a+b)^{n}$ is precisely the sum of all the ab-words of length n, where each word appears exactly once.

Since a and b commute, we can reduce each term via rewrite rules of the form $b^{n}a\mapsto ab^{n}$ to a term in which the a factors precede all the b factors. This produces a term of the form $a^{k}b^{n-k}$ for some k, where we use the expressions $a^{0}b^{n}$ and $a^{n}b^{0}$ to denote $b^{n}$ and $a^{n}$ respectively. For example, reducing the word $babab^{2}aba$ yields $a^{4}b^{5}$, via the following reduction.

 $babab^{2}aba\mapsto ababab^{2}ab\mapsto a^{2}babab^{3}\mapsto a^{3}bab^{4}% \mapsto a^{4}b^{5}.$

After performing this rewriting process, we collect like terms. Let us illustrate this with the case n = 3.

 $\displaystyle(a+b)^{3}$ $\displaystyle=aaa+aab+aba+abb+baa+bab+bba+bbb$ $\displaystyle=a^{3}+a^{2}b+a^{2}b+ab^{2}+a^{2}b+ab^{2}+ab^{2}+b^{3}$ $\displaystyle=a^{3}+3a^{2}b+3ab^{2}+b^{3}.$

To determine the coefficient of a reduced term, it suffices to determine how many ab-words have that reduction. Since reducing a term only changes the positions of as and bs and not their number, all the ab-words where k of the letters are bs and n-k are as, for $0\leq k\leq n$, have the same normalization. But there are exactly $\binom{n}{k}$ such ab-words, since there are $\binom{n}{k}$ ways to select k positions out of n to place as in an ab-word of length n. This shows that the coefficient of the $a^{n}$ term is $\binom{n}{0}=1$, the coefficient of the $b^{n}$ term is $\binom{n}{n}=1$, and that the coefficient of the $a^{k}b^{n-k}$ term is $\binom{n}{k}$. ∎

Title binomial theorem, proof of BinomialTheoremProofOf 2013-03-22 15:03:54 2013-03-22 15:03:54 mps (409) mps (409) 15 mps (409) Proof msc 11B65