Dejemos que $a_n$ sea el número de cadenas ternarias de longitud $n$ que no contengan tres símbolos consecutivos que sean diferentes. Es decir, $$a_n = \Bigl|\bigl\{\,(b_k)_{1\leq k\leq n}\in \{0,1,2\}^n\mid (\forall k \in \{1,\ldots, n-2\}) (\{b_k, b_{k+1}, b_{k+2}\} \neq \{0, 1, 2\})\,\bigr\}\Bigr|.$$
Por lo tanto, $a_1 = 3$ , $a_2 = 9$ , $a_3 = 21$ y así sucesivamente. Se puede demostrar que estos números satisfacen la recencia $$a_{n+1} = 2a_n + a_{n-1}$$ y por lo tanto $$a_n = \frac{3}{2}\left((1+\sqrt{2})^n + (1-\sqrt{2})^n\right).$$
Ahora considere $a_p$ donde $p\geq 3$ es un primo. Por el teorema del binomio se deduce que $$a_p \equiv 3 \pmod{p} \tag{*}$$ y un poco más de trabajo da que $a_p\equiv 3 \pmod{6p}$ .
Lo que quiero saber es lo siguiente: ¿podemos demostrar la congruencia $(*)$ utilizando puramente combinatoria ¿se trata de una forma natural de dividir el En particular, ¿existe una forma natural de dividir las cadenas ternarias no constantes de longitud $p$ que satisfacen la condición en clases de equivalencia de tamaño $p$ (o tamaños que son múltiplos de $p$ por claras razones combinatorias)?
El problema análogo en el que permitimos que las condiciones "envuelvan" (es decir, permitimos $k$ para ser cualquier número entero positivo en la definición y establecer $b_{n+i} = b_i$ para todos $i$ ) es fácil: si la longitud de la cadena es un primo $p$ La acción natural de $C_p$ en el conjunto de tales cadenas (es decir, la rotación) produce 3 órbitas de tamaño $1$ (las cuerdas constantes); las otras órbitas, ya que $p$ es primo, debe tener tamaño $p$ así que estas órbitas son nuestras buenas clases de equivalencia.
El mismo tipo de truco no funciona en este caso, ya que (por ejemplo) la cadena $01112$ está permitido, pero su rotación $11120$ no lo es. ¿Quizás algo más inteligente nos permita obtener una bonita prueba combinatoria?
