6.4 Binomial Coefficients and Identities

Question 1

Binomial Expression:

Answer 1

Sum of 2 terms such as x + y.

terms can be products of constants or variables.

Question 2

Obtain Expansion of (x + y)^3 using combinatorial proof:

Answer 2

= (x + y)(x + y)(x + y)
when this is expanded, all products of a term in the
first sum, a term in the second sum, and a term in the third sum are added.

Terms of the form x^3,x^2y, xy^2, and y^3 arise.

To obtain a term of the form x3, an x must be chosen in each of the sums, andthis can be done in only one way.
Thus, the x^3 term in the product has a coefficient of 1. To obtain a term of the form x^2y, an x must be chosen in two of the three sums (and consequently a y in the other sum).
Hence, the number of such terms is the number of 2-combinations of three objects, namely,
(3
2).
Similarly, the number of terms of the form xy2 is the number of ways to pick one of the three
sums to obtain an x (and consequently take a y from each of the other two sums). This can be done in
(3
1) ways.
Finally, the only way to obtain a y3 term is to choose the y for each of the three sums
in the product, and this can be done in exactly one way.
Consequently, it follows that
(x + y)^3 = (x + y)(x + y)(x + y) = (xx + xy + yx + yy)(x + y)
= xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy
= x^3 + 3x^2y + 3xy^2 + y^3.

Question 3

Theorem 1:

THE BINOMIAL THEOREM

Answer 3

Let x and y be variables, and let n be a nonnegative integer.
Then

(x + y)^n = page 437

Question 4

Proof of the bionomial thm :

Answer 4

We use a combinatorial proof. The terms in the product when it is expanded are of the
form x^(n−j)y^j for j = 0, 1, 2, … , n. To count the number of terms of this form, note that to
obtain such a term it is necessary to choose n − j xs from the n binomial factors (so that the
other j terms in the product are ys). Therefore, the coefficient of x^(n−j)y^j is
( n
n−j), which is equal to
(n
j).
This proves the theorem.

Question 5

Corollary 1:

Sum of coefficients : and proof:

Answer 5

Let n be a nonnegative integer. Then
2^n = C(n,r)
where r goes from 0 to n.

1. Binomial them with x=1, y=1. (1 +1)^n = 2^n

OR

think of it as set with n elements has total 2^n subsets.
that’s the cardinality of Power set.

Question 6

Corollary 2:

Sum of coeffiecients of x - y:

look in book.

Answer 6

= 0
x = 1, y = -1.
so, (1 + (-1) )^n = 0^n

this implies sum of coefficients with odd r = Sum with even r.

Also, ways of picking subsets with even cardinality = ways of picking subsets with odd cardinality…?

Question 7

Corollary 3:

sum of coefficients * 2^k

Answer 7

= 3^n

Bionomial thm for x= 1, y = 2.

(1 + 2)^n = 3^n

Question 8

Pascal’s Identity :

Answer 8

Let n and k be positive integers with n ≥ k. Then

C ( n+1 , k) = C ( n , k-1 ) + C ( n , k )

Question 9

Proof of Pascal’s Identity :

Answer 9

We will use a combinatorial proof. Suppose that T is a set containing n + 1 elements. Let
a be an element in T, and let S = T − {a}. Note that there are
(n+1
k)
subsets of T containing k elements. However, a subset of T with k elements either contains a together with k − 1 elements
of S, or contains k elements of S and does not contain a. Because there are
( n
k−1) subsets of k − 1 elements of S, there are
( n
k−1)
subsets of k elements of T that contain a. And there are (n
k)
subsets of k elements of T that do not contain a, because there are
(n
k)
subsets of k elements of S.

Or algebrically as well.

Question 10

About recursive definition of Binomial Coefficients:

Answer 10

Pascal’s identity, together with the initial conditions
(n
0)=
(n
n) = 1 for all integers n,
can be used to recursively define binomial coefficients. This recursive definition is useful in the computation of binomial coefficients because only addition, and not multiplication, of integers
is needed to use this recursive definition.

Question 11

Pascals triangle :

Answer 11

Pascal’s identity shows that when two adjacent binomial coefficients in this triangle
are added, the binomial coefficient in the next row between these two coefficients is produced.

The nth row consists of binomial coefficients of C( n,k ), k = 0,1,….,n.

Question 12

VANDERMONDE’S IDENTITY

and its proof:

Answer 12

Let m, n, and r be nonnegative integers with r not exceeding either m or n. Then

C( m+n , r ) = ∑ C ( m , r-k ).C( n , k )
for k going from 0 to r.

Well consider two sets one with m elements and ither with n.
LHS has union of these and make ur way forward, wink.

Question 13

COROLLARY 4:

from VANDERMONDE’s Identity :

and proof:

Answer 13

If n is a nonnegative integer, then

C( 2n, n) = ∑( C( n,k) ) ^2
for k going from 0 to n.

Vandermonde's identity m=r = n
and C (n,k) = C(n, n-k )

Question 14

We can prove combinatorial identities by counting bit strings with different properties, as
the proof of Theorem 4 will demonstrate.

Proof:

Answer 14

Let n and r be nonnegative integers with r ≤ n. Then

C ( n+1, r+1 ) = ∑ C ( j, r)
j from r to n.

LHS = Bit string of n+1 length with r+1 1s.
We show that the RHS counts the same objects by considering the cases corresponding to the possible locations of the final 1 in a string with r + 1 ones. This final one must
occur at position r + 1, r + 2, … , or n + 1.
Furthermore, if the last one is the kth bit there must
be r ones among the first k − 1 positions. Consequently, there are
(k −1
r) such bit strings. Summing over k with r + 1 ≤ k ≤ n + 1, we find that there are
∑( k − 1 ,r ) = ∑ C ( j, r)
k runs from r+1 to n+1 and j runs from r to n
bit strings of length n containing exactly r + 1 ones. (Note that the last step follows from the
change of variables j = k − 1.) Because the left-hand side and the right-hand side count the
same objects, they are equal. This completes the proof.