Chapter 4 Summations and Products CMSC 250 1 Induction Induction 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 CMSC 250 2 Finding an explicit formula Figure out the formula for this sequence 1 1 1 1 1 4 9 16 25 CMSC 250 3 Finding an explicit formula Different sequences with the same initial values k 0 ak 2k 1 bk k 1 3 k 2 CMSC 250 4 Summation product notation Sum of items specified 6 k 1 2 3 4 5 2 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 CMSC 250 5 Variable ending point n as the index of the final term n k 1 n k k 0 CMSC 250 for n 2 for n 3 6 Nesting of sum product notation Variations same or different n mj Yij j 1 i 1 CMSC 250 2 n mj Y ij j 1 i 1 2 n mj Yij 2 j 1 i 1 7 Telescoping series n k k 1 k 1 k 2 k 1 n i i 1 i 1 CMSC 250 8 Properties n Merging and splitting n ak bk k m k m n n k m k m ak bk CMSC 250 n ak bk k m n ak bk k m n ak k m n ak ak k m i n ak k m k i 1 i n ak k m k i 1 ak 9 Properties con t Distribution c CMSC 250 n n k m k m a k c ak 10 Discrete Structures CMSC 250 Lecture 22 March 24 2008 CMSC 250 11 Factorial n n n 1 n 2 2 1 Definition 0 1 n n n 1 CMSC 250 12
View Full Document
Unlocking...