MathDB

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

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

Problem Statement