How many strings of $6$ digits are there which use only the digits $0, 1$, or $2$ and in which $2$, whenever it appears, always does so after $1$? My attempt at the solution:  
Without $2$s: $\Rightarrow 6$ places, each of which can be filled in two ways.
Hence in total $2^6$ ways.  
Considering (01) as a set,
0 1 _ _ _ _ $\Rightarrow$ Remaining places can be filled in $3 \cdot 2^3$ ways (one place with any of the $3$ digits and remaining with only $2$ digits) . 
Shifting (01), we have 5 possibilities. 
Hence in total $5 \cdot 3 \cdot 2^3$ ways
Next possibility, $\Rightarrow$ 0 1 0 1 _ _  
$\Rightarrow$ Remaining places can be filled in $3 \cdot 2$ ways (one place with any of the three digits and the remaining with only two digits). Shifting (0101), we have $6$ possibilities. 
Hence in total $6 \cdot 3 \cdot 2$ ways. 
Grand Total $= 32 + 120 + 36 = 188$.
But the answer given in the book is $256$. Help! Thank you in advance.
 A: Let $a_n$ be the number of such strings of length $n$ which end in a $0$ or $2$. Also let $b_n$ be the number of such strings of length $n$ which end with $1$. Now obviously we can form the recursion relations:
$$a_{n+1} = a_n + 2b_n$$
$$b_{n+1} = a_n + b_n$$
Here the initial condition is $a_1 = 1, b_1 = 1$. So repeatedly using the relation above it shouldn't be hard to get that $a_2 = 3, b_2 = 2$; $a_3 = 7, b_3 = 5$; $a_4 = 17, b_4 = 12$; $a_5 = 41, b_5 = 29$; $a_6 = 99, b_6 = 70$, so the total number is $169$
Another way is using your method. If there is no $2$ then we have $2^6 = 64$ options. If there's a single two then you can consider $(12)$ as single digit and then place choose it's place in a $5$ digit word and there are $2^4$ options for the remaining $4$ digits. SO the wanted number is $5 \cdot 2^4 = 80$ If there are two twos, then again consider $(12)$ as a single digit. Choose the placement of them in a $4$-digit sequence and the rest two digits can be chosen in $2^2$ ways. So the number of such combinations is $\binom{4}{2} \cdot 2^2 = 24$. If there are three two then we have a single options. Finally the wanted number is:
$$64+80+24+1 = 169$$

[UPDATE]
We can count the number of solutions by the position of the first $2$. If there are no $2$'s then we have $2^6=64$ such sequences. Now obviously we can't have it appear first. If it appears second then the first digit is $1$ and we have $3^4=81$ options for the remaning $4$ digits. In general if the first $2$ appears in the $n$-th position we have:
$$(2^{n-1} - 1)3^{6-n} \text{ sequences}$$ 
This is true, as we need to exclude the sequence of all zeroes before the $2$. Summing all such possibilities we get:
$$64+81+81+63+45+31 = 365 $$
Note that this result is expected as there are exactly $3^6 = 729$ such sequences and the $1$ will appear before $2$ in exactly half of them, because of the symmetry. And indeed $\frac{729}{2} = 364.5$. Note that we are off by one as the sequence of all zeroes doesn't count in any set of sequences.
A: First place can only be filled by 1 - So forget it.
For Last 4 places you can fill with 12, 0, 1 with repeating numbers so 43 = 64
Second place can be occupied by 0,1,2 = 64 * 3 = 192
So total ways = 64 + 192 = 256.
