Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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

share|improve this answer
    
$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 at 3:15
    
@user168593 Oh, it seems to be. Shifting subscripts might be needed. –  The Great Seo Aug 8 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.