Principles of Mathematics in Operations Research

286 Solutions

r <n objects out of n objects is (™). Thus, ar = (™). We cannot choose more

than n objects; that is ar = 0, r > n. Therefore,

,,_n V /

X

\ r I

r=0

Let us prove the power expansion as a corollary to the Binomial theorem.

The Binomial theorem states that (l + z)n = £"=0 (").?*. Let z = |. Then

i + *V = y^ f

nN

i f£Y ^ (

x +

y\

n

= (

x

+ v)

n

= \p (

n

\ (^

y) i^\i)\y) \ v ) v

n

fjwW

i=0 ^ '

Let us prove the multinomial theorem as a corollary to the Binomial the-

orem by induction on k.

zi,.. .,4 S Z+

h-\ \-ik=n

Let Z = 2 and a;i = x, X2 = y. We use the power expansion to state that

the induction base (k = / = 2) is true. Let use assume as induction hypothesis

that

(*' + '••*>"- , £ (,„.".,«,)•

\"n i/

holds.

(Xi + • • • + Xi + Xi + 1 )n =

ii,... ,h,ii+i € Z+

«i H M; + ij+i = n

needs to be shown.
Let x = xi + • • • + X[ and y = xi+i in the power expansion.