I'm stuck and I can't find this recurrence relation which is :
Find a recurrence relation that count the number of ternary strings $(0,1,2)$ of length n that do not contains three consecutives 0's.
I can easily find the recurrence relation for ternary strings that contains two consecutives zeros which is :
$$a(n)=2\cdot a(n−1)+2\cdot a(n−2)+3^n−2$$
but I can't find a way to count it for three $0$'s.
If someone could give me advice, it would be appreciated.
Thanks.
Best Answer
In this case I think that a complete solution illustrating a possible approach may be best.
Say that a ternary string is good if it does not have three consecutive zeros and bad otherwise. Let $a_n$ be the number of good strings of length $n$ and $b_n$ the number of bad strings of length $n$; clearly $a_n+b_n=3^n$. (Of course this means that there’s no real need to have both $a_n$ and $b_n$, but it’s often easier to think about what’s going on if you give distinct names to things that are likely to be important. You can always get rid of the extras at the end.)
Suppose that $n\ge 4$, and $\sigma$ is a bad string of length $n$. Let $\sigma^{(k)}$ be the string obtained by deleting the last $k$ digits of $\sigma$. Then either $\sigma^{(1)}$ is already bad, or $\sigma^{(1)}$ is good and $\sigma=\sigma^{(3)}000$. In the latter case $\sigma^{(3)}$ cannot end in $0$, so $\sigma$ is either $\sigma^{(4)}1000$ or $\sigma^{(4)}2000$, where $\sigma^{(4)}$ is any good string of length $n-4$. It follows that
$$b_n=3b_{n-1}+2a_{n-4}$$
and hence that
$$3^n-a_n=3\left(3^{n-1}-a_{n-1}\right)+2a_{n-4}\;,$$
i.e.,
$$a_n=3a_{n-1}-2a_{n-4}\;.$$
Of course the initial conditions are $b_0=b_1=b_2=0$ and $b_3=1$, so $a_0=1$, $a_1=3$, $a_2=9$, and $a_3=26$.