1.6 The Binomial Theorem
Consider the following problem: You have the integers Sn =
integer no larger than n.
How many ways are there to fill k
slots with these integers
starting from left to right if whenever an integer from Sn
has been used, it cannot be re
used in any succeeding slot?
This number is known as permutations of n things taken k at a time and is denoted by
It is easy to figure it out. There are n
choices for the first slot. For each choice
for the fist slot, there remain n −
1 choices for the second slot. Thus there are n
ways to fill the first two slots. Now there remain
2 ways to fill the third. Thus there
ways to fill the first three slots. Continuing this way, you see there
ways to do this. Note there are k factors in the above product.
Now define for k a positive integer,
This is called k factorial. Thus P
! and you should verify that
Now consider the number of ways of selecting a set of k different numbers from Sn. For
each set of k numbers there are P
! ways of listing these numbers in order.
Therefore, denoting by
the number of ways of selecting a set of
it must be the case that
How many ways are there to select no numbers from Sn? Obviously one way. Note that
the above formula gives the right answer in this case as well as in all other cases due to
the definition which says 0! = 1.
Now consider the problem of writing a formula for
is a positive
integer. Imagine writing it like this:
Then you know the result will be sums of terms of the form akxkyn−k. What is ak? In
other words, how many ways can you pick x from k of the factors above and
y from the other n − k. There are n factors so the number of ways to do it
Therefore, ak is the above formula and so this proves the following important theorem
known as the binomial theorem.
Theorem 1.6.1 The following formula holds for any n a positive integer.