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 try- Let surfing be denoted as the number 1, water skiing as 2 and resting as 3. So we need to find the number of 9 digit numbers having only 1, 2 and 3 such that 1 and 2 never come together. Here is where I am stuck. Any help would be appreciated. Source - British Mathematical Olympiad

There is probably a more elegant way to see this, but:

Let $T_n$ be the desired answer. That is, the number of good strings of length $n$.

Let $A_n$ be the number which end in surf.

Let $B_n$ be the number which end in ski.

Let $C_n$ be the number which end in rest.

Then, of course, $$T_n=A_n+B_n+C_n$$

Recursively, it is clear that $$A_n=A_{n-1}+C_{n-1}\quad B_n=B_{n-1}+C_{n-1}\quad C_n=T_{n-1}$$ Adding we get $$T_n=A_{n-1}+B_{n-1}+C_{n-1}+C_{n-1}+T_{n-1}=2T_{n-1}+T_{n-2}$$

A quick calculation then gives $$\boxed {T_9=3363}$$