Set, Combinatorics, Probability, and Number TheoryPascal’s TriangleSlide 3Slide 4Binomial TheoremExercisesSet, Combinatorics, Probability, and Number TheoryMathematical Structures for Computer ScienceChapter 3Copyright © 2006 W.H. Freeman & Co. MSCS Slides Set, Combinatorics, Probability & Number TheorySection 3.6 Binomial Theorem 2Pascal’s TriangleConsider the following expressions for the binomials:(a + b)0 = 1(a + b)1 = a + b(a + b)2 = a2 + 2ab + b2(a + b)3 = a3 + 3a2b + 3ab2 + b3(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4Row n of the triangle (n 0) consists of all the values C(n, r) for 0 r n. Thus, the Pascal’s looks like this: Row C(0,0) 0 C(1,0) C(1,1) 1 C(2,0) C(2,1) C(2,2) 2 C(3,0) C(3,1) C(3,2) C(3,3) 3 C(4,0) C(4,1) C(4,2) C(4,3) C(4,4) 4 C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5) 5C(n,0) C(n,1) ….………… C(n,n1) C(n,n) nSection 3.6 Binomial Theorem 3Pascal’s TriangleThe Pascal’s triangle can be written as: C(0,0) C(1,0) C(1,1)C(2,0) C(2,1) C(2,2) C(3,0) C(3,1) C(3,2) C(3,3)C(4,0) C(4,1) C(4,2) C(4,3) C(4,4) C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5) . .……….C(n,0) C(n,1) ………. C(n,n 1) C(n,n)We note that C(n,k) = C(n 1,k 1) + C(n 1,k) for 1 k n 1Can be proved simply by expanding the right hand side and simplifying.Section 3.6 Binomial Theorem 4Pascal’s Triangle Coefficients Power0 0 1 1 1 1 2 1 21 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5Section 3.6 Binomial Theorem 5Binomial TheoremThe binomial theorem provides us with a formula for the expansion of (a + b)n.It states that for every nonnegative integer n:The terms C(n,k) in the above series is called the binomial coefficient.Binomial theorem can be proved using mathematical induction.€ a +b( )n=C(n,0)anb0+C(n,1)an − 1b1+C(n,2)an − 2b2+....+C(n,n− k)akbn − k+.... +C(n,n−1)a1bn − 1+C(n,n)anb0 = C(n,k)an − kbkk=0n∑Section 3.6 Binomial Theorem 6ExercisesExpand (x + 1)5 using the binomial theoremC(5,0)x5 + C(5,1)x4 + C(5,2)x3 + C(5,3)x4 + C(5,4)x1 + C(5,0)x0Expand (x 3)4 using the binomial theoremThe fifth term of (3a + 2b)7What is the coefficient of x5y2z2 in the expansion of (x + y + 2z)9 ?Use binomial theorem to prove that:C(n,0) – C(n,1) + C(n,2) - …….+ (-1)nC(n,n) =
View Full Document