1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 10Milos [email protected] Sennott SquareSequences and summationsM. HauskrechtCS 441 Discrete mathematics for CSSequencesDefinition: A sequence is a function from 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 …. a1a2a3a4a5a6….2M. HauskrechtCS 441 Discrete mathematics for CSSequencesExamples:• (1) an= n2, where n = 1,2,3...– What are the elements of the sequence? 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 progression is a sequence of the forma, a+d,a+2d, …, a+ndwhere a is the initial term and d is common difference, such that both belong to R.Example:•sn= -1+4n for n=0,1,2,3, …• members: -1, 3, 7, 11, …3M. HauskrechtCS 441 Discrete mathematics for CSGeometric progressionDefinition A geometric progression is a sequence of the form: a, ar, ar2, ..., ark, where a is the initial term, and r is the common ratio. 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 term.1, 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? • 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 3.1, 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. Example :•an = an-1 + 2 assuming a0 = 1;•a0 = 1;•a1 = 3;•a2 = 5;•a3 = 7;• Can you write an non-recursivelyusing 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 summation.nnmjmmjaaaa ...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. 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(....43211n+1 …n+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(jjjjTrickM. HauskrechtCS 441 Discrete mathematics for CSDouble summationsExample: 4121)2(ijjiS41212112ijjji  4121212ij jji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 series.Theorem: The sum of the terms of a geometric progression a, ar, ar2, ..., 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 •