CMSC 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 3Sequences 2,4,6,8,… for i ≥ 1 ai= 2i– infinite sequence with infinite distinct values For i ≥ 1 bi= (-1)i– infinite sequence with finite distinct values For 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 Formula Figure the formula of this sequence Different sequences with same initial values,...251,161,91,41,1−−2)1(1203++−=+=>=kkbkakkk()1,121≥−=+kkakk()( )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 ≥= kakk≥+===−−2,1;01210kaaaaakkk25 June 2007 Sequences & Summation 7Summation & Product Notation Sum of Items Specified Product of Items Specified654321612222222 +++++=∑=kk)5(2)4(2)3(2)2(2)1(2251⋅⋅⋅⋅=Π=kk25 June 2007 Sequences & Summation 8Variable ending point n as the index of the final term for n = 2 for n = 3∑=++nkknk01nnnnn 2123121+++++++ L25 June 2007 Sequences & Summation 9Telescoping Series∑=++−+nkkkkk1211+Π=11iini25 June 2007 Sequences & Summation 10Factorial n! = n ⋅ (n-1) ⋅ (n-2) ⋅ … ⋅ 2 ⋅ 1 Definition( )≥−⋅==1if!10if1!nnnnn25 June 2007 Sequences & Summation 11Properties Merging and Splitting Distribution( )∑∑∑===+=+nmkkknmkknmkkbaba( )kknmkknmkknmkbaba ⋅=⋅ΠΠΠ===( )∑∑==⋅=⋅nmkknmkkacac∑∑∑+===+=nikkimkknmkkaaa1⋅=ΠΠΠ+===knikkimkknmkaaa125 June 2007 Sequences & Summation 12Using the Properties1;1−=+=kbkakk∑∑==⋅+nmkknmkkba 2⋅∏∏==nmkknmkkba25 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.– Hence∑∑∑=====+7171601111kjkkjk1:11:60+=+∑=kjablevariofchangeksummationk( )jjk111111=+−=+∑∑===+7160111jkjk25 June 2007 Sequences & Summation 15Applications Indexing arrays using loops– When to start and end– … Algorithms– Convert from base 10 to base 2–
View Full Document