Find a recurrence relation for the number of n-digit (n

Carlie Fernandez

Carlie Fernandez

Answered question

2022-05-28

Find a recurrence relation for the number of n-digit (n greater or equal to 1) ternary sequences without an occurrence of the substring 012.

Answer & Explanation

nifeonibonitozg

nifeonibonitozg

Beginner2022-05-29Added 12 answers

Assume the number of ternary sequences with n digits = a n
For the first digit to be 0 , 1 , o r   2, the number of ternary sequences of the remaining n 1 digits are all a n 1 , but for the first digit is 0, the next digits cannot be 12,
Thus, the associated a n 3 number of ternary sequences must be excluded.
If the first digit is 2 ,the next number cannot be 1, then the associated a n 2 number of ternary sequence must be excluded.
Therefore, the recurrence relation will be a n = 3 a n 1 a n 3 a n 2

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?