In DNA chain, there are four types of bases: A, C, G, T. Let $g(n)$ be the number of configurations of a DNA chain of length $n$, in which the sequences TT and TG never appear. Write a recurrence for $g(n)$. Determine the asymptotic behavior of the recurrence. Also, prove whether this rate of growth is $o(n^{ n^{1/2}}), \Theta(n^{ n^{1/2}}),$ or $\Omega(n^{ n^{1/2}})$.
My answer: $g(n)=A(n)+C(n)+G(n)+T(n)$
$g(n)=g(n-1)+g(n-1)+g(n-1)+A(n-1)+C(n-1)$
$g(n)=3g(n-1)+2g(n-2)$
After solving this recurrence, we get
$$\begin{align} g(n) &= (\frac{(4)(17)^{1/2}+16}{(3)(17)^{1/2}+17})(\frac{3+(17)^{1/2})}{2})^n \\ &+(\frac{(17)^{1/2}-5)}{2(17)^{1/2}})(\frac{3-(17)^{1/2}}{2})^n \end{align}$$
Therefore when $n$ is large, $(\frac{3-(17)^{1/2})}{2})^n$ become smaller and smaller So we can write $$g(n) = \Theta((\frac{3+(17)^{1/2})}{2})^n).$$
(Do I determine the asymptotic behavior of the recurrence correctly?)
But I do not know what is the rate of growth, if we take the limit of $\frac{g(n)}{n^{ n^{1/2}}}$,where n tend to infinity, it seems impossible to calculate it. How could I determine the rate of growth?
You solved the recurrence and found its asymptotic behavior correctly. The growth is $c^n$, where $c=\frac12(3+\sqrt{17})$, and you are asked how this compares with $n^{n^{1/2}}$. The latter is faster: to see this, take logs of both, and note that $$ (\log c)n=o\Big(n^{1/2}\log n\Big) $$