# Words with A's and B's [closed]

Find the number of words of length $11$, where each letter is an $A$ or a $B$, and no two $A$s are consecutive. I got confused after making several cases and it looks like a recurrence relation... Any help?
Thanks.

• Words with As and Bs are binary strings, this should be helpful math.stackexchange.com/questions/1098439/… – 655321 Feb 16 '15 at 6:48
• Let $a_n$ be the number of such sequences of length $n$. Let $n\ge 2$. There are two types, the ones that end with B and the ones that end with A. The ones that end in B are obtained by appending a B to a good sequence of length $n-1$, so there are $a_{n-1}$ of them. The ones that end with A are obtained by appending BA to a good sequence of length $n-2$, so there are $a_{n-2}$ of them. Thus $a_n=a_{n-1}+a_{n-2}$, a familiar recurrence. Finally, note that $a_0=1$ and $a_1=2$. Now use the recurrence to find $a_{11}$. – André Nicolas Feb 16 '15 at 6:50

The number of the requested series is a Fibonacci sequence starting with 2,3: 2,3,5,8, 13,..., 235 at the 11$^{th}$ place.
This development of the number of sequence goes like shown in the following table. Here the $(n+1)^{th}$ element of the "A" column equals the $n^{th}$ element of the "B" column and the $(n+1)^{th}$ element of the "B" column equals the sum of the numbers in the $n^{th}$ (previous) row: