Transcription of Sequences and summations
1 1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 10 Milos Sennott SquareSequences and summationsM. HauskrechtCS 441 Discrete mathematics for CSSequencesDefinition:A sequenceis a functionfrom a subset of the set of integers (typically the set {0,1,2,..} or the set {1,2,3,..} to a set S. We use the notation anto denote the image of the integer n. We call ana term of the sequence . Notation:{an} is used to represent the sequence (note {} is the same notation used for sets, so be careful). {an} represents the ordered list a1, a2, a3, ..{an}1 2 3 4 5 6 .. HauskrechtCS 441 Discrete mathematics for CSSequencesExamples: (1) an= n2, where n = 1,2, What are the elements of the sequence ?)
2 1, 4, 9, 16, 25, .. (2) an= (-1) n, where n=0,1,2,3,.. Elements of the sequence ?1, -1, 1, -1, 1, .. 3) an= 2 n, where n=0,1,2,3,.. Elements of the sequence ?1, 2, 4, 8, 16, 32, ..M. HauskrechtCS 441 Discrete mathematics for CSArithmetic progressionDefinition:An arithmetic progressionis a sequence of the forma, a+d,a+2d, .., a+ndwhere a is the initial termand d is common difference, such that both belong to : sn= -1+4n for n=0,1,2,3, .. members: -1, 3, 7, 11, ..3M. HauskrechtCS 441 Discrete mathematics for CSGeometric progressionDefinitionA geometric progressionis a sequence of the form: a, ar, ar2, .., ark, where a is the initial term, and r is the common ratio.
3 Both a and r belong to R. Example: an= ( )n for n = 0,1,2,3, ..members: 1, , , 1/8, ..M. HauskrechtCS 441 Discrete mathematics for CSSequences Given a sequence finding a rule for generating the sequence is not always straightforwardExample: Assume the sequence : 1,3,5,7,9, .. What is the formula for the sequence ? Each term is obtained by adding 2 to the previous , 1+2=3, 3+2=5, 5+2=7 What type of progression this suggest? 4M. HauskrechtCS 441 Discrete mathematics for CSSequences Given a sequence finding a rule for generating the sequence is not always straightforwardExample: Assume the sequence : 1,3,5,7,9, .. What is the formula for the sequence ?
4 Each term is obtained by adding 2 to the previous term. 1, 1+2=3, 3+2=5, 5+2=7 It suggests an arithmetic progression: a+ndwith a=1 and d=2 an=1+2nM. HauskrechtCS 441 Discrete mathematics for CSSequences Given a sequence finding a rule for generating the sequence is not always straightforwardExample 2: Assume the sequence : 1, 1/3, 1/9, 1/27, .. What is the sequence ? The denominators are powers of , 1/3= 1/3, (1/3)/3=1/(3*3)=1/9, (1/9)/3=1/27 This suggests a geometric progression: ark with a=1 and r=1/3 (1/3 )n5M. HauskrechtCS 441 Discrete mathematics for CSRecursively defined Sequences The n-th element of the sequence {an} is defined recursively in terms of the previous elements of the sequence and the initial elements of the sequence .
5 Example : an = an-1 + 2 assuming a0 = 1; a0 = 1; a1 = 3; a2 = 5; a3 = 7; Can you write an non-recursively using n? an = 1 + 2nM. HauskrechtCS 441 Discrete mathematics for CSFibonacci sequence Recursively defined sequence , where f0 = 0; f1 = 1; fn = fn-1 + fn-2 for n = 2,3, .. f2= 1 f3= 2 f4= 3 f5= 56M. HauskrechtCS 441 Discrete mathematics for CSSummationsSummation of the terms of a sequence :The variable j is referred to as the index of summation. m is the lower limit and n is the upper limit of the ..1M. HauskrechtCS 441 Discrete mathematics for CSSummationsExample: 1) Sum the first 7 terms of {n2} where n=1,2,3, .. 2) What is the value of 140493625164171712 jjjja11)1(1)1(1)1(8484 kkjja7M.
6 HauskrechtCS 441 Discrete mathematics for CSArithmetic seriesDefinition:The sum of the terms of the arithmetic progressiona, a+d,a+2d, .., a+nd is called an arithmetic series. Theorem:The sum of the terms of the arithmetic progressiona, a+d,a+2d, .., a+nd is Why? 2)1()(11 nndnajdnajdaSnjnjM. HauskrechtCS 441 Discrete mathematics for CSArithmetic seriesTheorem:The sum of the terms of the arithmetic progressiona, a+d,a+2d, .., a+nd isProof:2)1()(11 nndnajdnajdaSnjnj njnjnjnjjdnadjajdaS1111)(nnnjnj )1()2(..432118M. HauskrechtCS 441 Discrete mathematics for CSArithmetic seriesTheorem:The sum of the terms of the arithmetic progressiona, a+d,a+2d, .., a+nd isProof: njnjnjnjjdnadjajdaS1111)(nnnjnj )1()2(.
7 43211n+ +12)1()(11 nndnajdnajdaSnjnjn+1)1(*2 nnM. HauskrechtCS 441 Discrete mathematics for CSArithmetic seriesExample: 51)32(jjS 515132jjj 5151312jjj 5135*2jj 5*2)15(310554510 9M. HauskrechtCS 441 Discrete mathematics for CSArithmetic seriesExample 2: 53)32(jjS 21215151312312jjjjjj421355 2151)32()32(jjjjTr i c kM. HauskrechtCS 441 Discrete mathematics for CSDouble summationsExample: 4121)2(ijjiS 41212112ijjji 4121212ijjji 41212*2ijji 4132*2ii 414134iii 4141134iii284*310*4 10M. HauskrechtCS 441 Discrete mathematics for CSGeometric seriesDefinition:The sum of the terms of a geometric progression a, ar, ar2, .., arkis called a geometric :The sum of the terms of a geometric progression a, ar, ar2.
8 , arnis 11)(100rraraarSnnjnjjjM. HauskrechtCS 441 Discrete mathematics for CSGeometric seriesTheorem:The sum of the terms of a geometric progression a, ar, ar2, .., arnisProof: multiply S by r Substract 11)( nnjjarararararrrSnnjjararararaarS ..320 nnarararaararararSrS ..2132aarn 1 11111rraraarSnn11M. HauskrechtCS 441 Discrete mathematics for CSGeometric seriesExample: General formula: 11)(100rraraarSnnjnjjj 30)5(2jjS 1515*2)5(2430jjS312156*24624*241625*2 M. HauskrechtCS 441 Discrete mathematics for CSInfinite geometric series Infinite geometric series can be computed in the closed form for x<1 How? Thus:xxxxxxkkknnknn 111111limlim100xxnn 110
