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
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