Let
![A](https://tex.z-dn.net/?f=A)
denote the set of such sequence of length
![n](https://tex.z-dn.net/?f=n)
, and take
![a(n)](https://tex.z-dn.net/?f=a%28n%29)
to be the size of
![A](https://tex.z-dn.net/?f=A)
, i.e. the number of such sequences of length
![n](https://tex.z-dn.net/?f=n)
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
![B](https://tex.z-dn.net/?f=B)
and
![\hat B](https://tex.z-dn.net/?f=%5Chat%20B)
, respectively, and denote their sizes by
![b(n)](https://tex.z-dn.net/?f=b%28n%29)
and
![\hat b(n)](https://tex.z-dn.net/?f=%5Chat%20b%28n%29)
. Clearly,
![a(n)=b(n)+\hat b(n)](https://tex.z-dn.net/?f=a%28n%29%3Db%28n%29%2B%5Chat%20b%28n%29)
.
Since every sequence in
![B](https://tex.z-dn.net/?f=B)
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
![\hat B](https://tex.z-dn.net/?f=%5Chat%20B)
we can add any of 0, 1, or 2. So,
![a(n+1)=2b(n)+3\hat b(n)](https://tex.z-dn.net/?f=a%28n%2B1%29%3D2b%28n%29%2B3%5Chat%20b%28n%29)
![\implies a(n+1)=2a(n)+\hat b(n)](https://tex.z-dn.net/?f=%5Cimplies%20a%28n%2B1%29%3D2a%28n%29%2B%5Chat%20b%28n%29)
![\hat B](https://tex.z-dn.net/?f=%5Chat%20B)
is the set of all sequences not consisting of 2s, which means
![\hat b(n)=2^n](https://tex.z-dn.net/?f=%5Chat%20b%28n%29%3D2%5En)
. There are 3 possible such sequences of length 1, so we can recursively define the total number of such sequences by