Question

Exercise 1.14. If n and k are integers, define the binomial coeffi- cient (m), read n choose k, by n! if 0 <k <n, = 0 otherwise. k!(n - k)! (a) Prove that ("#") = (m) + (-2) for all integers n and k. (b) By definition, () = 1 if k = 0 and 0 otherwise. The recursion relation in (a) gives a computational procedure, Pascal's triangle, for calculating binomial coefficients for small n. Start with a doubly- infinite row of Os containing a single 1, and generate each successive row by writing the sum of each pair of consecutive entries below and between the "parent" entries: 0 0 0 0 n=0 n=1: 0 n=2: 0 1 1 1 0 1 2 1 0 0 : 0 ... ... : Fill in the next five rows of Pascal's triangle. (c) Prove that (%) is the number of distinct k-element subsets of a set of n elements. Suggestion: Use induction on n. For the inductive step, consider a set {0, 1, 2,...,n} of (n+1) elements and separately count the number of subsets that do, or that do not contain 0.

(A and C)

Answer 1

Sol": as Given that 1 Iki (ok) 0 - Dosken ( 2 o otherwise with and Now for any integer n and kn 2 m ( ) + ( ) Kri + - KI (0-K), des - n ! (k-1) (n-K+)? hour X2 ni - K -1 (0-6); L [**!=n(n-14) (K-121 (2-K) n-kal - n aktin (K-1)! (-)! K(n-K+12 ) 2351 n! & (n+1) 2 *(K-1)! (m-K+1) 60-x) (n+1) Mann KInti - k) kan word Hence the result follows . A 10

TIT: subsets The number of of a set of distinct Kellement n elements is (2) is Now set n=1 and kal. Then there 1 set only containing one element, the set itself and sale ancka (2) det n=2 and al. Then clearly there are 2 subset containing one element and 2= 2 =nex - (2) Therefore, the result is true for sal, 2. der the result is true for n. i.e. the number of distinct k-element subrits of a set of selements is (2) We have to show that the result is true for (N+1). cor. without loss of generality let us assume that S=20,1,2,...unt de a net with (241) elements and and A = 1,2,...,n} be a nelement subet of. 3. Then there are (n) number of distinct k-element subsets of A and so is s.: ACCI Now since S.AZ03 i.e. o is the only element ins which is not in A,

then if we've to find another k.element subsets of s . We need to take (kai) element of A and take the element o.. So the number of distinct (kril-element subsets of A of a elements is (0) Therefore the total number of krelement subsets of sof (n+1) elements is. () + («?) - (n) [hy las] and these are the only u. elements subsets of s. Hence the result is true for tl) also. Therefore by Mathematical induction. the result is true for all n. This our proof is done.