Binomial coefficient formula and the Pascal triangle. (a)

QUESTION:

Binomial coefficient formula and the Pascal triangle. (a) Use the definition of G) as the number of distinct n-toss sequences with k heads, to derive the recursion suggested by the so called Pascal triangle, given in Fig. 1.20. (b) Use the recursion derived in part (a) and induction, to establish the formula (n) n! k - k! (n - k)! ' Solution. (a) Note that n-toss sequences that contain k heads (for a < k < n) can be obtained in two ways: (1) By starting with an (n - I)-toss sequence that contains k heads and adding a tail at the end. There are (nk1) different sequences of this type. (2) By starting with an (n - I)-toss sequence that contains k - 1 heads and adding a head at the end. There are G=) different sequences of this type. (0 ) 1 ) () () () (2 ) ) () () () ( ) () () () ( ) 1 .20: ........... "' ... 'n fEach term () in the 2 3 3 binomial com4Cle:m:.s 1 and in the array on the its two in the row above it (except for the boundary terms with k = 0 or k = n, which are equal to 1). if k = 1, ... j n - 1. if k = n. This is formula corresponding to the Pascal triangle calculation , given in (b) now use (a) to () = k! (n-k) ! ' 1 by on n. we t he () = (i) = 1, so n = 1 1 above formula is seen to hold as long as we use the convention O! = 1. If the formula holds for each index up to n - 1 \ we have for k = 1 , 2, . . . ,n - 1 j ( n ) (n - 1) (n - 1) k k - l + k = ------------------------ (k - k n - k n! = - . + -- . ------- n k! (n-k)! 11, k! (n - k)! k! ( n - k)! ' and the induction is complete.