A fair dice is to be rolled $n$ times. Find the probability of not getting three consecutive sixes. 
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.
 A: 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])$

Lets calculate $weight(C[000])$ according to the paper such that
$weight(C[666])= -x^3 - (x +x^2)weight(C[666])$
So , $weight(C[666]) = \frac{-x^3}{(1+x +x^2)} $

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$
A: For your dice rolls, let

*

*$A_n$ be the probability of $n$ acceptable roll sequences which do not end in $6$

*$B_n$ be the probability of $n$ acceptable roll sequences which end in one $6$

*$C_n$ be probability of $n$ acceptable roll sequences which end in two $6$s

You have

*

*$A_{n+1}=\frac56 (A_n+B_n+C_n)$ since any of five out of six results can be appended

*$B_{n+1}=\frac16 A_n$ since you need one $6$

*$C_{n+1}=\frac16 B_n$ since you need a second $6$ and so $C_{n+1}=\frac1{36}A_{n-1}$

*starting with $A_0=1,B_0=0,C_0=0$
The first three of those imply $A_{n+1}=\frac56 A_n+\frac5{36}A_{n-1}+\frac5{216}A_{n-2}$ at least for $n\ge 2$
You want $p_n= A_n+B_n+C_n$ as the sum of probabilities
so $p_{n}=\frac65 A_{n+1} = A_n+\frac16A_{n-1}+\frac1{36}A_{n-2}$ and $A_{n+1}=\frac56 p_{n}$,
i.e. $$p_n = \frac56 p_{n-1}+ \frac5{36}p_{n-2}+ \frac5{216}p_{n-3}
$$ at least for $n\ge 3$, and clearly $p_0=p_1=p_2=1$ to start you off since you cannot get $666$ with three rolls.  If you had wanted $S_n$ as the number of  rather than the probability, you would have $S_n = 5( S_{n-1}+ S_{n-2}+ S_{n-3})$ and $p_n=\frac{S_n}{6^n}$
A: To flesh out the hint in the comments, we want to count $S_n$, the number of strings with no $666$.
Since each "good" string of length $n≥3$ must end in one of $X, X6, X66$ where $X\in \{1,2,3,4,5\}$, we see that $$S_n=5(S_{n-1}+S_{n-2}+S_{n-3})$$  at least for $n≥4$. if we set $S_0=1$ then this holds for $n≥3$, but since it is easy to deduce that $S_1=6, S_2=36, S_3=215$ we really don't need to. However you do it, there is no difficulty computing $S_5$.
In principle we could solve this in closed form, but the characteristic polynomial $x^3=5x^2+5x+5$ does not have terrible pleasant roots, so this is not practical.  As it happens, only one root has norm $>1$ so one might at least hope for useful asymptotic formulas.  For instance, it is easy to see that $$\frac {S_n}{S_{n-1}}\to 5.9766$$
where $5.9766$ is, approximately, the large real root of the cubic.
