Find a recurrence relation for the number of n-digit ternary sequences in which no 1 appears anywehere to the right of a 2

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