Binomial Theorem by Induction

Date: 7/14/96 at 10:26:5
From: Scott Turner
Subject: Binomial Theorem by Induction

I'm trying to prove the Binomial Theorem by Induction. 
So (x+y)^n = the sum of as the series goes from j=0 to n, 
(n choose j)x^(n-j)y^j.

Okay the base case is simple.  We assume if it's true for n to derive 
it's true for n+1.

I've written out what the series looks like for n.  Then I write out 
what it looks like for n+1, hoping I can apply the Pascal Identity to 
end up with (x+y)^n (x+y) which equals (x+y)^n+1.  But I can't. I'm 
thinking there must be some "trick" that I'm not seeing.

Thanks.
ST

Date: 7/14/96 at 18:54:39
From: Doctor Anthony
Subject: Re: Binomial Theorem by Induction

To prove the binomial theorem by induction we use the fact that 
nCr + nC(r+1) = (n+1)C(r+1)

We can see the binomial expansion of (1+x)^n is true for n = 1.

Assume it is true for
(1+x)^n = 1 + nC1*x + nC2*x^2 + ....+ nCr*x^r + nC(r+1)*x^(r+1) + ...

Now multiply by (1+x) and find the new coefficient of x^(r+1).  We get 
it by multiplying x by nCr*x^r and also by multiplying 1 by nC(r+1)*x^
(r+1).  So coefficient of x^(r+1) will be 

  nCr + nC(r+1) = (n+1)C(r+1)

Thus (1+x)^(n+1) = 1 + (n+1)C1*x + .... +(n+1)C(r+1)x^(r+1) + ...

and this is the same series as before with n replaced by n+1 (and an 
extra term x^(n+1))  So if the series was correct for n, then it is 
also true for n+1.  But it is true for n = 1, therefore for n = 2, 
therefore for n = 3, and so on to all positive, integral values of n.

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 7/14/96 at 23:4:4
From: Scott Turner
Subject: Binomial Theorem by Induction

Doctor Anthony tried to help me with this problem but I'm afraid I 
don't understand.  He says that "n choose r" + "n choose r+1" is equal 
to "n+1 choose r+1".  How is that so? Pascal's Theorem?

Also, the binomial theorem results in (x+y)^n, which I try to prove 
for (x+y)^n+1.  The Doctor's hints are all about (x+1).  Where is y?

I really do appreciate your further help.

ST

Date: 7/15/96 at 0:15:27
From: Doctor Pete
Subject: Re: Binomial Theorem by Induction

I've looked over the information so far.  I will introduce a slightly
different notation for the binomial coefficient:  Let "n choose r," or 
nCr, be written as C(n,r).  Now, let's address your first question, 
which is to show that

     C(n,r) + C(n,r+1) = C(n+1,r+1) .

To do this, we must appeal to the definition of C(n,r), which is the 
number of combinations of n objects taken r at a time.

                  n!
     C(n,r) = --------- .
              (n-r)! r!

Therefore,

                             n!             n!
     C(n,r) + C(n,r+1) = --------- + ---------------
                         (n-r)! r!   (n-r-1)! (r+1)!

                           n! (r+1)        n! (n-r)
                       = ------------- + -------------
                         (n-r)! (r+1)!   (n-r)! (r+1)!

                          n! (n-r+r+1)
                       = -------------
                         (n-r)! (r+1)!

                               (n+1)!
                       = -------------------
                         (n+1-(r+1))! (r+1)!

                       = C(n+1,r+1) .


As for your second question, notice that the central part of Dr. 
Anthony's proof is showing that the coefficients "transfer over" into 
the next case, using the fact we just proved above in response to your 
first question. The use of (x+1)^n as opposed to (x+y)^n doesn't make 
too much of a difference, as it is easy to generalize and replace the 
"1" with "y."  For concreteness, however, we'll do this:

         (x+y)^n = Sum[C(n,k) x^k y^(n-k), {k,0,n}]
  => (x+y)^(n+1) = (x+y)Sum[C(n,k) x^k y^(n-k), {k,0,n}]
                 = Sum[C(n,k) x^(k+1) y^(n-k), {k,0,n}]
                   + Sum[C(n,k) x^k y^(n-k+1), {k,0,n}]
                 = Sum[C(n,k) x^(k+1) y^(n-k), {k,0,n}]
                   + Sum[C(n,k+1) x^(k+1) y^(n-k), {k,-1,n-1}]
                 = Sum[C(n,k) x^(k+1) y^(n-k), {k,0,n-1}]
                   + C(n,n) x^(n+1) y^0 + C(n,0) x^0 y^(n+1)
                   + Sum[C(n,k+1) x^(k+1) y^(n-k), {k,0,n-1}]
                 = Sum[(C(n,k)+C(n,k+1)) x^(k+1) y^(n-k), {k,0,n-1}]
                   + x^(n+1) + y^(n+1)
                 = Sum[C(n+1,k+1) x^(k+1) y^(n-k), {k,0,n-1}]
                   + x^(n+1) + y^(n+1)
                 = Sum[C(n+1,k) x^k y^(n+1-k), {k,1,n}] + x^(n+1) 
				   + y^(n+1)
                 = Sum[C(n+1,k) x^k y^(n+1-k), {k,0,n+1}] .

Thus, our statement is true from the induction hypothesis (i.e., the
assumption that (x+y)^n = Sum[C(n,k) x^k y^(n-k), {k,0,n}]. (I hope 
this wasn't too difficult to follow.... For example, Sum[k, {k,0,n}] 
means "the sum of k from k=0 to k=n." There's a lot of subtle sum 
manipulation, but I prefer to do it this way rather than writing out 
things like "C(n,0) x^0 y^n + C(n,1) x^1 y^(n-1) + ...", because it's 
more rigorous.)

I hope this clears things up.

-Doctor Pete,  The Math Forum 
 Check out our web site!  http://mathforum.org/dr.math/