Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Binomial Theorem

The Binomial Theorem states that the kth term of (x+y)n is C(n,k)xn-kyk, where C(n,k) is defined as n!/((n-k)!k!).  These terms are given by the binomial triangle,

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1
1   6  15  20  15   6   1

                C(0,0)
            C(1,0)  C(1,1)
        C(2,0)  C(2,1)  C(2,2)
    C(3,0)  C(3,1)  C(3,2)  C(3,3)
C(4,0)  C(4,1)  C(4,2)  C(4,3)  C(4,4)

Each number is the sum of the two numbers above it, (except the 1's on the edges).  To prove this recursively, I just need to show that C(n+1,k+1)=C(n,k)+C(n,k+1).

C(n+1,k+1) =
(n+1)!/((n-k)!(k+1)!) =
(k+1+n-k)n!/((n-k)!(k+1)!) =
(k+1)n!/((n-k)!(k+1)!) + (n-k)n!/((n-k)!(k+1)!) =
(k+1)n!/((n-k)!(k+1)k!) + (n-k)n!/((n-k)(n-k-1)!(k+1)!) =
n!/((n-k)!k!) + n!/(n-k-1)!(k+1)!) =
n!/((n-k)!k!) + n!/((n-(k+1))!(k+1)!) =
C(n,k) + C(n,k+1)

Do you see why (x+y)n is the sum(k=0 to n) of C(n,k)xn-kyk?  I can show that recursively, too, but I'll start instead with an example:

Pick any row of the binomial triangle  -- the 3rd row (counting from zero), for example -- and assume the coefficients of the expansion of (x+y)n is C(n,k)xn-kyk.  In other words,

(x+y)3 = 1x3 + 3x2y + 3xy2 + 1y3.

(x+y)4 = (x+y)(1x3 + 3x2y + 3xy2 + 1y3)

= (x)(1x3 + 3x2y + 3xy2 + 1y3)
+ (y)(1x3 + 3x2y + 3xy2 + 1y3)

= (1x4 + 3x3y + 3x2y2 + 1xy3)
         + (1x3y + 3x2y2 + 3xy3 + 1y4)

= (1x4 + 4x3y + 6x2y2 + 4xy3 + 1xy3)

As you can see, the coefficients of (x+y)4 come from the sum of pairs of the coefficients of (x+y)3, just as in the binomial triangle.  This is true for all n.  Well, this wasn't a proof per se, but you can see how this explanation could be whipped into a proof fairly easily.

Internet references

Mathworld: Binomial Theorem

Related pages in this website

Combination identities


The webmaster and author of this Math Help site is Graeme McRae.