Sequences & SummationsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSection 2.4 of [email protected] & SummationsThough you should be (at least intuitively) familiar with sequencesand summations, we give a quick review.NotesSequencesDefinitionA sequence is a function from a subset of integers to a set S. Weuse the notation(s):{an} {an}∞n{an}∞n=0{an}∞n=0Each anis 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.NotesSequencesExampleExampleConsider the sequence1 +1nn∞n=1The terms area1= (1 + 1)1= 2.00000a2= (1 +12)2= 2.25000a3= (1 +13)3= 2.37037a4= (1 +14)4= 2.44140a5= (1 +15)5= 2.48832What is this sequence?NotesSequencesExampleThe sequence corresponds to e:limn→∞1 +1nn= e = 2.71828 . . .NotesSequencesExample IIExampleThe sequence{hn}∞n=1=1nis known as the harmonic sequence.The sequence is simply1,12,13,14, . . .This sequence is particularly interesting because its summation isdivergent;∞Xn=11n= ∞NotesProgressions IDefinitionA geometric progression is a sequence of the forma, ar, ar2, ar3, . . . , arn, . . .Where a ∈ R is called the initial term and r ∈ R is the commonratio.A geometric progression is a discret e analogue of the exponentialfunctionf(x) = arxNotesProgressions I IDefinitionAn arithmetic progression is a sequence of the forma, a + d, a + 2d, a + 3d, . . . , a + nd, . . .Where a ∈ R is called the initial term and r ∈ R is the commondifference.Again, an arithmetic progression is a discrete analogue of the linearfunction,f(x) = dx + aNotesProgressions I IIExampleA common geometric progression in c omputer sc ience is{an} =12nHere, a = 1 and r =12Table 1 on Page 153 (Rosen) has useful sequences.NotesSummations IYou should be very familiar with Summation notation:nXj=maj= am+ am+1+ · · · + an−1+ anHere, j is the index of summation, m is the lower limit, and n isthe upper limit.Often times, it is useful to change the lower/upp er lim its; whichcan be done in a straightforward manner (though we must becareful).nXj=1aj=n−1Xj=0aj+1Sometimes we c an express a summation in closed form. Geometricseries, for example:NotesSummations IITheoremFor a, r ∈ R, r 6= 0,nXi=0ari=(arn+1−ar−1if r 6= 1(n + 1)a if r = 1NotesSummations IIIDouble summations often arise when analyzing an algorithm.nXi=1iXj=1aj= a1+a1+ a2+a1+ a2+ a3+· · ·a1+ a2+ a3+ · · · + anSummations can also be indexed over elements in a se t.Xs∈Sf(s)Table 2 on Page 157 (Rosen) has useful summations.NotesSeriesWhen we take the sum of a sequence, we get a series. We’vealready seen a closed form for geometric series.Some other useful closed forms include the following.uXi=l1 = u − l + 1, for l ≤ unXi=0i =n(n + 1)2nXi=0i2=n(n + 1)(2n + 1)6nXi=0ik≈1k + 1nk+1nXi=0αi=αn+1− 1α − 1, α 6= 1nXi=1log i ≈ n log nNotesInfinite Series IThough we will mostly deal with finite series (i.e. an upper limit ofn for a fixed integer), infinite series are also useful.ExampleNotesInfinite Series IIConsider the geometric series∞Xn=012n= 1 +12+14+ · · ·This series converges to 2. However, the geometric series∞Xn=02n= 1 + 2 + 4 + 8 + · · ·does not converge. However, note thatPnn=02n= 2n+1− 1In fact, we can generalize this as follows.LemmaNotesInfinite Series IIIA geometric series converges if and only if the absolute value ofthe common ratio is less than
View Full Document
Unlocking...