Number of 'hokage' words
Let n be any natural number. Now define a 'hokage' word as a word consisting only of A,B, and C letters, such that no letter A is followed immediately by B and no letter B is followed immediately by A. There is no such restriction on C.
How many n lettered 'hokage' words are possible?
My attempt: I noted that the word is of form of an alternating form, An example is 'AAAAACCCCBBCCAACACCCBBC'.
That is, when A starts then it must end with C. When B starts, it also similarly ends in C. C can end in any of A or B.
The Case wise approach was pretty difficult (or so i felt).
So I tried using recursion but ended up getting nowhere.
Hint: In order to find a recursion, note the following. There are 3 ways that we can build a valid word of length $n+1$:
- A, followed by a valid word starting with either A or C of length $n$,
- B, followed by a valid word starting with either B or C of length $n$,
- C, followed by any valid word of length $n$.
By symmetry, the number of valid words of length $n$ that begin with A is equal to the number of valid words of length $n$ that begin with B.
Some further explanation. Let $a_n$ denote the number of valid words of length $n$ that begin with $A$, and let $c_n$ denote the number of valid words of length $n$ that begin with $C$. From the rules above, we have $$ a_{n+1} = a_n + c_n\\ c_{n+1} = 2a_n + c_n $$ and of course, $a_1 = c_1 = 1$. In terms of matrices, we can write $$ \pmatrix{a_{n+1}\\ c_{n+1}} = \pmatrix{1 & 1\\2 & 1} \pmatrix{a_n\\ c_n}. $$