CAPS 1997 Problem 6

In a certain language there are only two letters, $A$ and $B$ . The words of this language obey the following rules: (i) The only word of length $1$ is $A$ ; (ii) A sequence of letters $X_1X_2...X_{n+1}$ , where $X_i\in \{A,B\}$ for each $i$ , forms a word of length $n+1$ if and only if it contains at least one letter $A$ and is not of the form $WA$ for a word $W$ of length $n$ . Show that the number of words consisting of $1998 A$ 's and $1998 B$ 's and not beginning with $AA$ equals $\binom{3995}{1997}-1$