# binomial theorem, proof of

###### Proposition.

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

$${(a+b)}^{n}=\sum _{k=0}^{n}\left(\genfrac{}{}{0pt}{}{n}{k}\right){a}^{k}{b}^{n-k},$$ |

where the $\mathrm{\left(}\genfrac{}{}{0pt}{}{n}{k}\mathrm{\right)}$ 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 a{b}^{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 $baba{b}^{2}aba$ yields ${a}^{4}{b}^{5}$, via the following reduction.

$$baba{b}^{2}aba\mapsto ababa{b}^{2}ab\mapsto {a}^{2}baba{b}^{3}\mapsto {a}^{3}ba{b}^{4}\mapsto {a}^{4}{b}^{5}.$$ |

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

${(a+b)}^{3}$ | $=aaa+aab+aba+abb+baa+bab+bba+bbb$ | ||

$={a}^{3}+{a}^{2}b+{a}^{2}b+a{b}^{2}+{a}^{2}b+a{b}^{2}+a{b}^{2}+{b}^{3}$ | |||

$={a}^{3}+3{a}^{2}b+3a{b}^{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\le k\le n$, have the same normalization. But there are exactly $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ such ab-words, since there are $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ 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 $\left(\genfrac{}{}{0pt}{}{n}{0}\right)=1$, the coefficient of the ${b}^{n}$ term is $\left(\genfrac{}{}{0pt}{}{n}{n}\right)=1$, and that the coefficient of the ${a}^{k}{b}^{n-k}$ term is $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$. ∎

Title | binomial theorem^{}, proof of |
---|---|

Canonical name | BinomialTheoremProofOf |

Date of creation | 2013-03-22 15:03:54 |

Last modified on | 2013-03-22 15:03:54 |

Owner | mps (409) |

Last modified by | mps (409) |

Numerical id | 15 |

Author | mps (409) |

Entry type | Proof |

Classification | msc 11B65 |