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 ndecisions 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 theab-words of length n, where each word appears exactly once.

Since a and b commute, we can reduce each term via rewriterules of the form $b^{n}a\\mapsto ab^{n}$ to a term in which the afactors precede all the b factors. This produces a term of theform $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. Forexample, reducing the word $babab^{2}aba$ yields $a^{4}b^{5}$ , via thefollowing 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. Letus 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 todetermine how many ab-words have that reduction. Since reducinga term only changes the positions of as and bs and not theirnumber, all the ab-words where k of the letters are bsand n-k are as, for $0\\leq k\\leq n$ , have the samenormalization. But there are exactly $\\binom{n}{k}$ suchab-words, since there are $\\binom{n}{k}$ ways to select kpositions out of n to place as in an ab-word of lengthn. 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}$ termis $\\binom{n}{k}$ .∎