How can I find a recursive relation for the following words?

Question

if c(n) is the number of words created by the alphabet {a,b,c} with n length that the word does not contain 'ab' term then write a recursive relation for c(n).

I don't have enough knowledge of the recursive relations but I have tried guessing the relation.

A word of length $n$ without ab is a word of length $n-1$ without ab followed by a, b or c, except you can't count the words of length $n-2$ without ab followed by ab. — Gerry Myerson, Apr 27 '14 at 06:36
@GerryMyerson I would think that would be good as an answer rather than just a comment. — Mike, Apr 27 '14 at 06:42
Gerry Myerson can you explain more what do you mean by "can't count the word of length n-2 without ab followed by ab". — Freelancer, Apr 27 '14 at 06:52

score 2 · Accepted Answer · answered Apr 27 '14 at 16:54

I guess since the comment wasn't enough, I'll explain it. To form a valid word of length $n$, take a valid word of length $n-1$ and append an a, b, or c. The problem is some of those new words will now end in ab. However, the first $n-2$ characters of such words will not contain ab, so we created $c(n-2)$ invalid combinations, which can simply be subtracted out.

How can I find a recursive relation for the following words?

1 Answers1