From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU Mon Mar 17 21:19:54 2008 Date: Mon, 17 Mar 2008 21:19:38 -0400 From: "William J. Rapaport" Subject: 191: Sequences and Summations -- further information To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU ------------------------------------------------------------------------ Subject: 191: Sequences and Summations -- further information ------------------------------------------------------------------------ There are just a couple of things I wanted to mention about sequences and summations but that I don't want to take up valuable class time for. So I'll mention them in this email message. 1. ------------------------------------------------------------------------ Recall that a sequence is the output (i.e., the range) of a function whose input (i.e., whose domain) is either the set of positive integers (Z+ = {1,2,3,...}) or the set of natural numbers (N = {0,1,2,3,...}), depending on whether it's more convenient to begin counting with 1 or 0. The name of the function is often "a", and instead of writing the outputs as a(0), a(1), a(2), etc., they are often written using subscripts, which I'll write (in this typewriter font) as: a0, a1, a2, ... To avoid confusion, I'll sometimes write: a_0, a_1, a_2, ..., a_n, a_(n+1), ... Here are a couple of examples: a) 0,1,4,9,16,25,... This is a sequence where a0 = 0 a1 = 1 a2 = 4 a3 = 9 a4 = 16 a5 = 25, etc. It can be described as follows: a_n = n^2, for all n b) 0,1,1,2,3,5,8,13,... This is a sequence where a0 = 0 a1 = 1 a2 = 1 a3 = 2 a4 = 3 a5 = 5 a6 = 8 a7 = 13, etc. It can be described as follows: a0 = 0 a1 = 1 a_n = a_(n-1) + a_(n-2), for all n > 1 In other words, the first term of the sequence is 0, the next is 1, and each one afterwards is the sum of the two preceding terms. It's a famous sequence that we'll see again, called the Fibonacci (pronounced "fib-o-NAH-tchi") sequence. (By the way, some people start it at a1, not a0; it can also be continued backwards to a_-1, a_-2, etc. You might want to try to figure out what those terms of the sequence might be.) I've mentioned the famous SAT/IQ-test questions where they give you a sequence and ask you what "the" next member is, and I've made fun of them because there is no such thing as "the" next member. Any number could be the next member. In other words, there's nothing wrong with a sequence described as follows: a0 = 0 a1 = 1 a2 = 2 a3 = 3 a4 = 4 a5 = 5 Do you think a6 = 6? It might. But I could continue as follows if I want to be perverse: a_n = 27^n, for all n such that 5 < n < 123 a_n = 3, for all n >= 123 I.e., the sequence is: 0, 1, 2, 3, 4, 5, 27^6, 27^7, 27^8, ..., 27^122, 3, 3, ... That's a weird, uninteresting sequence, but it **is** a sequence. Douglas Hofstadter, author of one of the best books on computation and cognition (it won the Pulitzer Prize for non-fiction when it was published)--_Goedel, Escher, Bach: An Eternal Golden Braid_--has done a lot of computational research on how to get computers to figure out **plausible** "next" members of sequences, in a book called _Fluid Concepts and Creative Analogies_. And don't forget to check out The On-Line Encyclopedia of Integer Sequences; the link is at: http://www.cse.buffalo.edu/~rapaport/191/S08/functions.html 2. Summations (which I've asked you to read about in Sect. 2.4, which are on HW #7, and which will be on the final exam :-) are simply the sums of the terms in a sequence. Some people call them "series" instead of summations (I've never figured out why). I.e., a summation is, by definition, the sum of some or all terms in a sequence. So, given the sequence a1, a2, ..., a_n, ... the corresponding summation is a1 + a2 + ... + a_n + ... You'd think that this would be a very large number (after all, you keep adding more and more numbers), and it often is quite large, but sometimes such a summation "converges" to a finite number and turns out to be a convenient way to compute the number that is the sum. For instance, consider this sequence: 1, -1/3, 1/5, -1/7, 1/9, ... where: if Odd(n), then a_n = +1/(2n-1) else a_n = -1/(2n-1) Check it out: Odd(1), so a1 = 1/(2*1 - 1) = 1/(2-1) = 1/1 = 1 Even(2), so a2 = -1/(2*2 - 1) = -1/(4-1) = -1/3 etc. Now consider its summation: 1 + -1/3 + 1/5 + -1/7 + 1/9 + ... = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ... As you might guess, this converges (i.e., it does not get infinitely large). After all, each time we're adding on a smaller fraction, and some of them are negative, so we're actually subtracting them. All of that will surely make each successive "partial" sum only a very little bit bigger than the previous some, and in some cases, it'll be smaller. Let's compute the partial sums: The sum of the first term is just 1. The sum of the first 2 terms is 1 - 1/3 = 2/3 = 0.666666666666666666... The sum of the first 3 terms is 1 - 1/3 + 1/5 = 0.66... + 0.2 = 0.8666... The sum of the first 4 terms is 1 - 1/3 + 1/5 - 1/7 = 0.866... - 0.1428571... = 0.723809523... The sum of the first 5 terms is 0.723809523... + 1/9 = 0.723809523... + 0.11111.... = 0.834920634... etc. It turns out (and I **won't** ask you to prove this!) that the sum of the infinite sequence is (get ready... drum roll, please): pi/4 (!) (Consider what happens when you multiply each term in the summation by 4: 4 - 4/3 + 4/5 - 4/7 + 4/9 - ... The partial sum of these first 5 terms is 3.33968253...; it's getting close to pi.) So, you could write a computer program to compute pi to any degree of accuracy (i.e., to any position in the decimal expansion of pi) by writing a for-loop (or a "count-loop") that adds up these numbers. It doesn't always happen that a series like this converges. Consider: 1 + 1/2 + 1/3 + 1/4 + 1/5 + ... This diverges! (I.e., it grows infinitely large, despite the fact that each number you add on is smaller than the previous one! It's just that it's not small enough to make the summation converge.) The final point about summations that I want to make is the notation for it, which I can't really show very well in this typewriter font. The symbol for a summation is the capital Greek letter sigma (which kind of looks like a backwards "3" with angles instead of curves: -- \ / -- is about the best I can do with this typewriter font. Instead, I'll write it as: SIGMA Just as with the big union and big intersection symbols, we can use this as a shorthand, so, instead of writing: a1 + a2 + a3 + a4 + ... we'll write: SIGMA a_n but we have to say where n begins and where it "ends". Typically, for an infinite summation, it won't end, so we use the infinity sign, which looks like the numeral "8" lying on its side. I'll write it as: infty Below the SIGMA, we write something like "n=1" or "n=0" to indicate where we start adding, depending on whether the range of the sequence is Z+ or N, and above the SIGMA we write either "n=k", if we want to stop at the k-th term, or "infty" if we want the infinite sum. So the summation above could be written something like: infty SIGMA a_n n=1 It is essentially what programming languages call a "for-loop" or a "count-loop": For n = 1 to infinity, or for n = 1 to k, add up the numbers or the output of the function (i.e., the numbers in the sequence). If we write it like this: SIGMA n [a_n] then it kind of looks like a quantifier expression with a bound variable.