A congruence in the number of certain ternary strings

Let $a_n$ be the number of ternary strings of length $n$ which do not contain three consecutive symbols that are all different. That is, $$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|.$$

Hence $a_1 = 3$, $a_2 = 9$, $a_3 = 21$, and so on. One can show that these numbers satisfy the reccurence $$a_{n+1} = 2a_n + a_{n-1}$$ and hence $$a_n = \frac{3}{2}\left((1+\sqrt{2})^n + (1-\sqrt{2})^n\right).$$

Now consider $a_p$ where $p\geq 3$ is a prime. It follows by the binomial theorem that $$a_p \equiv 3 \pmod{p} \tag{*}$$ and a little more work gives that $a_p\equiv 3 \pmod{6p}$.

What I want to know is the following: can we prove the congruence $(*)$ using purely combinatorial methods? In particular, is there a natural way to partition the non-constant ternary strings of length $p$ satisfying the condition into equivalence classes of size $p$ (or sizes which are multiples of $p$ for clear combinatorial reasons)?

The analogous problem where we allow the conditions to "wrap around" (i.e., we allow $k$ to be any positive integer in the definition and set $b_{n+i} = b_i$ for all $i$) is easy: if the length of the string is a prime $p$, the natural action of $C_p$ on the set of such strings (namely, rotation) yields 3 orbits of size $1$ (the constant strings); the other orbits, since $p$ is prime, must have size $p$, so these orbits are our nice equivalence classes.

The same sort of trick doesn't work in this case, since (for instance) the string $01112$ is allowed, but its rotation $11120$ is not. Perhaps something more clever will allow us to get a nice combinatorial proof?

Solution 1:

I just wanted to suggest another point of view on the problem:

Consider the map $$(\Bbb Z / 3 \Bbb Z)^n \rightarrow (\Bbb Z / 3 \Bbb Z)^{n-1} \\ (b_1,b_2,...,b_n) \mapsto (b_2-b_1,b_3-b_2,...,b_n-b_{n-1}).$$ The map is a 3:1 correspondence, as the pre-image is uniquely determined by fixing a first number. Also, there is a 3:1 correspondence of ternary strings of length p containing an "abc" substring with pairwise distinct a,b,c to ternary strings of length p-1 containing the substring "11" or "22".

Perhaps it is easier to show, that the number of such strings is congruent to 1 mod p (I suspect the zero-string of being the 1).