Recurrence relation for number of relations with length $n$ from symbols $0,1$ and $2$ i have a problem with recurrence relations problem..
I need to find a recurrence relation for a number of strings with length $n$ ranging from symbols $0,1$ and $2$ that do not contain two consecutive $0\,$s.
Thanks in advance!
 A: 
(Similar problems occur in the classical 1-dimensional lattice systems of Statistical Mechanics).

Let $\ T(n)\ $ be the set of the allowed strings of length $n$; and let
$$ S_i(n)\ :=\ \{ t\in T(n):\ t(n)=i \} $$
where $\ t:=(t(1)\ldots t(n)),\ $ for all natural $\ n$. Then
$$ S_0(n+1)\,\ =\,\ (S_1(n)\cup S_2(n))\times\{0\} $$
and
$$ S_i(n+1)\,\ =\,\ T_n\times\{i\}\qquad\mbox{for}\,\ i=1\ 2.$$
Let
$$ t(n)\ :=\ |T(n)| $$
and
$$ s_i(n)\ :=\ |S_i(n)|\qquad\mbox{for}\,\ i=0\ 1\ 2, $$
so that
$$ t(n+1)\ =\ s_0(n)+s_1(n)+s_2(n) $$
The concurrence formula for $\ t(n)\ $ is through such relations
for $ s_0(n)\ s_1(n)\ s_2(n),\ $ namely,
$$ [s_0(n+1)\,\ s_1(n+1)\,\ s_2(n+1)]
  \,\ =\,\ [s_0(n)\ s_1(n)\ s_2(n)] \cdot M $$
where the $3\times 3$-matrix $\ M\ $ is described uniquely by:
$$ s_0(n+1)\ =\ s_1(n) + s_2(n) $$
$$ s_1(n+1)=s_2(n+1)\ =\ s_0(n)+s_1(n)+s_2(n) $$
and the initial condition is
$$ s_0(1)=s_1(1)=s_2(1) $$
That's it.

One could combine cases $\ i=1\,\ 2\,\ $ for numeric reasons in the given
  specific case. It's conceptually clearer to keep them separate just like case $\ i=0.$

