Recurrence Relations in Discrete Structures

1. Fall 2002 CMSC 203 - Discrete Structures 1 Now its Time for Now its Time for Recurrence Recurrence Relations Relations

2. Fall 2002 CMSC 203 - Discrete Structures 2 Recurrence Relations Recurrence Relations A recurrence relation for the sequence {a n } is an equation that expresses a n is terms of one or more of the previous terms of the sequence, namely, a 0 , a 1 , , a n-1 , for all integers n with n n 0 , where n 0 is a nonnegative integer. A recurrence relation for the sequence {a n } is an equation that expresses a n is terms of one or more of the previous terms of the sequence, namely, a 0 , a 1 , , a n-1 , for all integers n with n n 0 , where n 0 is a nonnegative integer. A sequence is called a solution of a recurrence relation if it terms satisfy the recurrence relation. A sequence is called a solution of a recurrence relation if it terms satisfy the recurrence relation.

3. Fall 2002 CMSC 203 - Discrete Structures 3 Recurrence Relations Recurrence Relations In other words, a recurrence relation is like a recursively defined sequence, but without specifying any initial values (initial conditions) . 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 . 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. If both the initial conditions and the recurrence relation are specified, then the sequence is uniquely determined.

4. Fall 2002 CMSC 203 - Discrete Structures 4 Recurrence Relations Recurrence Relations Example: Consider the recurrence relation a n = 2a n-1 a n-2 for n = 2, 3, 4, Example: Consider the recurrence relation a n = 2a n-1 a n-2 for n = 2, 3, 4, Is the sequence {a n } with a n =3n a solution of this recurrence relation? Is the sequence {a n } with a n =3n a solution of this recurrence relation? For n 2 we see that 2a n-1 a n-2 = 2(3(n 1)) 3(n 2) = 3n = a n . For n 2 we see that 2a n-1 a n-2 = 2(3(n 1)) 3(n 2) = 3n = a n . Therefore, {a n } with a n =3n is a solution of the recurrence relation. Therefore, {a n } with a n =3n is a solution of the recurrence relation.

5. Fall 2002 CMSC 203 - Discrete Structures 5 Recurrence Relations Recurrence Relations Is the sequence {a n } with a n =5 a solution of the same recurrence relation? Is the sequence {a n } with a n =5 a solution of the same recurrence relation? For n 2 we see that 2a n-1 a n-2 = 2 5 - 5 = 5 = a n . For n 2 we see that 2a n-1 a n-2 = 2 5 - 5 = 5 = a n . Therefore, {a n } with a n =5 is also a solution of the recurrence relation. Therefore, {a n } with a n =5 is also a solution of the recurrence relation.

6. Fall 2002 CMSC 203 - Discrete Structures 6 Modeling with Recurrence Relations Modeling with Recurrence Relations Example: 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? 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: Solution: Let P n denote the amount in the account after n years. Let P n denote the amount in the account after n years. How can we determine P n on the basis of P n-1 ? How can we determine P n on the basis of P n-1 ?

7. Fall 2002 CMSC 203 - Discrete Structures 7 Modeling with Recurrence Relations Modeling with Recurrence Relations We can derive the following recurrence relation : We can derive the following recurrence relation : P n = P n-1 + 0.05P n-1 = 1.05P n-1 . P n = P n-1 + 0.05P n-1 = 1.05P n-1 . The initial condition is P 0 = 10,000. The initial condition is P 0 = 10,000. Then we have: Then we have: P 1 = 1.05P 0 P 1 = 1.05P 0 P 2 = 1.05P 1 = (1.05) 2 P 0 P 2 = 1.05P 1 = (1.05) 2 P 0 P 3 = 1.05P 2 = (1.05) 3 P 0 P 3 = 1.05P 2 = (1.05) 3 P 0 P n = 1.05P n-1 = (1.05) n P 0 P n = 1.05P n-1 = (1.05) n P 0 We now have a formula to calculate P n for any natural number n and can avoid the iteration. We now have a formula to calculate P n for any natural number n and can avoid the iteration.

8. Fall 2002 CMSC 203 - Discrete Structures 8 Modeling with Recurrence Relations Modeling with Recurrence Relations Let us use this formula to find P 30 under the Let us use this formula to find P 30 under the initial condition P 0 = 10,000: initial condition P 0 = 10,000: P 30 = (1.05) 30 10,000 = 43,219.42 P 30 = (1.05) 30 10,000 = 43,219.42 After 30 years, the account contains $43,219.42. After 30 years, the account contains $43,219.42.

9. Fall 2002 CMSC 203 - Discrete Structures 9 Modeling with Recurrence Relations Modeling with Recurrence Relations Another example: Another example: Let a n denote the number of bit strings of length n that do not have two consecutive 0s (valid strings). Find a recurrence relation and give initial conditions for the sequence {a n }. Let a n denote the number of bit strings of length n that do not have two consecutive 0s (valid strings). Find a recurrence relation and give initial conditions for the sequence {a n }. Solution: Solution: Idea: The number of valid strings equals the number of valid strings ending with a 0 plus the number of valid strings ending with a 1. Idea: The number of valid strings equals the number of valid strings ending with a 0 plus the number of valid strings ending with a 1.

10. Fall 2002 CMSC 203 - Discrete Structures 10 Modeling with Recurrence Relations Modeling with Recurrence Relations Let us assume that n 3, so that the string contains at least 3 bits. Let us assume that n 3, so that the string contains at least 3 bits. Let us further assume that we know the number a n-1 of valid strings of length (n 1). Let us further assume that we know the number a n-1 of valid strings of length (n 1). Then how many valid strings of length n are there, if the string ends with a 1? Then how many valid strings of length n are there, if the string ends with a 1? There are a n-1 such strings, namely the set of valid strings of length (n 1) with a 1 appended to them. There are a n-1 such strings, namely the set of valid strings of length (n 1) with a 1 appended to them. Note: Whenever we append a 1 to a valid string, that string remains valid. Note: Whenever we append a 1 to a valid string, that string remains valid.

11. Fall 2002 CMSC 203 - Discrete Structures 11 Modeling with Recurrence Relations Modeling with Recurrence Relations Now we need to know: How many valid strings of length n are there, if the string ends with a 0 ? Now we need to know: How many valid strings of length n are there, if the string ends with a 0 ? Valid strings of length n ending with a 0 must have a 1 as their (n 1)st bit (otherwise they would end with 00 and would not be valid). Valid strings of length n ending with a 0 must have a 1 as their (n 1)st bit (otherwise they would end with 00 and would not be valid). And what is the number of valid strings of length (n 1) that end with a 1? And what is the number of valid strings of length (n 1) that end with a 1? We already know that there are a n-1 strings of length n that end with a 1. We already know that there are a n-1 strings of length n that end with a 1. Therefore, there are a n-2 strings of length (n 1) that end with a 1. Therefore, there are a n-2 strings of length (n 1) that end with a 1.

12. Fall 2002 CMSC 203 - Discrete Structures 12 Modeling with Recurrence Relations Modeling with Recurrence Relations So there are a n-2 valid strings of length n that end with a 0 (all valid strings of length (n 2) with 10 appended to them). So there are a n-2 valid strings of length n that end with a 0 (all valid strings of length (n 2) with 10 appended to them). As we said before, the number of valid strings is the number of valid strings ending with a 0 plus the number of valid strings ending with a 1. As we said before, the number of valid strings is the number of valid strings ending with a 0 plus the number of valid strings ending with a 1. That gives us the following recurrence relation : That gives us the following recurrence relation : a n = a n-1 + a n-2 a n = a n-1 + a n-2

13. Fall 2002 CMSC 203 - Discrete Structures 13 Modeling with Recurrence Relations Modeling with Recurrence Relations What are the initial conditions ? What are the initial conditions ? a 1 = 2 (0 and 1) a 1 = 2 (0 and 1) a 2 = 3 (01, 10, and 11) a 2 = 3 (01, 10, and 11) a 3 = a 2 + a 1 = 3 + 2 = 5 a 3 = a 2 + a 1 = 3 + 2 = 5 a 4 = a 3 + a 2 = 5 + 3 = 8 a 4 = a 3 + a 2 = 5 + 3 = 8 a 5 = a 4 + a 3 = 8 + 5 = 13 a 5 = a 4 + a 3 = 8 + 5 = 13 This sequence satisfies the same recurrence relation as the Fibonacci sequence . This sequence satisfies the same recurrence relation as the Fibonacci sequence . Since a 1 = f 3 and a 2 = f 4 , we have a n = f n+2 . Since a 1 = f 3 and a 2 = f 4 , we have a n = f n+2 .

14. Fall 2002 CMSC 203 - Discrete Structures 14 Solving Recurrence Relations Solving Recurrence Relations In general, we would prefer to have an explicit formula to compute the value of a n rather than conducting n iterations. In general, we would prefer to have an explicit formula to compute the value of a n rather than conducting n iterations. For one class of recurrence relations, we can obtain such formulas in a systematic way. For one class of recurrence relations, we can obtain such formulas in a systematic way. Those are the recurrence relations that express the terms of a sequence as linear combinations of previous terms. Those are the recurrence relations that express the terms of a sequence as linear combinations of previous terms.

15. Fall 2002 CMSC 203 - Discrete Structures 15 Solving Recurrence Relations Solving Recurrence Relations Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form: Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form: a n = c 1 a n-1 + c 2 a n-2 + + c k a n-k , a n = c 1 a n-1 + c 2 a n-2 + + c k a n-k , Where c 1 , c 2 , , c k are real numbers, and c k 0. Where c 1 , c 2 , , c k are real numbers, and c k 0. A sequence satisfying such a recurrence relation is uniquely determined by the recurrence relation and the k initial conditions A sequence satisfying such a recurrence relation is uniquely determined by the recurrence relation and the k initial conditions a 0 = C 0 , a 1 = C 1 , a 2 = C 2 , , a k-1 = C k-1 . a 0 = C 0 , a 1 = C 1 , a 2 = C 2 , , a k-1 = C k-1 .

16. Fall 2002 CMSC 203 - Discrete Structures 16 Solving Recurrence Relations Solving Recurrence Relations Examples: Examples: The recurrence relation P n = (1.05)P n-1 The recurrence relation P n = (1.05)P n-1 is a linear homogeneous recurrence relation of degree one . is a linear homogeneous recurrence relation of degree one . The recurrence relation f n = f n-1 + f n-2 The recurrence relation f n = f n-1 + f n-2 is a linear homogeneous recurrence relation of degree two . is a linear homogeneous recurrence relation of degree two . The recurrence relation a n = a n-5 The recurrence relation a n = a n-5 is a linear homogeneous recurrence relation of degree five . is a linear homogeneous recurrence relation of degree five .

17. Fall 2002 CMSC 203 - Discrete Structures 17 Solving Recurrence Relations Solving Recurrence Relations Basically, when solving such recurrence relations, we try to find solutions of the form a n = r n , where r is a constant. Basically, when solving such recurrence relations, we try to find solutions of the form a n = r n , where r is a constant. a n = r n is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 + + c k a n-k if and only if a n = r n is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 + + c k a n-k if and only if r n = c 1 r n-1 + c 2 r n-2 + + c k r n-k . r n = c 1 r n-1 + c 2 r n-2 + + c k r n-k . Divide this equation by r n-k and subtract the right-hand side from the left: Divide this equation by r n-k and subtract the right-hand side from the left: r k - c 1 r k-1 - c 2 r k-2 - - c k-1 r - c k = 0 r k - c 1 r k-1 - c 2 r k-2 - - c k-1 r - c k = 0 This is called the characteristic equation of the recurrence relation. This is called the characteristic equation of the recurrence relation.

18. Fall 2002 CMSC 203 - Discrete Structures 18 Solving Recurrence Relations Solving Recurrence Relations The solutions of this equation are called the characteristic roots of the recurrence relation. The solutions of this equation are called the characteristic roots of the recurrence relation. Let us consider linear homogeneous recurrence relations of degree two . Let us consider linear homogeneous recurrence relations of degree two . Theorem: Let c 1 and c 2 be real numbers. Suppose that r 2 c 1 r c 2 = 0 has two distinct roots r 1 and r 2 . Theorem: Let c 1 and c 2 be real numbers. Suppose that r 2 c 1 r c 2 = 0 has two distinct roots r 1 and r 2 . Then the sequence {a n } is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 if and only if a n = 1 r 1 n + 2 r 2 n for n = 0, 1, 2, , where 1 and 2 are constants. Then the sequence {a n } is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 if and only if a n = 1 r 1 n + 2 r 2 n for n = 0, 1, 2, , where 1 and 2 are constants. See pp. 321 and 322 for the proof. See pp. 321 and 322 for the proof.

19. Fall 2002 CMSC 203 - Discrete Structures 19 Solving Recurrence Relations Solving Recurrence Relations Example: What is the solution of the recurrence relation a n = a n-1 + 2a n-2 with a 0 = 2 and a 1 = 7 ? Example: What is the solution of the recurrence relation a n = a n-1 + 2a n-2 with a 0 = 2 and a 1 = 7 ? Solution: The characteristic equation of the recurrence relation is r 2 r 2 = 0. Solution: The characteristic equation of the recurrence relation is r 2 r 2 = 0. Its roots are r = 2 and r = -1. Its roots are r = 2 and r = -1. Hence, the sequence {a n } is a solution to the recurrence relation if and only if: Hence, the sequence {a n } is a solution to the recurrence relation if and only if: a n = 1 2 n + 2 (-1) n for some constants 1 and 2 . a n = 1 2 n + 2 (-1) n for some constants 1 and 2 .

20. Fall 2002 CMSC 203 - Discrete Structures 20 Solving Recurrence Relations Solving Recurrence Relations Given the equation a n = 1 2 n + 2 (-1) n and the initial conditions a 0 = 2 and a 1 = 7, it follows that Given the equation a n = 1 2 n + 2 (-1) n and the initial conditions a 0 = 2 and a 1 = 7, it follows that a 0 = 2 = 1 + 2 a 0 = 2 = 1 + 2 a 1 = 7 = 1 2 + 2 (-1) a 1 = 7 = 1 2 + 2 (-1) Solving these two equations gives us 1 = 3 and 2 = -1. Solving these two equations gives us 1 = 3 and 2 = -1. Therefore, the solution to the recurrence relation and initial conditions is the sequence {a n } with Therefore, the solution to the recurrence relation and initial conditions is the sequence {a n } with a n = 3 2 n (-1) n . a n = 3 2 n (-1) n .

21. Fall 2002 CMSC 203 - Discrete Structures 21 Solving Recurrence Relations Solving Recurrence Relations a n = r n is a solution of the linear homogeneous recurrence relation a n = c 1 a n-1 + c 2 a n-2 + + c k a n-k a n = r n is a solution of the linear homogeneous recurrence relation a n = c 1 a n-1 + c 2 a n-2 + + c k a n-k if and only if if and only if r n = c 1 r n-1 + c 2 r n-2 + + c k r n-k . r n = c 1 r n-1 + c 2 r n-2 + + c k r n-k . Divide this equation by r n-k and subtract the right-hand side from the left: Divide this equation by r n-k and subtract the right-hand side from the left: r k - c 1 r k-1 - c 2 r k-2 - - c k-1 r - c k = 0 r k - c 1 r k-1 - c 2 r k-2 - - c k-1 r - c k = 0 This is called the characteristic equation of the recurrence relation. This is called the characteristic equation of the recurrence relation.

22. Fall 2002 CMSC 203 - Discrete Structures 22 Solving Recurrence Relations Solving Recurrence Relations The solutions of this equation are called the characteristic roots of the recurrence relation. The solutions of this equation are called the characteristic roots of the recurrence relation. Let us consider linear homogeneous recurrence relations of degree two . Let us consider linear homogeneous recurrence relations of degree two . Theorem: Let c 1 and c 2 be real numbers. Suppose that r 2 c 1 r c 2 = 0 has two distinct roots r 1 and r 2 . Theorem: Let c 1 and c 2 be real numbers. Suppose that r 2 c 1 r c 2 = 0 has two distinct roots r 1 and r 2 . Then the sequence {a n } is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 if and only if a n = 1 r 1 n + 2 r 2 n for n = 0, 1, 2, , where 1 and 2 are constants. Then the sequence {a n } is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 if and only if a n = 1 r 1 n + 2 r 2 n for n = 0, 1, 2, , where 1 and 2 are constants. See pp. 321 and 322 for the proof. See pp. 321 and 322 for the proof.

23. Fall 2002 CMSC 203 - Discrete Structures 23 Solving Recurrence Relations Solving Recurrence Relations Example: Give an explicit formula for the Fibonacci numbers. Example: Give an explicit formula for the Fibonacci numbers. Solution: The Fibonacci numbers satisfy the recurrence relation f n = f n-1 + f n-2 with initial conditions f 0 = 0 and f 1 = 1. Solution: The Fibonacci numbers satisfy the recurrence relation f n = f n-1 + f n-2 with initial conditions f 0 = 0 and f 1 = 1. The characteristic equation is r 2 r 1 = 0. The characteristic equation is r 2 r 1 = 0. Its roots are Its roots are

24. Fall 2002 CMSC 203 - Discrete Structures 24 Solving Recurrence Relations Solving Recurrence Relations Therefore, the Fibonacci numbers are given by Therefore, the Fibonacci numbers are given by for some constants 1 and 2 . for some constants 1 and 2 . We can determine values for these constants so that the sequence meets the conditions f 0 = 0 and f 1 = 1: We can determine values for these constants so that the sequence meets the conditions f 0 = 0 and f 1 = 1:

25. Fall 2002 CMSC 203 - Discrete Structures 25 Solving Recurrence Relations Solving Recurrence Relations The unique solution to this system of two equations and two variables is The unique solution to this system of two equations and two variables is So finally we obtained an explicit formula for the Fibonacci numbers: So finally we obtained an explicit formula for the Fibonacci numbers:

26. Fall 2002 CMSC 203 - Discrete Structures 26 Solving Recurrence Relations Solving Recurrence Relations But what happens if the characteristic equation has only one root? But what happens if the characteristic equation has only one root? How can we then match our equation with the initial conditions a 0 and a 1 ? How can we then match our equation with the initial conditions a 0 and a 1 ? Theorem: Let c 1 and c 2 be real numbers with c 2 0. Suppose that r 2 c 1 r c 2 = 0 has only one root r 0 . A sequence {a n } is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 if and only if a n = 1 r 0 n + 2 nr 0 n , for n = 0, 1, 2, , where 1 and 2 are constants. Theorem: Let c 1 and c 2 be real numbers with c 2 0. Suppose that r 2 c 1 r c 2 = 0 has only one root r 0 . A sequence {a n } is a solution of the recurrence relation a n = c 1 a n-1 + c 2 a n-2 if and only if a n = 1 r 0 n + 2 nr 0 n , for n = 0, 1, 2, , where 1 and 2 are constants.

27. Fall 2002 CMSC 203 - Discrete Structures 27 Solving Recurrence Relations Solving Recurrence Relations Example: What is the solution of the recurrence relation a n = 6a n-1 9a n-2 with a 0 = 1 and a 1 = 6? Example: What is the solution of the recurrence relation a n = 6a n-1 9a n-2 with a 0 = 1 and a 1 = 6? Solution: The only root of r 2 6r + 9 = 0 is r 0 = 3. Hence, the solution to the recurrence relation is Solution: The only root of r 2 6r + 9 = 0 is r 0 = 3. Hence, the solution to the recurrence relation is a n = 1 3 n + 2 n3 n for some constants 1 and 2 . a n = 1 3 n + 2 n3 n for some constants 1 and 2 . To match the initial condition, we need To match the initial condition, we need a 0 = 1 = 1 a 1 = 6 = 1 3 + 2 3 a 0 = 1 = 1 a 1 = 6 = 1 3 + 2 3 Solving these equations yields 1 = 1 and 2 = 1. Solving these equations yields 1 = 1 and 2 = 1. Consequently, the overall solution is given by Consequently, the overall solution is given by a n = 3 n + n3 n . a n = 3 n + n3 n .