0

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?

N. F. Taussig
  • 76,571
johnson
  • 519

2 Answers2

2

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)

JMoravitz
  • 79,518
  • In fibonacci, what would be the $a_n$ and $b_n$ in respect to the fibonnaci sequence? – johnson Mar 03 '17 at 06:59
  • @johnson as noted, $a_n=b_{n-1}$ and $b_n=w_{n-1}$ so we get $a_n=w_{n-2}$, so $a_n$ and $b_n$ also follow the fibonacci sequence themselves. Keep track of the indices. With $F_n$ the fibonacci sequence with $F_0=0$ and $F_1=1$, we have $w_n = F_{n+1}$, $b_n=F_n$ and $a_n = F_{n-1}$, with small adjustments made for when $n=0$ since technically you cannot have a length zero word which "starts with $A$" or which "starts with $B$" but you can technically have a "valid word of length zero". – JMoravitz Mar 03 '17 at 07:05
0

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}$

johnson
  • 519