probability of not getting same number twice in a row after n die rolls

Question

Having rolled a die $n$ times, I want to determine the probability of not getting any number twice in a row. If I wanted the probability of not getting any number three times in a row, I could use the following recursion: $$p_n=\frac{5}{6}p_{n-1}+\frac{5}{36}p_{n-2},$$ as the streak is broken $5/6$ of the time, meaning we just need to multiply by the corresponding probability for one fewer trials, and the streak is continued $1/6$ of the time, so we need to break it with probability $5/6$ and multiply by the corresponding probability for two fewer trials. However, I am having difficulties applying this method to the seemingly easier length-two streak case. Any ideas would be greatly appreciated.

Answer 1

The probability of not getting two in a row in $n$ trials is $5/6$ times the probability of not getting two in a row in $n-1$ trials.

Remark: A related problem, the probability of not getting two of a specified number, like $4$, twice in a row is harder. We get a second order recurrence rather than a first-order recurrence.

Added: We find a recurrence for the "no two $4$'s in a row problem. There are $6^n$ equally likely sequences of $n$ tosses. Let $a_n$ be the number of sequences with no two $4$'s in a row. A good sequence of length $n$ either (i) does not end in a $4$ or (ii) ends in a $4$.

The Type (i) sequences are obtained by appending a non-$4$ to any good sequence of length $n-1$, So there are $5a_{n-1}$ of them.

The Type (ii) sequences are obtained by appending a $4$ to a good sequence of length $n-1$ that does not end in a $4$. These can be obtained by appending a non-$4$ to a good sequence of length $n-2$, so there are $5a_{n-2}$ of them.

We have obtained the recurrence $a_n=5a_{n-1}+5a_{n-2}$.