My questions:
Call a string of letters "legal" if it can be produced by concatenating (running together) copies of the following strings: 'v', 'ww', 'xx' 'yyy' and 'zzz'. For example, the string 'xxvv' is legal because it can be produced by concatenating 'xx', 'v' and 'v', but the string 'xxxv' is not legal.
For each integer n≥1, let tn be the number of legal strings with n letters. For example, t1=1 ('v' is the only the legal string).
(a)
t2 = ? My Answer = 3
t3 = ? My Answer = 7
(b) tn = atn−1 + btn−2 + ctn−3 for each integer n≥4
where a = ? b = ? c =?
My answer: a = 1, b = 2, c = 2
(c) For each integer n≥1, let pn be the number of legal strings with n letters that also read the same right to left as they do left to right (like 'xxvxx', for example).
Which of the following expressions is equal to p101?
(a)t50+2t49 (b)t50+2t48 (c)t50+t48 (d)p50+p49 (e)p50+2p49 (f)p100+p99 (g)t50+t49 (h)t100+t99
Someone know how to solve question (c), not quite understand this question. And also someone can help me check if the answers for (a) and (b) are correct
For Question $(c)$-
For the string to palindromic and have $101$ characters, it must be of the form, $\underbrace{a_1a_2 \dots a_{50}} b_1 \underbrace{a_{50}a_{49} \dots a_{1}}$ or $\underbrace{a_1a_2 \dots a_{49}} b_1b_2b_3 \underbrace{a_{49}a_{48} \dots a_{1}}$. Using this, you can discover the reccurence relationship by considering the $a$ sequence and the $b$ sequence.