I tried to solve this question by subtracting the number of strings that contain consecutive symbols that are same from the total number of symbols possible of length n.
Let bn denote the number of strings of length n, with consecutive symbols that are same. Then bn can be obtained by 3*bn-1 , since there are 3 choices for appending the string of length n-1 to form a string of length n. So if an denotes the number of strings of length n that do not contain consecutive symbols that are same then, an = 3n – bn-1 . But I am stuck, how do I go from here ? How to solve such problems without generating the sequence and guessing ? I am having a hard time doing so.
Best Answer
HINT
Well, if $a_n$ denotes the number of ternary strings without consecutive symbols, and you are given such a string of length $n-1$, you can form an $n$-string by attaching $0,1,2$ at the end except you must make sure not to duplicate the last symbol. In other words you have 2 choices for the last character.
Can you finish this?