"A code-word from the alphabet $\{0,1,2\}$ is considered legitimate if and only if no two $0$'s appear consecutively. Find a recurrence for the number $b_n$ of legitimate code-words".
My dumb solution for this is just observing that, given the code-words of length one (there are three of them), we can append either $\{0,1,2\}$ to find $b_2$, from the resulting $9$ two letters code-word only $8$ are valid (no consecutive 00) or $ 3 \times 3 - 1 = 8$.
To find $b_3$ we work in a similar way, appending 1,2 or 3 give us 24 code-words, but only 22 of them are valid: $3\times8 - 2 = 22$. The next iteration is: $3\times22-6=3\times22-2\times3=60$, then $3\times60-16=3\times60-2\times8=164$.
Putting all this together (on paper) and you'll notice that in general it seems that $b_n=3\times b_{n-1}-2\times b_{n-3}$. Which looks the correct solution.
This problem can be solved also by using some set theory methodologies, does anybody have any idea on how this can be done? This should be something similar to the proof that given a set $A_n$ where $a_i=\{0,1\}$ then the number of subsets of $A$ which do not have consecutive 0 is: $b_n=F_{n+1}$ for $n\ge1$ where $F_n$ is the n-th Fibonacci number.
Suppose that $A=\{0,1,2,\cdots,r\}$ be a set of length $r+1$. We want to count all sub-sequences of length $n$ of the set $A$ such that there is no two consecutive zero in these sub-sequences. Let the number of these sub-sequences denoted with $Z_r(n)$.
If the first position of $n$-array be the numbers $\{1,2,\cdots ,r\}$ then the other $n-1$ position can be filled by $Z_r(n-1)$ cases. In continue, If the first position of $n$-array be zero then the second position should be the numbers $\{1,2,\cdots ,r\}$ and the other $n-2$ position can be filled by $Z_r(n-2)$ cases.
The desired sub-sequences of length $n$ begin with zero or $\{1,2,\cdots ,r\}$ and two mentioned cases are separated and cover all these sub-sequences. So the term of $Z_r(n)$ can be defined as follows $$ Z_r(n)=r\, Z_r(n-1)+r\, Z_r(n-2) $$ The first two initial values of $Z_r(n)$ are defined in the following form:
$ Z_r(0)=1$ because there is just zero number.
$ Z_r(1)=r+1$ because there are $r+1$ numbers of length $1$
In your question $r=2$, and the the sequence is as follows : $$ \begin{array}{ccccc} Z_2(n)=2\, Z_2(n-1)+2\, Z_2(n-2) &,& Z_2(0)=1& ,&Z_2(1)=3 \end{array} $$