The number of permutations with a distance condition

Question

How can I think about this question:

I have a string of As and Bs and I want the number of permutations such that the distance between two Bs is at least 2

for n = 3, the number of valid strings is 4
BAA
AAB
ABA
AAA

for n = 6,
AABAAB is valid 
BABAAA is not valid because the distance between the first two Bs is 1
AAAAAA is valid
BAAAAA is valid
ABAAAB is valid

Answer 1

Hint: Each acceptable string of length $n\ge3$ either begins with an A followed by an acceptable string of length $n-1$, or with a BAA followed by an acceptable string of length $n-3$.

Answer 2

This might helps:

Change $B$ to $ABA$, and calculate with dividing cases by the number of $ABA$.

You might also have to consider the case when $B$ is in the end of the sequence.

Answer 3

Hint: let $C(n)$ be the number of acceptable strings of length $n$ that end with $B$ Let $D(n)$ be the number that end with $BA$ Let $E(n)$ be the number that end with $AA$. Can you write coupled recurrences for each of these? The answer you want is then $C(n)+D(n)+E(n)$ You might start with a spreadsheet to see what is happening. It is OEIS A164316