1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Words with As and Bs are binary strings, this should be helpful math.stackexchange.com/questions/1098439/… $\endgroup$ – 655321 Feb 16 '15 at 6:48
  • 3
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Feb 16 '15 at 6:50
0
$\begingroup$

The number of sequences ending with A is a Fibonacci sequence; 1, 1 , 2, 3, ..., etc. The number of sequences ending with B is another Fibonacci sequence starting at 1,2: 1,2,3,5, ..., etc.

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:

\begin{matrix} \text{n} & \text{endig in A} & \text{ending in B}&\text{sum}\\ \hline 1&1&1&2\\ 2&1&2&3\\ 3&2&3&5\\ 4&3&5&8\\ 5&5&8&13\\ 6&8&13&21\\ 7&13&21&34\\ 8&21&34&55\\ 9&34&55&89\\ 10&55&89&146\\ 11&89&146&235\\ \end{matrix}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your approach is correct, but its not completely Fibonacci. The starting terms are 0,1. Therefore the answer is 233. $\endgroup$ – user167045 Feb 16 '15 at 13:57
  • $\begingroup$ Let is be so :) $\endgroup$ – zoli Feb 16 '15 at 14:04