binomial theorem, proof of
Let a and b be commuting elements of some rig. Then
where the are binomial coefficients.
Each term in the expansion of 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 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 to a term in which the a factors precede all the b factors. This produces a term of the form for some k, where we use the expressions and to denote and respectively. For example, reducing the word yields , via the following reduction.
After performing this rewriting process, we collect like terms. Let us illustrate this with the case n = 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 , have the same normalization. But there are exactly such ab-words, since there are 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 term is , the coefficient of the term is , and that the coefficient of the term is . ∎