Pascal's Formula
The Binomial Theorem and Binomial Expansions

Pascal's Triangle

nCr has a mathematical formula: nCr = n! / ((n - r)!r!), see Theorem 6.4.1. Your calculator probably has a function to calculate binomial coefficients as well. But for small values the easiest way to determine the value of several consecutive binomial coefficients is with Pascal's Triangle:

n = 0

1

n = 1

1   1

n = 2

1   2   1

n = 3

1   3   3   1

n = 4

1   4   6   4   1

n = 5

1   5   10   10   5   1

Note the symmetry, aside from the beginning and ending 1's each term is the sum of the two terms above.

Consider again Pascal's Triangle in which each number is obtained as the sum of the two neighboring numbers in the preceding row. The way the entries are constructed in the table give rise to Pascal's Formula:

Theorem 6.6.1 Pascal's Formula top
Let n and r be positive integers and suppose r £ n. Then

Pascal's Fromula

Example 6.6.5 Deriving New Formulas from Pascal's Formula
Use Pascal's formula to derive a formula for n +2Cr in terms of nCr, nCr - 1, nCr - 2, where n and r are nonnegative integers and 2 £ r £ n.
Solution: By Pascal's formula,

n +2Cr = n + 1Cr - 1 + n + 1Cr.

Applying Pascal's formula again to each term on the right hand side (RHS) of this equation,

n +2Cr = nCr - 2 + nCr - 1 + nCr - 1 + nCr,

for all nonnegative integers n and r such that 2 £ r £ n + 2.
Use this formula and Pascal's Triangle to verify that 5C3 = 10.

5C3 = 3C1 + 2(3C2) + 3C3

5C3 = 3 + 2(3) + 1 = 10.

Can we use this new formula to calculate 5C4?

Now use this formula to calculate the value of 7C5.

7C5 = 5C3 + 2(5C4) + 5C5

7C5 = 10 + 2(5) + 1 = 21.

A binomial is a polynomial that has two terms. A quick method of raising a binomial to a power can be learned just by looking at the patterns associated with binomial expansions. To begin, we look at the expansion of (x + y)n for several values of n.

(x + y)0 = 1

(x + y)1 = x + y

(x + y)2 = x2 + 2xy + y2

(x + y)3 = x3 + 3x2y + 3xy2 + y3

(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4

(x + y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5

We can make several observations:

  1. In each expansion, there are n + 1 terms.
  2. In each expansion, x and y have symmetric roles. The powers of x decrease by 1 in successive terms, whereas the powers of y increase by 1.
  3. The sum of the powers of each term is n.
  4. The binomial coefficients, nCr, where r is the exponent of the second term, are symmetrical:
    5C1 = 5C4 = 5, 5C2 = 5C3 = 10.

Try it. (x + c)3 = x3 + 3x2c + 3xc2 + c3 as opposed to the more tedious method of long hand:

 

 

 

 

 

 

 

x

+

c

 

 

 

 

 

 

*

x

+

c

 

 

 

 

 

 

 

------------------------

 

 

 

 

 

 

 

 

cx

c2

 

 

 

 

 

 

+

x2

xc

 

 

 

 

 

 

 

 

------------------------

 

 

 

 

 

 

 

x2

2xc

c2

 

 

 

 

 

 

*

x

+

c

 

 

 

 

 

 

-------------------------------

 

 

 

 

 

 

 

x2c

2xc2

c3

 

 

 

 

 

+

x3

2x2c

xc2

 

 

 

 

 

 

 

-------------------------------

 

 

 

 

 

 

x3 + 3x2c + 3xc2 + c3

 

The binomial expansion of a difference is as easy, just alternate the signs.
(x - y)3 = x3 - 3x2y + 3xy2 - y3.

In general the expansion of the binomial (x + y)n is given by the Binomial Theorem.
Theorem 6.7.1 The Binomial Theorem top

Binomial Theorem

 Can you see just how this formula alternates the signs for the expansion of a difference?

Example 6.7.1 Substituting into the Binomial Theorem
Expand the following expressions using the binomial theorem:
a. (a + b)5
b. (x - 4y)4.
Solution a.

(a + b)^5,

substituting in the values for the binomial coefficients from Pascal's Triangle we have

(a + b)5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5.

Solution b.
Given that for n = 4 the coefficients are 1, 4, 6, 4, 1 we have

(x - 4y)4 = x4 + 4x3(-4y) + 6x2(-4y)2 + 4x(-4y)3 + (-4y)4

(x - 4y)4 = x4 - 16x3y + 6(16)x2y2 - 4(64)xy3 + 256y4

(x - 4y)4 = x4 - 16x3y + 96x2y2 - 256xy3 + 256y4.

Example 6.7.3 Deriving Another Combinatorial Identity from the Binomial Theorem
Use the Binomial theorem to show that

Sigma(n choose r) = 2^n

for all integers n ³ 0.

Solution: Since 2 = (1 + 1) and 2n = (1 + 1)n, apply the binomial theorem to this expression.

2^n proof

since 1n - r = 1 and 1r = 1.

Number of Subsets of a Set
Theorem 5.3.6 For all integers n ³ 0, if a set X has n elements then the Power Set of X, denoted P(X), has 2n elements.
Proof: Suppose S is a set with n elements. Then every subset of S has some number of elements k, where k is between 0 and n. It follows that the total number of subsets of S, the cardinality of the power set of S, can be expressed as the following sum:

 

Number of
subsets of
S


=

Number of
subsets of
size 0


+

Number of
subsets of
size 1


+


…


+

Number of
subsets of
size n

Now the number of subsets of size k of a set with n elements is nCk . Hence the number of subsets of S :

Cardinality of a Power Set

by Example 6.7.3. QED [quod erat demonstrandum (which was to be demonstrated)]