Difficult recursion problem

Question

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.

Answer 1

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?

Answer 2

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).$$

Answer 3

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.