CZ-SK-MO 1999 Problem 4

In a certain language there are only two letters, $A$ and $B$ . We know that (i) There are no words of length $1$ , and the only words of length $2$ are $AB$ and $BB$ . (ii) A segment of length $n > 2$ is a word if and only if it can be obtained from a word of length less than $n$ by replacing each letter $B$ by some (not necessarily the same) word. Prove that the number of words of length $n$ is equal to $\frac{2^n +2\cdot (-1)^n}{3}$