I have the following homework assignment:
Let $s_n$ be the number of ternary sequences of length n, such that the sub-sequences 00, 01, 10, and 11 never occur. Prove that $s_n = s_{n-1} + 2s_{n-2}$ for $ n \ge 3$ with $s_1 = 3$ and $s_2 = 5$
Then find a direct formula for $s_n$.
So I found the direct formula using the second-order homogeneous linear difference equation and got $s_n = - {\frac{1}{3}}(-1)^n + {\frac{4}{3}}(2)^n $ as my solution for the second part. I'm not quite sure how to go about proving the recurrence relation for this.