Foundations Of Discrete Mathematics Solutions

1. (8) Find the next four terms of the recursively-defined sequence: v k =kv k −1 −v k−2 , for all integers k ≥3 v 1 =1 , v 2 =1 Make sure to show the complete work. No points awarded if only the four terms are written with no work. 2. (9) State the recurrence relation and initial conditions for the sequence S: 2, 4, 10, 28, …, 3n+1, … and explain how you arrived at your answer, in detailed English sentences. 3. (9) Consider the recurrence relation and initial conditions: a n=−3 a n−1 +4 an −2 a 0=5 , a1=−5 Show that a n=2 (−4 ) n +3 for all n  0. (Show means “prove in general”. Showing that it works for a few terms is not a proof. Hint: use induction.) You must explain every step in your proof completely, for full credit. 4. (10) Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induction: a k=kak −1 , for all integers k ≥1 a0 =1 Also, explain how you arrived at your answer in complete English sentences. 5. (14) For problems a to g listed below, write if the given relation is a second-order linear homogeneous recurrence relation with constant coefficients and explain each answer in detail. 3 a. t k = t k−1+7.33t k−2 5 b. h k =( k +1 ) hk−1−3 h k−2 c. d k =3 d k −1−πd k −2 d. r k =r k−1 −r k −2−2 e. s k =100 s k −2 f. c k =c k −1⋅c k −2 2 g. uk =2 uk −1 6. (10) Find an explicit formula for the sequence that is a solution to the following recurrence relation and initial conditions (must use the method of characteristic equation and explain each step in detail): ak = -ak-1 + 6ak-2 , for all integers k ≥2 a0 = 3, a1 = -4 7. (10) Find a solution for the following recurrence relation and initial conditions (use the method of characteristic equation and explain each step in detail): ak = 10ak-1 - 25ak-2 for all integers k ≥2 a0 = 1 and a1 = 15 8. (10) Find a solution for the following recurrence relation and initial conditions (using the method of characteristic equation and explain each step in detail): ak = ak-1 + 2ak-2 for all integers k ≥2 a0 = 15 and a1 = 0 9. (20) Connecting math to programming Choose one from the following two projects (if you have experience writing computer programs, please do the first one, otherwise, do the second one). You can look at solutions online to get ideas, but the work you turn in must be your own. a. Factorial - Write a program that does the following: Given a positive integer n as input, return the factorial of n, which is n(n-1)(n-2)1. Compute the result recursively, without using any loops. Deliverables: By the due date, please turn in the code file and screen shots that show how the program runs. Think of this as showing your “boss” how your program works without running it for him/her in person. It’s your job to convince me that your program works and to explain how it works. It’s not my job to figure out how it works. The code file carries 10 points and the output screen shots carries 10 points. (Include this as separate files in the submission) b. Write a two to three page paper, 12pt font, double-spaced, that explains how what we learned in Chapter 8 about recursion is pertinent to computer science. This should be written at the college level (no spelling or grammar issues) and be as detailed as possible. Turn in your paper as a separate file from the rest of the exam. File attached