Discrete Mathematics for Computer Science

Combinatorial Identities 461

Proof. Expand (x + y)f with x = y = 1. 0

Corollary 2: The number of subsets of an n-element set is 2n.

For different arguments to prove Corollary 2, see Theorem 2 in Section 1.7.4 and

Example 4 in Section 7.2.1.

Theorem 7. For n > 1,

n

E C(n, i)(-1)' = 0

i=O

Proof. The idea of the proof is to use the Binomial Theorem and expand (x + y)n

with x = 1 and y = -1. By the Binomial Theorem with n > 1, we have (x + y)n+l =

ZinO C(n, i)xn- yt.Let x =^1 and y = -1. The identity then becomes

n+1

(1 + (- 1))n+l = LC(n, )ln-i (-1)i

i=0

n+1

0 E C(n, i)(-1)i

i=O

Corollary 3: For n even,

n/2 n/2-1

E C(n' 2i) Y' C(n, 2i-+-1)

i=0 i=O

Corollary 4: For n odd,

[n/2J Ln/2j+1

SC(n, 2i)= C(n, 2i+ 1

i=0 i=O
The corollaries to Theorem 7 can be interpreted as saying that for any n-element set,
there are as many subsets with an even number of elements as there are subsets with an
odd number of elements. An obvious result of the corollaries is that

n/2 Ln/2j

C C(n, 2i) Y' C C(n, 2i)

i=0 i=O

Since it is also true that

n/2 [n/21

ZC(n' 2i) + Y' C(n, 2i) =^2

i=0 i=O

it follows that

n/2 [n/2J

C(n, 2i) = C(n, 2i) = 2-1

i=0 i=0