Encontrar una relación de recurrencia sobre un diccionario dado

Deja $a_n$sea ​​el número de cadenas admisibles con $n$dígitos

¿Cómo podemos construir una cadena admisible con $n+1$dígitos?

Hay dos posibilidades. Podemos tomar una cadena admisible con $n$dígitos y agregue cualquiera de los dígitos diferentes del primero y el último al final. Esto contribuye $2a_n$posibilidades, pero como me señaló Don Mil, ignora cadenas como $1412$que no surgen de esta manera. Podemos obtenerlos comenzando con cualquier $n-2$-cadena admisible de dígitos, agregando el primer dígito al final y luego agregando cualquiera de los otros tres dígitos al final de eso.

$$a_{n+1}=2a_n+3a_{n-1}$$

A la vista de los datos iniciales $a_1=0,\ a_2=12$, las técnicas estándar dan la solución

$$a_n=3^n+3(-1)^n$$

Escribí un pequeño script en Python para contar las cadenas admisibles por fuerza bruta hasta $n=10$, y confirmó esta fórmula.

Primero, cuente el número de palabras donde los dígitos adyacentes son diferentes, ignorando la condición de la primera y la última letra. Este límite es obviamente $4\cdot 3^{n-1}$.

De esta cuenta, debemos restar las palabras que violan la condición de primera/última letra. Palabras de longitud $n$sin dos letras adyacentes de modo que la primera letra sea igual a la última, están en biyección con palabras cíclicas de longitud $n-1$sin dos letras adyacentes (solo borre la última letra). Juntando todo esto, obtenemos

$$a_n=4\cdot 3^{n-1}-a_{n-1}\qquad (n\ge 2)$$ Esta es la recursividad que deseabas. Para resolver esta recursión, aplicamos la misma recursión a $a_{n-1}$, y así, expandiéndolo hasta el final. el resultado es $$\begin{align} a_n &= 4\cdot3^{n-1}-a_{n-1} \\&= 4\cdot3^{n-1}-(4\cdot 3^{n-2}-a_{n-2}) \\&= 4\cdot3^{n-1}-\big(4\cdot 3^{n-2}-(4\cdot 3^{n-3}-a_{n-3})\big) \\&\;\;\vdots \\&=4\big(3^{n-1}-3^{n-2}+3^{n-3}-\dots+(-1)^{n-2}\cdot 3^1+\require{cancel}\cancelto{0}{\color{grey}{(-1)^{n-1}a_1}} \big) \\&=4\cdot \frac{3^{n-1}-(-1)^{n-1}}{1-\frac{-1}3} \\&=3^n+3(-1)^{n}. \end{align}$$