= Solution
There is no forbidden pair in a <sequence> of length zero or one, so $p_0=p_1=1$. For $n\geqslant2$, divide acceptable <sequences> into two disjoint cases. If the first digit differs from $3$, its <probability> is $2/3$, and the remaining $n-1$ independent digits must avoid the pair. If the first digit is $3$, the next must differ from $3$, which has combined <probability> $2/9$, and the remaining $n-2$ digits must avoid the pair. The boundary between this prefix and the remaining digits cannot create a forbidden pair, because the prefix ends in a digit other than $3$. Consequently
$$
\boxed{p_n=\frac23p_{n-1}+\frac29p_{n-2},\qquad p_0=p_1=1.}
$$
The <characteristic polynomial of a linear recurrence> is $r^2-\frac23r-\frac29$, with distinct roots
$$
r_+=\frac{1+\sqrt3}{3},\qquad r_-=\frac{1-\sqrt3}{3}.
$$
Writing $p_n=Ar_+^n+Br_-^n$, the <initial conditions> give $A+B=1$ and $Ar_++Br_-=1$. Therefore
$$
\boxed{p_n=\frac{2+\sqrt3}{2\sqrt3}\left(\frac{1+\sqrt3}{3}\right)^n+\frac{\sqrt3-2}{2\sqrt3}\left(\frac{1-\sqrt3}{3}\right)^n,\qquad n\geqslant0.}
$$
For example, $p_2=8/9$, since only one of the nine equally likely pairs is forbidden. This is the case with success <probability> $1/3$ of the <avoidance recurrence for two consecutive successes>.
Back to article page
