British Olympiad; Combinatorics Recursion

Isaac is planning a nine-day holiday. Every day he will go surfing, or water skiing, or he will rest. On any given day he does just one of these three things. He never does different water-sports on consecutive days. How many schedules are possible for the holiday?

$A$ is surfing, $B$ is water-skiing and $C$ is resting.

Three cases, case 1, week begins with $A$, case 2, week begins with $B$ and case 3, week begins with $C$. Then the total possible weeks by $x(n)$ is:

$$x(n) = a(n) + b(n) + c(n)$$

Where $a(n)$ is the sequence with beginning $A$ etc...

Lets look at case 1 first.

Because it is $A$ _ _ _ _ _ _ _ _,

$$a(n) = c(n-1) + a(n-1)$$

But I cant get rid of $a$, which is the goal. What should I do?

Solution 1:

Denote $s_n$ the number of possibilities spanning $n$ days, the first one being surfing. In the same way, denote $w_n,r_n$ the possibilities when the first day is water ski or rest, respectively. You have the following recurrence relations $$ \begin{cases} s_n = w_{n-1}+r_{n-1} \\ w_n = s_{n-1}+r_{n-1} \\ r_n = s_{n-1}+w_{n-1}+r_{n-1} \end{cases} $$

The easy way out is to write this as a matrix multiplication $Av_{n-1}=v_n$, where $A = \begin{pmatrix} 0 & 1 & 1 \\ 1& 0 & 1\\ 1& 1 & 1\end{pmatrix}, v_n = \begin{pmatrix} s_n \\ w_n \\ r_n \end{pmatrix}$. Start with $s_1=w_1=r_1=1$. We have $v_9 = A^8 \begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}=\begin{pmatrix} 985\\ 985\\ 1393\end{pmatrix}$, giving a total of $3363$ possibilities.

Since this is an olympiad problem, it must have a simpler solution. Denote $a_n = s_n+w_n+r_n$. Then the recurrence relations imply that $$ a_n = 2s_{n-1}+2w_{n-1}+3r_{n-1}=2a_{n-1}+r_{n-1}=2a_{n-1}+a_{n-2}.$$ Now this is a simple linear recurrence with $a_1 = 3,a_2 = 7$. In a few steps you get $a_9 = 3363$.