Problem set 6 5 (a) Express the number of possible n-day schedules using a recurrence equation and sufficient base cases Solution S(0)=1, S(1)=2 any schedule for n> 1 days ends with one of 3 possible 2-day activities or one of 2 possible 1-day activities. So S(m)=2S(m-1)+3S(n-2 for n >1 (b) Find a closed-form expression for the number of possible n-day schedules br Solution. The characteristic polynomial for this linear homogeneous recurrence is 2-2.c-3=(r+1(a-3). Hence the solution is of the form S(n)=a(-1)"+b3n Letting n=0, we conclude that a+b= l, and letting n= l, we conclude -a+3b= 2, so b=3/4, a=1/4, and the solution is (-1) 4 Problem 6. Find a closed-form expression for T(n), which is defined by the following recurrence T(0)=0 T(1)=1 T(n)=5T(n-1)-6T(n-2)+6 for all n 22 Solution. The characteristic equation is x2-5x+6=0, which has roots r=2 and 3. Thus, the homogenous solution is T(m)=A.2n+B·3 For a particular solution, let's first guess T(n)=c Our guess was correct; T(n)=3 is a particular solution. Adding this to the homogenous solution gives the general solution T(m)=A.2+B.32+3Problem Set 6 5 (a) Express the number of possible n­day schedules using a recurrence equation and sufficient base cases. Solution. S(0) = 1, S(1) = 2. Any schedule for n > 1 days ends with one of 3 possible 2­day activities or one of 2 possible 1­day activities. So S(n) = 2S(n − 1) + 3S(n − 2) for n > 1. (b) Find a closed­form expression for the number of possible n­day schedules by solving the recurrence. Solution. The characteristic polynomial for this linear homogeneous recurrence is 2 x − 2x − 3 = (x + 1)(x − 3). Hence the solution is of the form S(n) = a(−1)n + b3n . Letting n = 0, we conclude that a+b = 1, and letting n = 1, we conclude −a+3b = 2, so b = 3/4, a = 1/4, and the solution is: 3n+1 + (−1)n S(n) = . 4 Problem 6. Find a closed­form expression for T(n), which is defined by the following recurrence: T(0) = 0 T(1) = 1 T(n) = 5T(n − 1) − 6T(n − 2) + 6 for all n ≥ 2 2 Solution. The characteristic equation is x − 5x + 6 = 0, which has roots x = 2 and x = 3. Thus, the homogenous solution is: 2n 3n T(n) = A · + B · For a particular solution, let’s first guess T(n) = c: c = 5c − 6c + 6 ⇒ c = 3 Our guess was correct; T(n) = 3 is a particular solution. Adding this to the homogenous solution gives the general solution: T(n) = 2n 3n A · + B · + 3