Question $9$:

Consider strings over the alphabet $\{a,b,c\}.$ An $aa-$free string is a string in which there

are no substrings $aa.$ Let $T_n$ be the number of $aa-$free strings of length $n.$

$($a$)$ Determine $T_1$ and $T_2,$ and develop a recursive expression for $T_n.$

$($b$)$ Express $T_n$ for $n3$ using some number from this assignment.

$($c$)$ Prove that $T_{m+n+1}=2*T_n{T}_m+4*T_{n-1}{T}_{m-1}$ for $n2,m2$ using a combinatorial

argument. That is$,$ what is an alternate way to count an $aa-$free string of length

$m+n+1?$

$($d$)$ Prove that $T_{2n+2}=4*T_n^2+8*T_n{T}_{n-1}$ for $n2$ using a combinatorial argument. That

is$,$ what is an alternate way to count an $aa-$free string of length $2n+2?$