Recurrence Relation Homework Question 3

Question

This is a HW question

Consider the set $T={A,B,C,1,2,3,4}$. For $ n\geq 0$ let $c_n$ be the number of n-character sequences of elements of T that contain no consecutive letters (distinct or identical)

I believe there has to be two cases here. eg.. One where $a_{10}$ ends in a letter then $a_{11}$ has 4 choices for the 11th digit ${1,2,3 or 4}$ else if $a_{10}$ ends with a number then we can pick any element from the set T for the 11th character in $a_{11}$

Is my understanding of the question correct ? If it is could I get a hint on how to proceed.

Answer 1

Call a word good if it has no two consecutive letters. Let $c_n$ be the number of good words of length $n$.

We count the number of good words of length $n+1$.

These are of two types, (i) the ones that end with a digit and (ii) the ones that end with a letter.

(i) There are as you saw $4c_n$ good words of length $n+1$ that end with a digit. For we can append any digit to a good word of length $n$.

(ii) What about the good words of length $n+1$ that end with a letter? The $n$-th symbol (if there is one) must be a digit, and the string of length $n-1$ before that can be any good string. So Type (ii) words of length $n+1$ are made by taking a good word of length $n-1$ and appending a digit then a letter. This can be done in $12$ ways. So there are $12c_{n-1}$ Type (ii) good words of length $n+1$.

Now one can write down a nice linear recurrence for $c_{n+1}$ in terms of $c_n$ and $c_{n-1}$.

Remark: A better way to solve the problem is is to let $a_n$ be the number of good strings that end with a digit, and $b_n$ the number of good strings that end with a letter. One gets very natural $2$-variable recurrences. The cleanest analysis then uses matrices.

Answer 2

Yes, your understanding is correct. One way to proceed is to introduce a second variable: let $a_n$ be the number of allowable sequences of length $n$ that end in a digit. Then $a_{n+1}=4c_n$, since you can always append any of $4$ digits to an allowable $n$-character string.

HINT: Express $c_{n+1}$ in the form $kc_n+\ell a_n$ for some positive integers $k$ and $\ell$ that do not depend on $n$, and use the relation $a_n=4c_{n-1}$ to eliminate $a_n$.