Question: 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

Answer: 
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}.$$
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.