A fair dice is to be rolled $n$ times. Find the probability of not getting three consecutive sixes. (Here $12664665$ or $12346522$ is a valid result while $12666555$ or $66664256$ isn't.)
The problem is inspired from this problem. I think the problem can be solved by case working. But I am not interested in that kind of solution. Rather I am interested in a solution that uses recurrence relations like this solution of the original problem. I've thought of a way to solve the problem which is not complete:
The main concern of solving the problem is to find the number of ways to arrange the numbers $1$ to $6$ such that no three sixes are consecutive. Now, we change all the digits which are not $6$ into $0$. For example, if we get $1266564$, we will change this as $0066060$. Let $S_n$ be the number of such valid results that contain $0$ and $6$ only.
Now, if the first rolled dice gets a $0$ then there are $n-1$ rolls still left. But any of the results will be similar to one of the configurations of $S_{n-1}$.
If the first rolled dice gets a $6$ and the second rolled dice gets a $0$, then using the same logic above we get that there $S_{n-2}$ ways of getting a valid result.
If the first rolled dice gets a $6$ and the second rolled dice gets a $6$, then the third rolled dice will get a $0$ for the result to be valid. So, there will be $S_{n-3}$ ways of getting the result.
Hence, we get a recurrence relation that is: $S_n=S_{n-1}+S_{n-2}+S_{n-3}$. Now, my idea was to change all $0$s into $1,2,3,4$ or $5$. But I think that's not possible or that will be too complicated as there will be too many cases.
So, I need a solution to the problem that uses recurrence relations.
Best Answer
What a beautiful question to make use of the power of Goulden-Jackson method ! (I want to especially thank to @Markus Scheuer for this beautiful method)
I am putting here a link for you : https://arxiv.org/abs/math/9806036 ,you can learn more about it.
According to the article , our bad words are $666$.
Then , our alphabet is $V= \{1,2,3,4,5,6\}$
$$A(x)= \frac{1}{1-dx-weight(C)}$$ with $d=|V|=6$ and $weight(C) = weight(C[666])$
Hence , $$weight(C) = \frac{-x^3}{1+x+x^2} $$
Then , $$A(x) = \frac{1}{1-6x -\frac{-x^3}{1+x+x^2}} = \frac{1+x+x^2}{1-5x-5x^2-5x^3}$$
Now , we will turn this fraction into recurrence relation. See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley. (https://www.maa.org/press/maa-reviews/enumerative-combinatorics-vol-i)
$$\frac{1+x+x^2}{1-5x-5x^2-5x^3} \rightarrow a_{n+3}-5a_{n+2}-5a_{n+1}-5a_{n}=0$$
Then , $$a_n=5a_{n-1} + 5a_{n-2} +5a_{n-3}$$
Moreover , we can find the reseult of any string by generating functions such that https://www.wolframalpha.com/input/?i=expanded+form+of+%281%2Bx+%2B+x%5E2%29+%2F+%281-5x-5x%5E2+-5x%5E3%29
$$\frac{1+x+x^2}{1-5x-5x^2-5x^3}=1+6x+36x^2 + \color{blue}{215x^3} + 1285x^4 + ...$$
This means that there are $215$ different string of lenght $3$ do not contain three consecutive $6$
Moreover , the sample space is $6^n$
You can say that $$\frac{a_n=5a_{n-1} + 5a_{n-2} +5a_{n-3}}{6^n}$$ where $a_0 =1 , a_1 =6 , a_2=36 , a_3=215$