Let $X = \{1,2,3,4\}$ and $a_n$ be the number of $X$-strings of length $n$ that do not contain $344$ as a sub-string.
Find a recurrence relation for $a_n$.
We can construct a string of length $n$ in the following ways:
$1.$ String of length $n-1$ and $1/2/3$ in the last place.
$2.$ String of length $n-2$ and $14/24/34$ in the last two places.
$3.$ String of length $n-3$ and $144/244/444$ in the last three places.
Hence the required recurrence relation for $a_n$ is $$a_n = 3a_{n-1}+3a_{n-2}+3a_{n-3}$$ with initial conditions $a_0 = 1,a_1 = 4$ and $a_2 = 16$.
Is the argument valid?