Number of Arrangements from the set $\{A,B\}$ with no consecutive As allowed

Question

I'm trying to do this by recurrence.

$n=1$: 2

$n=2$:3

$n=3$:5

$n=4$:8

$n=54:12

I can't seem to find a pattern within the first 5 which should be all I need.

The book gives me the answer,

let $a_n$ be the number of arrangements of words that start with A

let $b_n$ be the number of arrangements of words that start with B.

let $w_n$ be the number of arrangements for words of n length.

$w_n = a_n + b_n$

Is there no better answer?

Answer 1

The books "answer" is really just a hint to get started, as it doesn't tell you what recurrence to use for $a_n$ or $b_n$.

Let $w_n$ denote the number of valid words of length $n$. Let $a_n$ denote the number of valid words that begin with $A$ specifically. Let $b_n$ denote the number of valid words that begin with $B$ specifically.

A valid word of length $n\geq 1$ will either begin with an $A$ or it will begin with a $B$ and there is no overlap between the two cases and all valid words will fall into one of these two cases. As such $w_n=a_n+b_n$

Now, notice that a valid word of length $n$ which begins with the letter $A$ can be described as the letter $A$ followed by a valid word of length $n-1$ which begins with $B$ (because the second letter could not be an $A$ as per the condition no two $A$'s can be adjacent). This is a very important observation to make. This brings us to the understanding that $a_n = b_{n-1}$.

Finally, notice that a valid word of length $n$ which begins with the letter $B$ can be described as the letter $B$ followed by a valid word of length $n-1$ which starts with either letter (since no restriction is placed on $B$'s being adjacent). This brings us to the understanding that $b_n = w_{n-1}$

So, combining all of this information, we get $w_n = a_n+b_n = b_{n-1}+w_{n-1}=w_{n-2}+w_{n-1}$

That is, $w_n = w_{n-1}+w_{n-2}$. Our familiar fibonacci recurrence. Keeping track of the specific seed values used, $w_0=1, w_1=2, w_2=3,\dots$

(note: $w_5$ should have equaled $13$ which may have prevented you from spotting the fibonacci sequence right away. ABABA, ABABB, ABBAB, ABBBA, BABAB, BABBA, BBABA, ABBBB, BABBB, BBABB, BBBAB, BBBBA, BBBBB)

Answer 2

I believe I have it,

I was trying to create a recursion from looking at the words, but by looking at the words by each letter, I was able to find a pattern.

$a_n = a_{n-1} + a_{n-2}$

$b_n = b_{n-1} + b_{n-2}$

Therefore, $w_n = a_n + b_n = a_{n-1} + a_{n-1} + b_{n-1} + b_{n-2}$