Find a recurrence relation for the number of ternary strings that do not contain consecutive symbols that are the same.

Question

I tried to solve this question by subtracting the number of strings that contain consecutive symbols that are same from the total number of symbols possible of length n.

Let b_n denote the number of strings of length n, with consecutive symbols that are same. Then b_n can be obtained by 3*b_n-1 , since there are 3 choices for appending the string of length n-1 to form a string of length n. So if a_n denotes the number of strings of length n that do not contain consecutive symbols that are same then, a_n = 3ⁿ - b_n-1 . But I am stuck, how do I go from here ? How to solve such problems without generating the sequence and guessing ? I am having a hard time doing so.

score 0 · Accepted Answer · answered Oct 10 '18 at 20:53

0

HINT

Well, if $a_n$ denotes the number of ternary strings without consecutive symbols, and you are given such a string of length $n-1$, you can form an $n$-string by attaching $0,1,2$ at the end except you must make sure not to duplicate the last symbol. In other words you have 2 choices for the last character.

Can you finish this?

answered Oct 10 '18 at 20:53

gt6989b

54,422

1

Yes, so a(n)= 2a(n-1) , that seems so obvious now, thanks. Sometimes I make such simple things so complicated. – srishti77714 Oct 10 '18 at 20:55
@srishti77714 this answer is correct :-) – gt6989b Oct 10 '18 at 20:58

Find a recurrence relation for the number of ternary strings that do not contain consecutive symbols that are the same.

1 Answers1

Linked