Let $A = {a,b,c}$ be the alphabet to use for the words. Number words of length n which contain the sequence $(aa)$ at least once.
$n = 0$ and $n = 1$ yield no words, because they do not contain $(aa)$. So we can start with $n = 2$
There are $n-1$ possibilities for the position of the $aa$. We have $n-2$ remaining letters, for which each has three possibilities for a letter.
I come to the conclusion that the formula must be $(n-1) \cdot 3^{n-2}$
I'm not sure about this and I wonder if there is a cleaner approach, maybe a recurvive approach?