Call a string of letters “legal” if it can be produced by concatenating (running together) copies of the strings ‘a’, ‘b’, ‘cc’ and ‘ddd’. For example, the string ‘accb’ is legal because it can be produced by concatenating ‘a’, ‘cc’ and ‘b’, but the string ‘ccca’ is not legal.
For each integer n ≥ 1, let tn be the number of legal strings with n letters. For example, t1 = 2 (‘a’ and ‘b’ are the legal strings).
How can you find a recurrence for tn that holds for n>4 and explain why it gives the correct number for tn?
Thanks for the help!
Hint: Well lets say that you have a string of length $n,$ call it $x$ then there are $4$ options, either $$x = ya,$$ $$x = yb,$$ $$x = ycc,$$ $$x = yddd,$$ So if you call $t_n = \text{# legal strings of length }n,$ then they are formed by strings in $t_{n-1}$ by concatenating $a$ or $b$ plus $t_{n-2}$ by concatenating $cc$... Can you finish?