CMSC 250 Discrete StructuresWhat is Next?SequencesIdentical series?Finding the Explicit FormulaWhat is the Formula?Summation & Product NotationVariable ending pointTelescoping SeriesFactorialPropertiesUsing the PropertiesChange of Variables (1 of 2)Change of Variables (2 of 2)ApplicationsCMSC 250Discrete StructuresSummation:Sequences and Mathematical Induction25 June 2007 Sequences & Summation 2What is Next?2, 4, 6, 8, 10, …1, 4, 9, 16, 25, …2, 4, 8, 16, 32, …0, 1, 1, 2, 3, 5, …25 June 2007 Sequences & Summation 3Sequences2,4,6,8,… for i ≥ 1 ai = 2i –infinite sequence with infinite distinct valuesFor i ≥ 1 bi = (-1)i –infinite sequence with finite distinct valuesFor 1<=i<=6 ci = i+5 –finite sequence (with finite distinct values)25 June 2007 Sequences & Summation 4Identical series?1,1 kkkak2,1 iiibi25 June 2007 Sequences & Summation 5Finding the Explicit FormulaFigure the formula of this sequenceDifferent sequences with same initial values,...251,161,91,41,1 2)1(1203kkbkakkk 1,121kkakk 0,112 kkakk25 June 2007 Sequences & Summation 6What is the Formula?2, 4, 6, 8, 10, …1, 4, 9, 16, 25, …2, 4, 8, 16, 32, …0, 1, 1, 2, 3, 5, …1,2 kkak1,2 kkak1,2 kakk2,1;01210kaaaaakkk25 June 2007 Sequences & Summation 7Summation & Product NotationSum of Items SpecifiedProduct of Items Specified654321612222222 kk)5(2)4(2)3(2)2(2)1(2251kk25 June 2007 Sequences & Summation 8Variable ending point n as the index of the final termfor n = 2for n = 3nkknk01nnnnn 2123121 25 June 2007 Sequences & Summation 9Telescoping Series nkkkkk121111iini25 June 2007 Sequences & Summation 10Factorialn! = n (n-1) (n-2) … 2 1Definition 1if!10if1!nnnnn25 June 2007 Sequences & Summation 11PropertiesMerging and SplittingDistribution nmkkknmkknmkkbaba kknmkknmkknmkbaba nmkknmkkacacnikkimkknmkkaaa1knikkimkknmkaaa125 June 2007 Sequences & Summation 12Using the Properties1;1 kbkakknmkknmkkba 2nmkknmkkba25 June 2007 Sequences & Summation 13Change of Variables (1 of 2) 3124221kjkj25 June 2007 Sequences & Summation 14Change of Variables (2 of 2)Calculate new lower and upper limits–When k = 0, j = k + 1 = 0 + 1 = 1.–When k = 6, j = k + 1 = 6 + 1 = 7.Calculate new general term–Since j = k + 1, then k = j – 1.–Hence7171601111kjkkjk1:11:60kjablevariofchangeksummatio nk jjk1111117160111jkjk25 June 2007 Sequences & Summation 15ApplicationsIndexing arrays using loops–When to start and end–…Algorithms–Convert from base 10 to base
View Full Document
Unlocking...