Let
denote the set of such sequence of length
, and take
to be the size of
, i.e. the number of such sequences of length
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
and
, respectively, and denote their sizes by
and
. Clearly,
.
Since every sequence in
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
we can add any of 0, 1, or 2. So,
is the set of all sequences not consisting of 2s, which means
. There are 3 possible such sequences of length 1, so we can recursively define the total number of such sequences by