Binomial Identities.ppt

1、Binomial Identities,Expansion of (a + x)n,(a + x) = a + x = 1C0a + 1C1x (a + x)(a + x) = aa + ax + xa + xx = x2 + 2ax + a2 = 2C0x2 + 2C1ax + 2C2a2 The 4 red terms are the “formal” expansion of (a+x)2 The 3 blue terms are the “simplified” expansion of (a+x)2 (a + x)(a + x)(a + x) = aaa + aax + axa +

2、axx + xaa + xax + xxa + xxx = x3 + 3a2x + 3ax2 + a3 = 3C0x3 + 3C1a2x + 3C2ax2 + 3C3a3,Generalizing . . .,In (a + x)4, how many terms does the:formal expansion have? simplified expansion have? In (a + x)n, how many terms does the:formal expansion have? simplified expansion have?,The Coefficient on ak

3、xn-k,The coefficient on akxn-k is the number of terms in the formal expansion that have exactly k as (and hence exactly n-k xs). It is equal to the number of ways of choosing an a from exactly k of the n binomial factors: nCk.,Binomial Theorem,(1 + x)n = nC0x0 + nC1x1 + nC2x2 + . . . nCnxn In additi

4、on to the combinatorial argument that the coefficient of xi is nCi, we can prove this theorem by induction on n.,Binomial Identities,nCk = n!/k!(n-k)! = nCn-k The number of ways to pick k objects from n = the ways to pick not pick k (i.e., to pick n-k). Pascals identity: nCk = n-1Ck + n-1Ck-1 The nu

5、mber of ways to pick k objects from n can be partitioned into 2 parts: Those that exclude a particular object i: n-1Ck Those that include object i: n-1Ck-1 Give an algebraic proof of this identity.,nCk kCm = nCm n-mCk-m,Each side of the equation counts the number of k-subsets with an m-subsubset. Th

6、e LHS counts: 1. Pick k objects from n: nCk 2. Pick m special objects from the k: kCm The RHS counts: 1. Pick m special objects that will be part of the k-subset: nCm 2. Pick the k-m non-special objects: n-mCk-m,Pascals Triangle,kth number in row n is nCk:,1,1,1,1,2,1,1,3,3,1,n = 4,n = 3,n = 2,n = 1

7、,n = 0,1,4,6,4,1,k = 0,k = 1,k = 2,k = 3,k = 4,Displaying Pascals Identity,0C0,n = 4,n = 3,n = 2,n = 1,n = 0,k = 0,k = 1,k = 2,k = 3,k = 4,1C0,1C1,2C0,2C1,2C2,3C0,3C1,3C2,3C3,4C0,4C1,4C2,4C3,4C4,Block-walking Interpretation,0C0,n = 4,n = 3,n = 2,n = 1,n = 0,k = 0,k = 1,k = 2,k = 3,k = 4,1C0,1C1,2C0,

8、2C1,2C2,3C0,3C1,3C2,3C3,4C0,4C1,4C2,4C3,4C4,nCk = # ways to get to corner n,k starting from 0,0,nCk = # strings of n Ls & Rs with k Rs.,Pascals Identity via Block-walking,0C0,n = 4,n = 3,n = 2,n = 1,n = 0,k = 0,k = 1,k = 2,k = 3,k = 4,1C0,1C1,2C0,2C1,2C2,3C0,3C1,3C2,3C3,4C0,4C1,4C2,4C3,4C4,# routes

9、to corner n,k = # routes thru corner n-1,k + # routes thru corner n-1,k-1,nC0 + nC1 + nC2 + . . . + nCn = 2n,LHS counts # subsets of n elements using the sum rule: partitioning the subsets according to their size (k value). RHS counts # subsets of n elements using the product rule: Is element 1 in s

10、ubset? (2 choices) Is element 2 in subset? (2 choices) Is element n in subset? (2 choices),rCr + r+1Cr + r+2Cr + . . . + nCr = n+1Cr+1,0C0,n = 4,n = 3,n = 2,n = 1,n = 0,k = 0,k = 1,k = 2,k = 3,k = 4,1C0,1C1,2C0,2C1,2C2,3C0,3C1,3C2,3C3,4C0,4C1,4C2,4C3,4C4,rCr + r+1Cr + r+2Cr + . . . + nCr = n+1Cr+1,R

11、HS = routes to corner 4,2 LHS: Partition the routes to 4,2 into those: whose last right branch is at corner 1,1: 1C1 whose last right branch is at corner 2,1: 2C1 whose last right branch is at corner 3,1: 3C1For each subset of routes, there is only 1 way to complete the route from that corner to 4,2

12、: RLL, RL, & R respectively. The identity generalizes this argument.,nC02 + nC12 + nC22 + + nCn2 = 2nCn,0C0,n = 4,n = 3,n = 2,n = 1,n = 0,k = 0,k = 1,k = 2,k = 3,k = 4,1C0,1C1,2C0,2C1,2C2,3C0,3C1,3C2,3C3,4C0,4C1,4C2,4C3,4C4,nC02 + nC12 + nC22 + + nCn2 = 2nCn,RHS = all routes to corner 4,2 LHS partit

13、ions routes to 4,2 into those that: go thru corner 2,0: 2C0 2C2 go thru corner 2,1: 2C1 2C1 go thru corner 2,2: 2C2 2C0 The identity generalizes this argument: # routes to 2n, n that go thru n,k = nCk nCn-k Sum over k = 0 to n,123 + 234 + 345 + (n-2)(n-1)n = ?,The general term = (k-2)(k-1)k = P(k,3)

14、 = k!/(k-3)! = 3! kC3 Sum = 3!3C3 + 3!4C3 + 3!5C3 +.+ 3!nC3 = 3! 3C3 + 4C3 + 5C3 +.+ nC3 = 3! n+1C4,A Strategy,When the general term of a sum is not a binomial coefficient: break it into a sum of P(n, k) terms, if possible; rewrite these terms using binomial coefficients,12 + 22 + 32 +. . . + n2 = ?

15、 General term: = k2 = k(k-1) + k = P(k, 2) + k = 2! kC2 + k,Sum k=1,n (2! kC2 + k ) = 2! k=1,n kC2 + k=1,n k = 2! n+1C3 + n+1C2,Another Strategy: Manipulate the Binomial Theorem,(1 + 1)n = 2n = nC0 + nC1 + . . . + nCn (1 - 1)n = 0 = nC0 - nC1 + nC2 - . . . +(-1)n nCn ornC0 + nC2 . . . = nC1 + nC3 + . . . = 2n-1 Differentiate the Binomial theorem, n(1 + x)n-1 = 1nC1x0 + 2nC2x1 + 3nC3x2 + + nnCnxn-1 n(1 + 1)n-1 = 1nC1 + 2nC2 + 3nC3 + + nnCn,