The Binomial Theorem states that the k^th term of (x+y)ⁿ is C(n,k)x^n-ky^k, 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)ⁿ is the sum(k=0 to n) of C(n,k)x^n-ky^k?  I can show that recursively, too, but I'll start instead with an example:

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

(x+y)³ = 1x³ + 3x²y + 3xy² + 1y³.

(x+y)⁴ = (x+y)(1x³ + 3x²y + 3xy² + 1y³)

= (x)(1x³ + 3x²y + 3xy² + 1y³)
+ (y)(1x³ + 3x²y + 3xy² + 1y³)

= (1x⁴ + 3x³y + 3x²y² + 1xy³)
         + (1x³y + 3x²y² + 3xy³ + 1y⁴)

= (1x⁴ + 4x³y + 6x²y² + 4xy³ + 1xy³)

As you can see, the coefficients of (x+y)⁴ come from the sum of pairs of the coefficients of (x+y)³, 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.