For each integer n>= 1, let $t_n$ be the number of strings of n letters that can be produced by concatenating (running together) copies of the strings "a", "bc", and "cb"
For example, $t_1$ = 1("a" is the only possible string) and $t_2$ = 3 ("aa", "bc" and "cb" are the possible strings).
a) Find $t_3$ and $t_4$
b) Find the recurrence for $t_n$ that holds for all n>=3. Explain why your recurrence gives $t_n$.
I am not sure if I understand the question. How do we get $t_2$ = "aa"? How would i get $t_3$ adn $t_4$ and the recurrence for $t_n$? Any guidance would be appreciated.
a) Let $S_n$ be the collection of $n$ character strings that can be made using the character strings a, and/or bc and/or cb. Then $t_n$ is the number of strings in $S_n$.
For example, $S_2$ consists of the character strings aa, bc, and cb. Thus $t_2=3$.
In part a), we are asked to find $t_3$ and $t_4$. There are more streamlined ways of doing it, but we will simply list all the strings in $S_3$ and count. Similarly, we will list all the strings in $S_4$ and count.
For $S_3$, here are all of them: aaa, abc, acb, bca, cba. Thus $t_3=5$.
For $S_4$, here are all of them: aaaa, aabc, aacb,abca, acba, bcaa, cbaa, bcbc, bccb, cbbc, cbcb. Thus $t_4=11$.
b) Listing and counting can be tedious, and also error-prone. So we find a more efficient way of calculating $t_n$, by finding a recurrence.
Let us count the number of strings in $S_{n+1}$ efficiently. Such a string can be of one of two types:
A Type (i) string is one that ends with an a;
A Type (ii) string is one that ends with bc or cb.
Any Type (i) string with $n+1$ characters is obtained by appending an a to any string in $S_n$, and different strings in $S_n$ yield different Type (i) strings of length $n+1$. Thus there are $t_n$ Type (i) strings with $n+1$ characters.
Any Type (ii) string with $n+1$ characters can be obtained by appending bc or cb to any string in $S_{n-1}$. Thus there are $2t_{n-1}$ Type (ii) strings of length $n+1$. It follows that $$t_{n+1}=t_n+2t_{n-1}.\tag{1}$$ The above recurrence is easy to compute with. For example, we saw that $t_3=5$ and $t_4=11$. It follows that $t_5=21$, and therefore $t_6=43$.
Remark: One can even use recurrence (1) to find a simple closed form formula for $t_n$, but since the problem did not ask for that we shall not do so.