Pascal's Formula
The Binomial Theorem and Binomial Expansions
Pascal's Triangle
_{}nC_{r} has a mathematical formula: _{n}C_{r} = 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
Example 6.6.5 Deriving New Formulas from Pascal's Formula
Use Pascal's formula to derive a formula for _{n} +2C_{r} in terms of _{n}C_{r}, _{n}C_{r} - 1, _{n}C_{r} - 2, where n and r are nonnegative integers and 2 £ r £ n.
Solution: By Pascal's formula,
_{}n +2C_{r} = _{n + 1}C_{r - 1} + _{n }+ 1C_{r}.
Applying Pascal's formula again to each term on the right hand side (RHS) of this equation,
_{}n +2C_{r} = _{n}C_{r - 2} + _{n}C_{r} - 1 + _{n}C_{r - 1} + _{n}C_{r},
for all nonnegative integers n and r such that 2 £ r £ n + 2.
Use this formula and Pascal's Triangle to verify that _{5}C_{3} = 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:
In each expansion, there are n + 1 terms.
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.
The sum of the powers of each term is n.
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
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. , 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
for all integers n ³
0.
Solution: Since 2 = (1 + 1) and 2n = (1 + 1)n, apply the binomial theorem to this expression.
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 :
by Example 6.7.3. QED [quod erat demonstrandum (which was to be demonstrated)]
document.write(" Page last updated: "+document.lastModified)
}