DOC PREVIEW
UNL CSCE 235 - Sequences & Summations

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 sequence1 +1nn∞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 +1nn= 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

UNL CSCE 235 - Sequences & Summations

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Sequences & Summations
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sequences & Summations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sequences & Summations 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?