Binomial Theorem by InductionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/