Notes Sequences Summations Slides by Christopher M Bourke Instructor Berthe Y Choueiry Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Section 2 4 of Rosen cse235 cse unl edu Sequences Summations Notes Though you should be at least intuitively familiar with sequences and summations we give a quick review Sequences Notes Definition A sequence is a function from a subset of integers to a set S We use the notation s 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 Sequences Notes Example Example Consider the sequence 1 1 n n n 1 The terms are a1 a2 a3 a4 a5 1 1 1 1 21 2 1 13 3 1 14 4 1 15 5 2 00000 2 25000 2 37037 2 44140 2 48832 What is this sequence Sequences Notes Example The sequence corresponds to e 1 n lim 1 e 2 71828 n n Sequences Notes Example II Example The sequence hn n 1 1 n is known as the harmonic sequence 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 Progressions I Notes Definition A geometric progression is a sequence of the form a ar ar2 ar3 arn 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 Progressions II Notes Definition An arithmetic progression is a sequence of the form a a d a 2d a 3d a nd 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 Progressions III Notes Example A common geometric progression in computer science is an Here a 1 and r 1 2n 1 2 Table 1 on Page 153 Rosen has useful sequences Summations I Notes You should be very familiar with Summation notation n X aj am am 1 an 1 an j m 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 j 0 Sometimes we can express a summation in closed form Geometric series for example Summations II Notes Theorem For a r R r 6 0 n X ari i 0 ar n 1 a r 1 if r 6 1 n 1 a if r 1 Summations III Notes Double summations often arise when analyzing an algorithm n X i 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 Table 2 on Page 157 Rosen has useful summations Series Notes 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 u X 1 u l 1 for l u i l n X i i 0 n X i2 n n 1 2n 1 6 ik 1 nk 1 k 1 i 0 n X i 0 n X i i 0 n X Infinite Series I n n 1 2 n 1 1 6 1 1 log i n log n Notes i 1 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 Infinite Series II Notes 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 Pn In fact we can generalize this as follows Lemma n n 0 2 2n 1 1 Infinite Series III A geometric series converges if and only if the absolute value of the common ratio is less than 1 Notes
View Full Document
Unlocking...