Recurrence relation for number of relations with length $n$ from symbols $0,1$ and $2$

Question

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!

Answer 1

(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.$