BMO1 2013, solving a recurrence relation

Question

The question is

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?

My attempt: $$ \text{Define a}_{\text{n}}\,\,\text{to be the number of n}-\text{day holiday that the last day is rest} \\ \text{b}_{\text{n}}\,\,\text{similarly, last day is skiing}. \\ \text{Then a}_{\text{n}+1}=\text{a}_{\text{n}}+\text{2b}_{\text{n}}, \text{b}_{\text{n}+1}=\text{b}_{\text{n}}+\text{a}_{\text{n}} \\ $$ Then I do not know how to proceed to solve this sequence

Answer 1

From $a_{n+1}=a_n+2b_n$ we get $a_n=a_{n-1}+2b_{n-1}$. Subtracting the second from the first gives

$$a_{n+1}=2a_n-a_{n-1}+2(b_n-b_{n-1})$$

But we know that $b_n-b_{n-1}=a_{n-1}$. So we get

$$a_{n+1}=2a_n+a_{n-1}$$

Solving this recurrence in the usual way gives $$a_n=\frac12((1+\sqrt 2)^n+(1-\sqrt 2)^n)$$

Now note that the number of possible schedules for a $9$-day holiday is the same as the number of schedules for a $10$-day holiday that end with a rest day. So the answer we want is $a_{10}=\frac12((1+\sqrt 2)^{10}+(1-\sqrt 2)^{10})$, which Wolfram Alpha evaluates as $3363$.

Unfortunately this answer is not very helpful in the context of an exam, when computing $(1+\sqrt 2)^{10}+(1-\sqrt 2)^{10}$ is not really practical. I think in an exam you would just have to compute $a_{10}$ iteratively by hand.

Answer 2

You also need to define $c_n$ as the number of $n$-day schedules with the last day surfing. Then we are looking for the sum of entries of $$\begin{bmatrix}1&1&1\\1&0&1\\1&1&0\end{bmatrix}^8\begin{bmatrix}1\\1\\1\end{bmatrix}$$ The left matrix exponentiation can easily be calculated by repeated squaring. The final column vector should be $(1393,985,985)^T$, whose entries sum to $3363$, the final answer.