# Recursion relation for the number of ternary string that does not contain two consecutive characters.

Ternary strings are those that contain only 3 characters at most. For ex: abcbca is ternary string over set {a,b,c}, etc. Can anyone tell what will be the recursion relation for the string that does not contain consecutive characters , for ex: abccba,bcaacb etc.

Let $a_n$ be the number of good strings of length $n$. Every good string of length $n+1$ is obtained by adding one of two characters to a string of length $n$, one of the two that don’t match its last character, so $a_{n+1}=2a_n$ for $n\ge 1$. However, $a_1=3$, so $a_n=3\cdot2^{n-1}$ for $n\ge 1$.
@satyam: Do you mean strings with just one instance of repetition, or strings that allow only one of the three characters to repeat but allow it to repeat more than once, like abccbccacccbaba? –  Brian M. Scott Sep 29 '12 at 6:43