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^na\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^2aba$ yields $a^4 b^5$ , via the following reduction. $$ babab^2aba \mapsto a ba ba b^2a b \mapsto a^2babab^3 \mapsto a^3bab^4 \mapsto a^4b^5. $$ 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 $0\le k\le 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}$ .