Let $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$. 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?
 A: As i said in the comment your answer goes wrong when $n\geq 4$ , so let me give you a tricky way to solve it.
As you said all strings can end up with any of these $4$ letters and assume that these strings do not contain $344$ in it , so there are $4a_{n-1}$ such strings.
Now , think the string which ends up with $4$ and do not contain $344$.It has $a_{n−1}$ string that do not have $344$ , but this $a_{n−1}$ string might end with $34$. Because of this, we must subtract the sequence which end up with $4$ and have a substring with length $n−1$ but ends with $34$.
$$a_n=4a_{n-1}-a_{n-3}, \text{where $a_0=1,a_1=4,a_2=16,a_3=63$}$$
A: Here is essentially the same approach but with a convenient notation which helps to derive the recurrence relation.

We count the number $a(n)$ of valid strings from the alphabet $X=\{1,2,3,4\}$, i.e. strings which do not contain $344$   by partitioning  them according to their matching length with the initial parts of   the  bad string $344$.
\begin{align*}
\color{blue}{a_n=a^{[\emptyset]}_n+a^{[4]}_n+a^{[44]}_n}\tag{1}
\end{align*}


*

*The  number $a^{[\emptyset]}_n$ counts the valid strings of  length  $n$   which do not start with the   rightmost character  of  the       bad   word $34\color{blue}{4}$,  i.e.  start  with $1,2$ or $3$.


*The  number $a^{[4]}_n$ counts the valid strings of length  $n$  which do  start with the   rightmost character  of  the       bad   word $34\color{blue}{4}$,  i.e.  $\color{blue}{4}$.


*The  number $a^{[44]}_n$ counts the valid strings of length   $n$   which do  start with the two  rightmost characters  of  the       bad   word $3\color{blue}{44}$,  i.e. start  with   $\color{blue}{44}$.
We  get a    relationship  between valid strings of length $n$  with  those of length  $n+1$  as follows:

*

*If a word counted  by $a^{[\emptyset]}_n$ is appended by $1,2$ or $3$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $4$ from the left it contributes to $a^{[4]}_{n+1}$.


*If a word counted  by $a^{[4]}_n$ is appended by $1,2$ or $3$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $4$ from the left it contributes to $a^{[44]}_{n+1}$.


*If a word counted  by $a^{[44]}_n$ is appended by $1$ or $2$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. Appending from the left by $3$  is not allowed since then we have an invalid string starting with $344$. If it is appended by $4$ from the left it contributes to $a^{[44]}_{n+1}$.

This relationship can be written as
\begin{align*}
\color{blue}{a^{[\emptyset]}_{n+1}}&\color{blue}{=3a^{[\emptyset]}_{n}+3a^{[4]}_{n}+2a^{[44]}_{n}}\tag{2}\\
\color{blue}{a^{[4]}_{n+1}}&\color{blue}{=a^{[\emptyset]}_{n}}\tag{3}\\
\color{blue}{a^{[44]}_{n+1}}&\color{blue}{=a^{[4]}_n+a^{[44]}_n}\tag{4}
\end{align*}

We can now derive a recurrence relation from (1) - (4):

We obtain for $n\geq 2$:
\begin{align*}
\color{blue}{a_{n+1}}&=a^{[\emptyset]}_{n+1}+a^{[4]}_{n+1}+a^{[44]}_{n+1}\tag{$ \to (1)$}\\
&=\left(3a^{[\emptyset]}_{n}+3a^{[4]}_{n}+2a^{[44]}_{n}\right)\\
&\qquad+a^{[\emptyset]}_{n}+\left(a^{[4]}_n+a^{[44]}_n\right)\tag{$\to (2),(3),(4)$}\\
&=4a^{[\emptyset]}_{n}+4a^{[4]}_{n}+3a^{[44]}_{n}\\
&=4a_n-a^{[44]}_{n}\tag{$\to (1)$}\\
&=4a_n-a^{[4]}_{n-1}-a^{[44]}_{n-1}\tag{$\to  (4)$}\\
&=4a_n-a^{[\emptyset]}_{n-2}-\left(a^{[4]}_{n-2}-a^{[44]}_{n-2}\right)\tag{$\to  (3),(4)$}\\
&\,\,\color{blue}{=4a_n-a_{n-2}}\tag{$\to (1)$}
\end{align*}
in accordance with an already given answer. We  finally derive  manually the starting values
\begin{align*}
\color{blue}{a_0=1,a_1=4,a_2=16}
\end{align*}

