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 a recurrence for $t_n$ that holds for all $n ≥ 3$ Explain why your recurrence gives $t_n$
(You do not have to solve the recurrence.)
Answer I've got so far (by no means do i think this is even close to right)
a) $t_3$ = $"aaa"$, $"bca"$, $"acb"$ ??
a) You miss two possibilities. aaa, abc, acb, bca, cba, thus $t_3=5$.
b) $t_4$ is 11. Above 5 with an additional a after it, then those form $t_2$ with bc after it, then those from $t_2$ with cb after it.
c) Can you figure this out yourself using the information in b?