Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Discrete Mathematics
High School Polynomials

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/