Пусть $a_n$ — число слов длины $n$ над алфавитом из 3 букв без одинаковых соседних букв. Тогда
- $a_1=3$ (любой из трёх символов),
- для $n\ge 2$ последний символ не может совпадать с предыдущим, значит для каждого слова длины $n-1$ есть ровно 2 варианта дополнить его: $$a_n=2a_{n-1}.$$
Решение рекурренты с начальными условиями даёт замкнутую форму: $$a_n=3\cdot 2^{n-1}(\text{для}n\ge 1),$$ (при желании считать пустое слово: $a_0=1$).
Асимптотика при $n\to \infty$: рост экспоненциальный с основанием 2, например $$a_n\sim \frac{3}{2}{2}^n,\underset{n\to \infty }{\lim }\frac{a_{n+1}}{a_n}=2,\ln a_n\sim n\ln 2.$$