Chapter 11

Some Useful Identities

We gave four simple identities involving binomial coefficients, namely (10.2) -(10.5), in Chapter 10. In this chapter, we shall derive some more identities involving binomial coefficients from (BT). These identities, while interesting in their own right, are also useful in simplifying certain algebraic expressions.

Consider the expansion of (1 + x)ⁿ in (BT). If we let x = 1, we then obtain from (BT) the following

Example 11.1 In Example 5.2, we discussedi a counting problem on P(S), the set of all subsets of a finite set S. If S is an n-element set (i.e. |S| = n), it can be shown (see Problem 5.4) by establishing a bijection between P(S) and the set of n-digit binary sequences that there are exactly 2ⁿ subsets of S inclusive of the empty set and the set S itself (i.e. |P(S)| = 2ⁿ). We can now (give a more natural proof for this fact. Assume that |S| = n. By definition, the number of

Thus,

Example 11.2 The number 4 can be expressed as a sum of one or more positive integers, taking order into account, in the following 8 ways:

Show that every natural number n can be so expressed in 2^n–1 ways.

Solution This is in fact Problem 5.6. Let us see how (B1) can be used to prove the result. But first of all, consider the special case above when n = 4.

We write 4 = 1 + 1 + 1 + 1 and note that there are three “+”s in the expression. Look at the following relation.

This correspondence is actually a bijection between the set of all such expressions of 4 and the set of all subsets of three “+”s. Thus, by (BP) and (B1), the required answer is

In general, write

and note that there are n – 1 “+”s in the above expression. We now extend the above technique by establishing a bijection between the set of all such expressions of n and the set of all subsets of n – 1 “+”s. Thus, by (BP) and (B1), the number of all such expressions of n is

Consider again the expansion of (1 + x)ⁿ in (BT). If we now let x = –1, we then have

where the terms on the LHS alternate in sign. Thus, if n is even, say n = 2k, then

and if n is odd, say n = 2k + 1, then

As

by (B1), we have:

Example 11.3 A finite set S is said to be “even” (“odd”) if |S| is even (odd). Consider ₈ = {1,2,...,8}. How many even (odd) subsets does ₈ have?

Solution The number of even subsets of ₈ is

and the number of odd subsets of ₈ is

By (B2)

Consider the following binomial expansion once again:

If we treat the expressions on both sides as functions of x, and differentiate them with respect to x, we obtain:

By letting x = 1 in the above identity, we have:

Let us try to derive (B3) by a different way. Consider the following problem. Suppose that there are n(n ≥ 1) people in a group, and they wish to form a committee consisting of people from the group, including the selection of a leader for the committee. In how many ways can this be done?

Let us illustrate the case when n = 3. Suppose that A,B,C are the three people in the group, and that a committee consists of k members from the group, where 1 ≤ k ≤ 3. For k = 1, there are 3 ways to do so as shown below.

For k = 2, there are 6 ways to do so as shown below.

For k = 3, there are 3 ways to do so as shown below.

Thus, there are altogether 3 + 6 + 3 = 12 ways to do so.

In general, from a group of n people, there are ways to form a k-member committee, and k ways to select a leader from the k members in the committee. Thus, the number of ways to form a k-member committee including the selection of a leader is, by (MP), k. As k could be 1,2,...,n, by (AP), the number of ways to do so is given by

Let us count the same problem via a different approach as follows. First, we select a leader from the group, and then choose k – 1 members, where k = 1, 2,... ,n, from the group to form a k-member committee. There are n choices for the first step and

ways for the second step. Thus, by (MP) and (B1), the required number is

Since both

count the same number, identity (B3) follows.

In the above discussion, we establish identity (B3) by first introducing a “suitable” counting problem. We then count the problem in two different ways so as to obtain two different expressions. These two different expressions must be equal as they count the same quantity. This way of deriving an identity is quite a common practice in combinatorics, and is known as “counting it twice”.

Exercise

11.1 By applying Identity (10.5) or otherwise, show that

11.2 Show that

11.3 Show that

by integrating both sides of with respect to
       x.

11.4 Show that

11.5 Solve Example 11.2 by using result (7.1)(ii).