CMSC 250 Discrete Structures Summation Sequences and Mathematical Induction What 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 2 Sequences 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 3 Identical series k ak k 1 k 1 25 June 2007 i 1 bi i 2 i Sequences Summation 4 Finding the Explicit Formula Figure the formula of this sequence k 1 1 ak k 1 1 1 1 1 2 k 1 4 9 Different 16 25 1 k ak k 1 2 k 0 sequences with same initial values k 0 ak 2 k 1 3 bk k 1 k 2 25 June 2007 Sequences Summation 5 What is the Formula 2 4 6 8 10 1 4 9 16 25 ak 2k k 1 2 ak k k 1 k 2 4 8 16 32 ak 2 k 1 0 1 1 2 3 5 a0 0 a1 1 ak ak 2 ak 1 k 2 25 June 2007 Sequences Summation 6 Summation Product Notation Sum 6 of Items Specified 2 k 1 2 3 4 5 2 2 2 2 2 2 6 k 1 Product 5 of Items Specified 2 k 2 1 2 2 2 3 2 4 2 5 k 1 25 June 2007 Sequences Summation 7 Variable ending point n as the index of the final term n k 1 k 0 n k for n 2 for n 3 1 2 3 n 1 L n n 1 n 2 2n 25 June 2007 Sequences Summation 8 Telescoping Series k 1 k k 2 k 1 k 1 n n i 1 25 June 2007 i i 1 Sequences Summation 9 Factorial n n n 1 n 2 2 1 Definition if n 0 1 n n n 1 if n 1 25 June 2007 Sequences Summation 10 Properties Merging n n and Splitting n a b a k k m k k m k bk k m n i a a k k m n n n ak bk ak bk k m k m k m k m n k a k k i 1 i n ak a k ak k m k m k i 1 n Distribution n n k m k m c ak c ak 25 June 2007 Sequences Summation 11 Using the Properties ak k 1 bk k 1 n a k m n k 2 bk k m ak bk k m k m n 25 June 2007 n Sequences Summation 12 Change of Variables 1 of 2 4 j 1 2 k j 2 25 June 2007 3 2 k 1 Sequences Summation 13 Change of Variables 2 of 2 6 1 summation k 0 k 1 Calculate new lower and upper limits When k 0 When k 6 Calculate change of variable j k 1 j k 1 0 1 1 j k 1 6 1 7 new general term Since j k 1 then k j 1 1 1 1 Hence k 1 j 1 1 j 6 7 1 1 7 1 k 0 k 1 j 1 j k 1 k 25 June 2007 Sequences Summation 14 Applications Indexing arrays using loops When to start and end Algorithms Convert from base 10 to base 2 25 June 2007 Sequences Summation 15
View Full Document
Unlocking...