IMC 2005 · Problem 2

For an integer $n \ge 3$ consider the sets

$$S_n = \{(x_1, x_2, \dots, x_n) : \forall i \; x_i \in \{0,1,2\}\}$$ $$A_n = \{(x_1, x_2, \dots, x_n) \in S_n : \forall i \le n-2 \; |\{x_i, x_{i+1}, x_{i+2}\}| \ne 1\}$$

and

$$B_n = \{(x_1, x_2, \dots, x_n) \in S_n : \forall i \le n-1 \; (x_i = x_{i+1} \Rightarrow x_i \ne 0)\}.$$

Prove that $|A_{n+1}| = 3 \cdot |B_n|$.

($|A|$ denotes the number of elements of the set $A$.)