\f\f\f\f\f\f\f\f\f\fSequences, Mathematical Induction and Recursion 1 5.1 Sequences 2 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 a n a term of the sequence. Example: subset of N: S: 1 2 3 4 5 ... 2 4 6 8 10 ... 3 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. 4 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, ... 2, 5, 10, 17, 26, ... 0.25, 0.5, 0.75, 1, 1.25 ... 3, 9, 27, 81, 243, ... an = (-1)n an = n2 + 1 an = 0.25n an = 3 n 5 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. 6 Summations n What does a j j m 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. 7 Summations How can we express the sum of the first 1000 terms of the sequence {an} with an=n2 for 1000 n = 1, 2, 3, ... ? j 2 We write it as . j 1 What is the value of ? 6 j j 1 It is 1 + 2 + 3 + 4 + 5 + 6 = 21. 100 What is the value j j 1 of ? It is so much work to calculate this... 8 Summations It is said that Friedrich Gauss came up with the following formula: n j 1 n(n 1) j 2 When you have such a formula, the result of any summation can be calculated much more easily, for example: 100 j 1 100(100 1) 10100 j 5050 2 2 9 Arithemetic Series How does: n j 1 n(n 1) j 2 ??? 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. 10 Geometric Series a ( n 1) 1 ??? How does: aj (a 1) j 0 n Observe that: S = 1 + a + a 2 + a3 + ... + a n 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).example: 1 + 2 + 4 + 8 +... + 1024 = For 2047. 11 Useful Series n 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 n n 2 (n 1) 2 j3 4 j 1 12 Product Notation n What does ak stand for? k m 13 5.2 Mathematical Induction 14 Induction The principle of mathematical induction is a useful tool for proving that a certain predicate is true for all natural numbers. It cannot be used to discover theorems, but only to prove them. 15 Induction If we have a propositional function P(n), and we want to prove that P(n) is true for any natural number n, we do the following: Show that P(0) is true. (basis step) Show that if P(n) then P(n + 1) for any nN. (inductive step) Then P(n) must be true for any nN. (conclusion) 16 Induction Example: Show that n < 2n for all positive integers n. Let P(n) be the proposition \"n < 2n.\" 1. Show that P(1) is true. (basis step) P(1) is true, because 1 < 21 = 2. 17 Induction 2. Show that if P(n) is true, then P(n + 1) is true. (inductive step) Assume that n < 2n is true. We need to show that P(n + 1) is true, i.e. n + 1 < 2n+1 We start from n < 2n: n + 1 < 2n + 1 2n + 2n = 2n+1 Therefore, if n < 2n then n + 1 < 2n+1 18 Induction 3. Then P(n) must be true for any positive integer. (conclusion) n < 2n is true for any positive integer. End of proof. 19 Induction Another Example (\"Gauss\"): 1 + 2 + ... + n = n (n + 1)/2 1. Show that P(0) is true. (basis step) For n = 0 we get 0 = 0. True. 20 Induction 2. Show that if P(n) then P(n + 1) for any nN. (inductive step) 1 + 2 + ... + n = n (n + 1)/2 1 + 2 + ... + n + (n + 1) = n (n + 1)/2 + (n + 1) = (2n + 2 + n (n + 1))/2 = (2n + 2 + n2 + n)/2 = (2 + 3n + n2 )/2 = (n + 1) (n + 2)/2 = (n + 1) ((n + 1) + 1)/2 21 Induction 3. Then P(n) must be true for any nN. (conclusion) 1 + 2 + ... + n = n (n + 1)/2 is true for all nN. End of proof. 22 Induction There is another proof technique that is very similar to the principle of mathematical induction. It is called the second principle of mathematical induction. It can be used to prove that a propositional function P(n) is true for any natural number n. 23 Induction The second principle of mathematical induction: Show that P(0) is true. (basis step) Show that if P(0) and P(1) and ... and P(n), then P(n + 1) for any nN. (inductive step) Then P(n) must be true for any nN. (conclusion) 24 Induction Example: Show that every integer greater than 1 can be written as the product of primes. Show that P(2) is true. (basis step) 2 is the product of one prime: itself. 25 Induction Show that if P(2) and P(3) and ... and P(n), then P(n + 1) for any nN. (inductive step) Two possible cases: If (n + 1) is prime, then obviously P(n + 1) is true. If (n + 1) is composite, it can be written as the product of two integers a and b such that 2 a b < n + 1. By the induction hypothesis, both a and b can be written as the product of primes. Therefore, n + 1 = ab can be written as the product of primes. 26 Induction Then P(n) must be true for any nN. (conclusion) End of proof. We have shown that every integer greater than 1 can be written as the product of primes. 27 5.6 Defining Sequences Recursively 28 Recurrence Relations A recurrence relation for the sequence {an} is an equation that expresses an is terms of one or more of the previous terms of the sequence, namely, a0, a1, ..., an-1, for all integers n with n n0, where n0 is a nonnegative integer. A sequence is called a solution of a recurrence relation if it terms satisfy the recurrence relation. 29 Recurrence Relations In other words, a recurrence relation is like a recursively defined sequence, but without specifying any initial values (initial conditions). Therefore, the same recurrence relation can have (and usually has) multiple solutions. If both the initial conditions and the recurrence relation are specified, then the sequence is uniquely determined. 30 Recurrence Relations Example: Consider the recurrence relation an = 2an-1 - an-2 for n = 2, 3, 4, ... Is the sequence {an} with an=3n a solution of this recurrence relation? For n 2 we see that 2an-1 - an-2 = 2(3(n - 1)) - 3(n - 2) = 3n = an. Therefore, {an} with an=3n is a solution of the recurrence relation. 31 Recurrence Relations Is the sequence {an} with an=5 a solution of the same recurrence relation? For n 2 we see that 2an-1 - an-2 = 25 - 5 = 5 = an. Therefore, {an} with an=5 is also a solution of the recurrence relation. 32 Modeling with Recurrence Relations Example: Someone deposits $10,000 in a savings account at a bank yielding 5% per year with interest compounded annually. How much money will be in the account after 30 years? Solution: Let Pn denote the amount in the account after n years. How can we determine Pn on the basis of Pn-1? 33 Modeling with Recurrence Relations We can derive the following recurrence relation: Pn = Pn-1 + 0.05Pn-1 = 1.05Pn-1. The initial condition is P0 = 10,000. Then we have: P1 = 1.05P0 P2 = 1.05P1 = (1.05)2P0 P3 = 1.05P2 = (1.05)3P0 ... Pn = 1.05Pn-1 = (1.05)nP0 We now have a formula to calculate Pn for any natural number n and can avoid the iteration. 34 Modeling with Recurrence Relations Let us use this formula to find P30 under the initial condition P0 = 10,000: P30 = (1.05)3010,000 = 43,219.42 After 30 years, the account contains $43,219.42. 35 The Towers of Hanoi A Legend Legend has it that there were three diamond needles set into the floor of the temple of Brahma in Hanoi. Stacked upon the leftmost needle were 64 golden disks, each a different size, stacked in concentric order: A Legend (Ct'd) The priests were to transfer the disks from the first needle to the second needle, using the third as necessary. But they could only move one disk at a time, and could never put a larger disk on top of a smaller one. When they completed this task, the world would To Illustrate For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... Since we can only move one disk at a time, we move the top disk from A to B. Example For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... We then move the top disk from A to C. Example (Ct'd) For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... We then move the top disk from B to C. Example (Ct'd) For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... We then move the top disk from A to B. Example (Ct'd) For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... We then move the top disk from C to A. Example (Ct'd) For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... We then move the top disk from C to B. Example (Ct'd) For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... We then move the top disk from A to B. Example (Ct'd) For simplicity, suppose there were just 3 disks, and we'll refer to the three needles as A, B, and C... and we're done! The problem gets more difficult as the number of disks increases... Our Problem Today's problem is to write a program that generates the instructions for the priests to follow in moving the disks. While quite difficult to solve iteratively, this problem has a simple and elegant recursive solution. Analysis For flexibility, let's allow the user to enter the number of disks for which they wish a set of instructions: /* hanoi.cpp * ... */ void Move(int n, char src, char dest, char aux); int main() { cout << \"\ \ The Hanoi Towers!\ \ \" << \"Enter how many disks: \"; int numDisks; cin >> numDisks; } Move(numDisks, 'A', 'B', 'C'); Analysis (Ct'd) Our task, then is to write function Move() that does all the work: /* hanoi.cpp * ... */ void Move(int n, char src, char dest, char aux); int main() { cout << \"\ \ The Hanoi Towers!\ \ \" << \"Enter how many disks: \"; int numDisks; cin >> numDisks; } Move(numDisks, 'A', 'B', 'C'); Design Basis: What is an instance of the problem that is trivial? n == 1 Since this base case could occur when the disk is on any needle, we simply output the instruction to move the top disk from src to dest. Design Basis: What is an instance of the problem that is trivial? n == 1 Since this base case could occur when the disk is on any needle, we simply output the instruction to move the top disk from src to dest. Design (Ct'd) Induction Step: n > 1 How can recursion help us out? a. Recursively move n-1 disks from src to aux. Design (Ct'd) Induction Step: n > 1 How can recursion help us out? b. Move the one remaining disk from src to dest. Design (Ct'd) Induction Step: n > 1 How can recursion help us out? c. Recursively move n-1 disks from aux to dest... Design (Ct'd) Induction Step: n > 1 How can recursion help us out? d. We're done! Algorithm We can combine these steps into the following algorithm: 0.Receive n, src, dest, aux. 0.Receive aux. 1. If n > 1: a. Move(n-1, src, aux, dest); Move(n-1, dest); b. Move(1, src, dest, aux); aux); c. Move(n-1, aux, dest, src); Move(n-1, src); Else Display \"Move the top disk from \