Recurrence Relation Homework Question 3 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.
 A: 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$.
A: 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.
