Difficult recursion problem A student can do the things bellow:


*

*a. Do his homework in 2 days

*b. Write a poem in 2 days

*c. Go on a trip for 2 days

*d. Study for exams for 1 day

*e. Play pc games for 1 day


A schedule of n days can be completed by any combination of the activities above. For example 3 possible schedules for 7 days are:


*

*homework, poem, homework, play

*poem, study, play, homework, study

*trip, trip, trip, study


Find a recursive function T(n) that represents the number of all possible schedules for n days. 
 A: HINT: He has $T(n-1)$ ways to schedule $n-1$ days; for each of those ways, he can spend the $n$-th day studying for exams or playing pc games, so those $T(n-1)$ ways to schedule $n-1$ days can be extended to $2T(n-1)$ ways to spend $n$ days. That accounts for all of the $n$-day schedules in which the last activity takes only one day. 


*

*Where do the other possible schedules for $n$ days come from? How many of them are there? 

A: Suppose $n=1$. Then you can't do any of the 2-day activities, and have two choices for 1-day activities: $T(1) = 2.$
Now suppose $n=2$. You can either do one of three 2-day activities, or one of two 1-day activities. In the latter case, you will have one day left, and $T(1)$ ways to spend it. So $T(2) = 3+2T(1).$
Finally, for $n>2$, you have 3 ways to spend two days (followed by $T(n-2)$ ways to spend the rest of the days) and 2 ways to spend one day (followed by $T(n-1)$ ways to spend the others.) So
$$T(n) = 3T(n-2) + 2T(n-1).$$
A: Hint: an $n$ day schedule is either an $n-1$ day schedule followed by a $1$ day activity, or an $n-2$ day schedule followed by a $2$ day activity.
