Chapter 4, Summations and ProductsInductionFinding an explicit formulaSlide 4Summation & product notationVariable ending pointNesting of sum/product notationTelescoping seriesPropertiesProperties, con't.Discrete Structures CMSC 250 Lecture 22Factorial1CMSC 250Chapter 4, Summations and Products2CMSC 250InductionInduction is a proof technique used to verify a property of a sequence–2,4,6,8,… for i 1 ai = 2i•an infinite sequence with infinite distinct values–for i 1 bi = (1)i•an infinite sequence with finite distinct values–for 1 i 6 ci = i + 5•a finite sequence (with finite distinct values)3CMSC 250Finding an explicit formulaFigure out the formula for this sequence:,...251,161,91,41,1 4CMSC 250Finding an explicit formulaDifferent sequences with the same initial values:2)1(12:03kkbkakkk5CMSC 250Summation & product notationSum of items specifiedProduct of items specified654321612222222 kk)5(2*)4(2*)3(2*)2(2*)1(2251kk6CMSC 250Variable ending point n as the index of the final termfor n = 2for n = 3nkknk017CMSC 250Nesting of sum/product notationVariations (same or different??): njmiijjY121)( njmiijjY121)( njmiijjY1 128CMSC 250Telescoping series nkkkkk1)211()1(1iini9CMSC 250PropertiesMerging and splittingnmkkknmkknmkkbaba )()(** kknmkknmkknmkbabanikkimkknmkkaaa1knikkimkknmkaaa1*10CMSC 250Properties, con't.Distributionnmkknmkkacac )*(*11CMSC 250Discrete StructuresCMSC 250Lecture 22March 24, 200812CMSC 250Factorialn! = n (n 1) (n 2) … 2 1Definition:0! = 1n! = n (n
View Full Document
Unlocking...