Let [tex]A[/tex] denote the set of such sequence of length [tex]n[/tex], and take [tex]a(n)[/tex] to be the size of [tex]A[/tex], i.e. the number of such sequences of length [tex]n[/tex] consisting of digits 0, 1, or 2.
Split up this set of sequences according to whether a given sequence contains a 2 or does not contain a 2. Let's denote these subsets by [tex]B[/tex] and [tex]\hat B[/tex], respectively, and denote their sizes by [tex]b(n)[/tex] and [tex]\hat b(n)[/tex]. Clearly, [tex]a(n)=b(n)+\hat b(n)[/tex].
Since every sequence in [tex]B[/tex] contains a 2, the only new digit we can append to these sequences must be a 0 or a 2. On the other hand, to every sequence in [tex]\hat B[/tex] we can add any of 0, 1, or 2. So,
[tex]a(n+1)=2b(n)+3\hat b(n)[/tex]
[tex]\implies a(n+1)=2a(n)+\hat b(n)[/tex]
[tex]\hat B[/tex] is the set of all sequences not consisting of 2s, which means [tex]\hat b(n)=2^n[/tex]. There are 3 possible such sequences of length 1, so we can recursively define the total number of such sequences by
[tex]\begin{cases}a(1)=3\\a(n+1)=2a(n)+2^n&\text{for }n\ge1\end{cases}[/tex]
