maybe there is a smarter way, but this is a more straightforward way. Let $x_n,y_n,z_n$ denote respectively the number of good tuples of length $n$, starting with $3,5$ and neither 3 nor 5 respectively. then we have the following relation(these may or may not contain 5): $\left(\begin{array}{ccc}{ccc} 1&0&1\1&1&1\1&1&1\end{array}\right)\left(\begin{array}{ccc} x_ny_nz_n\end{array}\right)=\left(\begin{array}{(ccc)}x_{n+1}y_{n+1}z_{n+1}\end{array}\right)$. Also we have $\left(\begin{array}{c}{ccc}x_{1}y_{1}z_{1}\end{array}\right)=\left(\begin{array}{(ccc)}1\1\3\end{array}\right)$. one can check by induction that if the above matrix is $A$, then $A^{n+1}=\left(\begin{array}{ccc}{ccc}F_{2n}&F_{2n-1}&F_{2n}\F_{2n+1}&F_{2n}&F_{2n+1}\F_{2n+1}&F_{2n}&F_{2n+1}\end{array}\right)$ where $F_n$ is the $n$th Fibonacci number($F_0=F_1=1,F_2=2$ etc) what we need is of course $\left(\begin{array}{ccc}{(c)}1&1&1\end{array}\right)A^{n-1}\left(\begin{array}{(ccc)}1\1\3\end{array}\right)=F_{2n}+3F_{2n-1}$. to include $5$'s we just throw away all the sequences without $5$'s from this, which is just $4^n$. (hopefully everything is alright)

Isn't it like this? Let $a_n$ be n-digit without $3$ in front of $5$, and $b_n$ be n-digit without $3$ in front of $5$ and ending with $3$ We have $a_{n+1} = 5(a_n-b_n)+4b_n$ and $b_{n+1} = a_n$ And we get $a_{n+1}-5a_n+a_{n-1} = 0$ So $a_n = A(\frac{5+\sqrt{21}}{2})^n+B(\frac{5-\sqrt{21}}{2})^n$ where $A,B$ are constants we have to solve. And then we take out the $4^n$ without a $5$.