Over an alphabet of $n$ symbols, how many are the strings of length $k$ without consecutive symbols repeated? From combinatorics, it's known that over an alphabet of $n$ symbols there are $n^k$ different strings of length $k$, of which $\frac{n!}{(n-k)!}$ (assuming $k \le n$) are those without any repeated symbols.
But how to find how many strings of length $k$ without consecutive symbols repeated?
For example if the alphabet is {A, B, C }, acceptable strings are ABAB and BACA, whereas ABBA or AAAA are not.

Hint: You have $n$ choices for the first symbol. After that, you always have $n-1$ choices.
