IntroductionSequencesSummationsSeriesSequences &SummationsCSE235IntroductionSequencesSummationsSeriesSequences & SummationsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSection 2.4 of [email protected] / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSequences & SummationsThough you should be (at least intuitively) familiar withsequences and summations, we give a quick review.2 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSequencesDefinitionA 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=0Each anis called the n-th term of the sequence.We rely on context to distinguish between a sequence and aset; though there is a connection.3 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSequencesExampleExampleConsider 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?4 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSequencesExampleThe sequence corresponds to e:limn→∞1 +1nn= e = 2.71828 . . .5 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSequencesExample 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 summationis divergent;∞Xn=11n= ∞6 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesProgressions 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 thecommon ratio.A geometric progression is a discrete analogue of theexponential functionf(x) = arx7 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesProgressions IIDefinitionAn 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 thecommon difference.Again, an arithmetic progression is a discrete analogue of thelinear function,f(x) = dx + a8 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesProgressions IIIExampleA common geometric progression in computer science is{an} =12nHere, a = 1 and r =12Table 1 on Page 153 (Rosen) has useful sequences.9 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSummations 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 nis the upper limit.Often times, it is useful to change the lower/upper limits;which can be done in a straightforward manner (though wemust be careful).nXj=1aj=n−1Xj=0aj+110 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSummations IISometimes we can express a summation in closed form.Geometric series, for example:TheoremFor a, r ∈ R, r 6= 0,nXi=0ari=(arn+1−ar−1if r 6= 1(n + 1)a if r = 111 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSummations 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 set.Xs∈Sf(s)Table 2 on Page 157 (Rosen) has useful summations.12 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesSeriesWhen 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 n13 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesInfinite Series IThough we will mostly deal with finite series (i.e. an upperlimit of n for a fixed integer), infinite series are also useful.ExampleConsider 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− 114 / 15Sequences &SummationsCSE235IntroductionSequencesSummationsSeriesInfinite Series IIIn fact, we can generalize this as follows.LemmaA geometric series converges if and only if the absolute value ofthe common ratio is less than 1.15 /
View Full Document