I am trying to understand the following problem:
For each integer $n \geq 1$,let $t_n$ be the number of strings of $n$ letters that can be produced by concatenating copies of the string 'a','bb' and 'cc'.
For example:
$t_1=1$ ('a' is the only possible string)
$t_2=3$ ('aa','bb' and 'cc').
a) Find $t_3$ and $t_4$.
My guess: Is $t_3=0$ and $t_4=0$?
b) Find a recurrence for $t_n$ that holds for all $n \geq 3$. Explain why your recurrence gives $t_n$.
I do not see how to find the recurrence.
a) consider possible string of length $3$.
Notice that $a$ must be used as it is the only small building block of odd length. It can be used $1$ time, or $3$ times.
$$abb, acc, bba, cca, aaa$$
Now consider possible string of length $4$.
Cases where $a$ is used $4$ times: $$aaaa$$
Cases where $a$ is used twice: $$aabb, abba, bbaa$$
$$aacc, acca, ccaa$$
Cases where $a$ is not used.
$$bbbb, cccc, bbcc, ccbb$$
b) Hint for part b.
Consider what if the string of length $n$ begins with $a$. Then we just have to concatenate $a$ with another string of length $n-1$.
What about string of length $n$ that begins with $b$ and $c$?