advertisement

… and now for… Sequences Fall 2002 CMSC 203 - Discrete Structures 1 Sequences Sequences represent ordered lists of elements. A sequence is defined as a function from a subset of N to a set S. We use the notation an to denote the image of the integer n. We call an a term of the sequence. Example: subset of N: 1 2 3 4 5 … S: 2 4 6 8 10 … Fall 2002 CMSC 203 - Discrete Structures 2 Sequences We use the notation {an} to describe a sequence. Important: Do not confuse this with the {} used in set notation. It is convenient to describe a sequence with a formula. For example, the sequence on the previous slide can be specified as {an}, where an = 2n. Fall 2002 CMSC 203 - Discrete Structures 3 The Formula Game What are the formulas that describe the following sequences a1, a2, a3, … ? 1, 3, 5, 7, 9, … an = 2n - 1 -1, 1, -1, 1, -1, … an = (-1)n 2, 5, 10, 17, 26, … an = n2 + 1 0.25, 0.5, 0.75, 1, 1.25 … an = 0.25n 3, 9, 27, 81, 243, … Fall 2002 an = 3n CMSC 203 - Discrete Structures 4 Strings Finite sequences are also called strings, denoted by a1a2a3…an. The length of a string S is the number of terms that it consists of. The empty string contains no terms at all. It has length zero. Fall 2002 CMSC 203 - Discrete Structures 5 Summations What does n a j m j stand for? It represents the sum am + am+1 + am+2 + … + an. The variable j is called the index of summation, running from its lower limit m to its upper limit n. We could as well have used any other letter to denote this index. Fall 2002 CMSC 203 - Discrete Structures 6 Summations How can we express the sum of the first 1000 terms of the sequence {an} with an=n2 for n = 1, 2, 3, … ? We write it as 1000 j 1 j2 . What is the value of 6 j ? j 1 It is 1 + 2 + 3 + 4 + 5 + 6 = 21. What is the value of 100 j ? j 1 It is so much work to calculate this… Fall 2002 CMSC 203 - Discrete Structures 7 Summations It is said that Friedrich Gauss came up with the following formula: n(n 1) j 2 j 1 n When you have such a formula, the result of any summation can be calculated much more easily, for example: 100(100 1) 10100 j 5050 2 2 j 1 100 Fall 2002 CMSC 203 - Discrete Structures 8 Arithemetic Series How does: n(n 1) j 2 j 1 n ??? Observe that: 1 + 2 + 3 +…+ n/2 + (n/2 + 1) +…+ (n - 2) + (n - 1) + n = [1 + n] + [2 + (n - 1)] + [3 + (n - 2)] +…+ [n/2 + (n/2 + 1)] = (n + 1) + (n + 1) + (n + 1) + … + (n + 1) (with n/2 terms) = n(n + 1)/2. Fall 2002 CMSC 203 - Discrete Structures 9 Geometric Series How does: ( n 1) a 1 ??? j a (a 1) j 0 n Observe that: S = 1 + a + a 2 + a 3 + … + an aS = a + a2 + a3 + … + an + a(n+1) so, (aS - S) = (a - 1)S = a(n+1) - 1 Therefore, 1 + a + a2 + … + an = (a(n+1) - 1) / (a - 1). For example: 1 + 2 + 4 + 8 +… + 1024 = 2047. Fall 2002 CMSC 203 - Discrete Structures 10 Useful Series 1. 2. 3. 4. n(n 1) j 2 j 1 ( n 1) n a 1 j a (a 1) j 0 n n(n 1)( 2n 1) 2 j 6 j 1 2 2 n n ( n 1 ) 3 j 4 j 1 n Fall 2002 CMSC 203 - Discrete Structures 11 Double Summations Corresponding to nested loops in C or Java, there is also double (or triple etc.) summation: Example: 5 2 ij i 1 j 1 5 (i 2i ) i 1 5 3i i 1 3 6 9 12 15 45 Fall 2002 CMSC 203 - Discrete Structures 12 Double Summations Table 2 in Section 1.7 contains some very useful formulas for calculating sums. Exercises 15 and 17 make a nice homework. Fall 2002 CMSC 203 - Discrete Structures 13