binomial theorem, proof of


Proposition.

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

(a+b)n=k=0n(nk)akbn-k,

where the (nk) are binomial coefficientsMathworldPlanetmath.

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 sequenceMathworldPlanetmath 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 bnaabn to a term in which the a factors precede all the b factors. This produces a term of the form akbn-k for some k, where we use the expressions a0bn and anb0 to denote bn and an respectively. For example, reducing the word babab2aba yields a4b5, via the following reduction.

babab2abaababab2aba2babab3a3bab4a4b5.

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
=a3+a2b+a2b+ab2+a2b+ab2+ab2+b3
=a3+3a2b+3ab2+b3.

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 0kn, have the same normalization. But there are exactly (nk) such ab-words, since there are (nk) 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 an term is (n0)=1, the coefficient of the bn term is (nn)=1, and that the coefficient of the akbn-k term is (nk). ∎

Title binomial theoremMathworldPlanetmath, 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