Discrete Mathematics for Computer Science

460 CHAPTER 7 Counting and Combinatorics

(Inductive step) Choose n > no, and assume n E T. Now, prove that n + 1 E T. Begin

by setting

(x + y)n+l = (x + y)(x + y)n.

By the inductive assumption, this is

n

(X -y)n+l = (X + y) * • C(n, i) Xn-i yi

i=O

= x 1 C(n, i) xn-i yi) + y C(n, i) xn-i yi)

ni=0 i=O

n

= C(n, O)xn+l + - C(n, i) xn-i+l yi

i=1

n-1

• C(n, i) Xn-i yi+l + C(n, n)yn+

1

i=O

Next, replace i by i - 1 in the third term, giving

n-1 n

Y C(n,i)xn-i yijl =: C(n, i - 1) xn-i+l yi

i=O i=t

This makes the two sums start at the same value so that they can be added term by term to

get

n

S(C(n, i) +4 C(n, i - 1)) xn-i+t yi

By Pascal's Identity, the sum becomes

n

Y' C(n + 1, i) xn-i+l yi

i=1

Combining these results gives

n

(X + y)n+l - yn+l -+ Z C(n + 1, i) Xn-i+l y i +t xn+

i=1

n+1

S L C(n ± 1, i)xn+l-i yi

i=O

Therefore, n + 1 E T.

By the Principle of Mathematical Induction, T = N. U

Knowing the form of the coefficients of (x + y)n allows some interesting results to be

proven.

Theorem 6. For n E N,

2n = C(n, O) + C(n, 1) - ' C(n, n)