1

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.

Community
  • 1
adam19325
  • 13
  • Let $X_n$ be the collection of ternary sequences of length $n$ satisfying given constraint. $X_n$ is a disjoint union of 3 subsets: $${ 02.x : x \in X_{n-2} } ;\sqcup; { 12.x : x \in X_{n-2} } ;\sqcup; X_n = { 2.y : y \in X_{n-1} }$$ where $.$ stands for concatenation of sequences. – achille hui Apr 30 '17 at 18:30

0 Answers0