# Fibonacci numbers as numbers of strings over alphabets

i am asked to show that for $n \geq 3$ $F_{n} =$ the number of strings of size $n - 2$ over the alphabet ${a,b}$ with no consecutive $b$s.

Base case is obvious. $F_{n+1} = F_{n} + F_{n-1}$ so we use strong induction and get that its the sum of the number of strings of size $n-2$ and $n-3$ with no consecutive $b$s. So i figure we should count how many such strings there are:

$2^{n-2} + 2^{n-3} - (n-3)(n-4)! - (n-4)(n-5)!,$ where the subtractions come from the fact that, for example, in the case of $n-2$ long strings we have $n-3$ consecutive pairs and the rest can be permuted. I am quite sure this is wrong, because what if say two of the symbols are the same, so that the permutation leaves the string unchanged, and i am assuming in this case it shouldn't count as a new string.

In any case, i am stuck here, so any help would be appreciated. Thanks

-

Suppose that we want to construct the sequence of $a$, $b$ with length $n+1$.

If the last term is $a$, other $n$ terms can be any sequence which satisfies the condition, so we have $F_n$ sequences.

If the last term is $b$, $n$th term has to be $a$, since $n$th and $n+1$th terms cannot be both $b$. Now, other $n-1$ terms can be any sequence which satisfies the condition, so we have $F_{n-1}$ sequences.

Thus we have: $$F_{n+1}=F_n+F_{n-1}.$$

-
$F_{n}$ is the number of sequences of length $n-2.$ If the last term is $a,$ you are left with $n$ terms – user168593 Aug 8 '14 at 3:15
@user168593 Oh, it seems to be. Shifting subscripts might be needed. – The Great Seo Aug 8 '14 at 3:40

Let $a_n$ and $b_n$ be the number of strings of size $n-2$ that ends with $a$ and $b$, respectively. Then you have the following recursion. $$a_n = a_{n-1}+b_{n-1}$$ and $$b_n = a_{n-1}$$, with the obvious identity $F_n = a_n+b_n$. Now you can easily prove the rest using induction.

-
I am sorry, but why is $F_{n} = a_{n} + b_{n}$ so obvious? – user168593 Aug 8 '14 at 3:20
Because a string can end with either $a$ or $b$, according to your formulation of the problem. – dezdichado Aug 8 '14 at 16:51