0
$\begingroup$

Consider a language that uses the alphabet {A, B, C} In this language words obey one single rule: a B cannot follow a B. How many words of length n exist in this language?

How do i go about solving this and what should i use in discrete math as a tool?

  • 0
    This was discussed at meta, e.g. [here](http://meta.math.stackexchange.com/questions/3472/how-much-asking-is-too-much) and [here](http://meta.math.stackexchange.com/questions/610/user-flooding-the-site-with-questions-more-than-6-day). It is mentioned there that at most 50 questions a month are allowed - if you try to post more, the site will not accept new question. At the current rate you would use your 50 questions pretty fast.2012-04-20

1 Answers 1

1

Hints:

Let $a_n$ be the number of words of length $n$ which do not end with a B and $b_n$ be the number of words which do end with a B. So the total number of words of length $n$ is $a_n+b_n$.

Can you see the starting position is $a_0=1$ and $b_0=0$?

Can you express $a_n$ and $b_n$ in terms of $a_{n-1}$ and $b_{n-1}$?

Can you then express $a_n$ in terms of $a_{n-1}$ and $a_{n-2}$?

Can you solve this recurrence to find an expression for $a_n$ in terms of $n$?

Can you find expressions for $b_n$ and for $a_n+b_n$?