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.

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?

share|improve this question
3  
You are flooding the system with questions. If you need that much help, you're better off going to your teacher to ask for help, or perhaps hiring a tutor. In any event, ask one question, wait for an answer, meditate on it until you understand it, then you'll be in a better position to ask a second question. –  Gerry Myerson Apr 20 '12 at 6:06
    
Sorry i understand. –  soniccool Apr 20 '12 at 6:08
    
This was discussed at meta, e.g. here and here. 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. –  Martin Sleziak Apr 20 '12 at 7:06

1 Answer 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$?

share|improve this answer

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.