Q6 Matemática  (Czech-Polish-Slovak Match 1997)

Em um determinado idioma existem apenas duas letras, $A$ e $B$. As palavras desta língua obedecem às seguintes regras: (i) A única palavra de comprimento $1$ é $A$; (ii) Uma sequência de letras $X_1{X}_2...X_{n+1}$, onde $X_i\in \{A,B\}$ para cada $i$, forma uma palavra de comprimento $n+1$ se e somente se contiver pelo menos uma letra $A$ e não for da forma $WA$ para uma palavra $W$ de comprimento $n$. Mostre que o número de palavras que consistem em $1998A$'s e $1998B$'s e não começam com $AA$ é igual a $\left(\genfrac{}{}{0ex}{}{3995}{1997}\right)-1$