Sequences Summations CSE235 Sequences Summations Introduction Sequences Summations Series Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 15 Section 2 4 of Rosen Sequences Summations Sequences Summations CSE235 Introduction Sequences Summations Series 2 15 Though you should be at least intuitively familiar with sequences and summations we give a quick review Sequences Sequences Summations CSE235 Introduction Sequences Summations Definition A sequence is a function from a subset of integers to a set S We use the notation s Series an an n an n 0 an n 0 Each an is called the n th term of the sequence We rely on context to distinguish between a sequence and a set though there is a connection 3 15 Sequences Example Sequences Summations CSE235 Example Consider the sequence Introduction Sequences Summations 1 1 n n n 1 Series The terms are a1 a2 a3 a4 a5 What is this sequence 4 15 1 1 1 1 21 2 1 31 3 1 41 4 1 51 5 2 00000 2 25000 2 37037 2 44140 2 48832 Sequences Example Sequences Summations CSE235 Introduction Sequences Summations Series 5 15 The sequence corresponds to e 1 n lim 1 e 2 71828 n n Sequences Example II Sequences Summations CSE235 Example The sequence hn n 1 Introduction Sequences Summations 1 n is known as the harmonic sequence Series The sequence is simply 1 1 1 1 2 3 4 This sequence is particularly interesting because its summation is divergent X 1 n n 1 6 15 Progressions I Sequences Summations CSE235 Introduction Definition A geometric progression is a sequence of the form Sequences Summations a ar ar2 ar3 arn Series Where a R is called the initial term and r R is the common ratio A geometric progression is a discrete analogue of the exponential function f x arx 7 15 Progressions II Sequences Summations CSE235 Introduction Definition An arithmetic progression is a sequence of the form Sequences Summations a a d a 2d a 3d a nd Series Where a R is called the initial term and r R is the common difference Again an arithmetic progression is a discrete analogue of the linear function f x dx a 8 15 Progressions III Sequences Summations CSE235 Introduction Example Sequences A common geometric progression in computer science is Summations Series an Here a 1 and r 1 2n 1 2 Table 1 on Page 153 Rosen has useful sequences 9 15 Summations I Sequences Summations CSE235 Introduction Sequences Summations You should be very familiar with Summation notation n X aj am am 1 an 1 an j m Series Here j is the index of summation m is the lower limit and n is the upper limit Often times it is useful to change the lower upper limits which can be done in a straightforward manner though we must be careful n n 1 X X aj aj 1 j 1 10 15 j 0 Summations II Sequences Summations CSE235 Introduction Sequences Sometimes we can express a summation in closed form Geometric series for example Summations Series Theorem For a r R r 6 0 n X i 0 11 15 ari ar n 1 a r 1 if r 6 1 n 1 a if r 1 Summations III Double summations often arise when analyzing an algorithm Sequences Summations CSE235 Introduction Sequences Summations Series i n X X aj a1 i 1 j 1 a1 a2 a1 a2 a3 a1 a2 a3 an Summations can also be indexed over elements in a set X f s s S 12 15 Table 2 on Page 157 Rosen has useful summations Series Sequences Summations CSE235 Introduction When we take the sum of a sequence we get a series We ve already seen a closed form for geometric series Some other useful closed forms include the following Sequences Summations Series u X i l n X 1 u l 1 for l u i i 0 n X i2 n n 1 2n 1 6 ik 1 nk 1 k 1 i 0 n X 13 15 i 0 n n 1 2 Infinite Series I Sequences Summations CSE235 Introduction Sequences Summations Series Though we will mostly deal with finite series i e an upper limit of n for a fixed integer infinite series are also useful Example Consider the geometric series X 1 1 1 1 2n 2 4 n 0 This series converges to 2 However the geometric series X 2n 1 2 4 8 n 0 does not converge However note that 14 15 Pn n n 0 2 2n 1 1 Infinite Series II Sequences Summations CSE235 Introduction Sequences In fact we can generalize this as follows Summations Series Lemma A geometric series converges if and only if the absolute value of the common ratio is less than 1 15 15
View Full Document
Unlocking...