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 1 the formula of this sequence k 1 1 ak 2 k 1 1 1 1 1 k 4 9 Different k 0 values 16 25 1 ak 2 k 1 k k 0 sequences with same initial ak 2k 1 3 bk k 1 k 2 25 June 2007 Sequences Summation 5 What is the Formula 2 4 6 8 10 ak 2k k 1 2 a k k 1 1 4 9 16 25 k k a 2 k 1 2 4 8 16 32 k 0 1 1 2 3 5 25 June 2007 a0 0 a1 1 ak ak 2 ak 1 k 2 Sequences Summation 6 Summation Product Notation Sum 6 2 of Items Specified k 1 2 3 4 5 2 2 2 2 2 2 6 k 1 Product of Items Specified 5 2k 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 n k k 0 for n 2 for n 3 1 2 3 n 1 n n 1 n 2 2n 25 June 2007 Sequences Summation 8 Telescoping Series k 1 k k 2 k 1 k 1 n i i 1 i 1 n 25 June 2007 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 k n a k k i 1 i n ak ak 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 j 2 25 June 2007 2 3 k Sequences Summation 2 k 1 13 Change of Variables 2 of 2 6 1 summation k 0 k 1 Calculate change of variable j k 1 new lower and upper limits When k 0 1 When k 6 7 j k 1 0 1 j k 1 6 1 1 1 term Calculate1 new general 1 kj j 1 1then Since j k 1k j1 6 7 7 1 1 1 Hence 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...