Recursion for strings.

Question

Write a recursive procedure to compute the number of strings from $\{A, C, T, G\}$ of length $n$ that do not have $2$ consecutive $A$’s.

Answer 1

Let

$f(n)$ be length $n$ string starting with $A$ with NO consecutive $A$.

$g(n)$ be length $n$ string not starting with $A$ with NO consecutive $A$.

Then what you want is $h(n)=f(n)+g(n)$ because that counts all strings of length $n$ with no consecutive $A$.

We have $f(n)=g(n-1)$ because for any string in $f(n)$ which has to start with an $A$, the second letter must not be an $A$ and hence the substring starting from the second letter is a member in $g(n-1)$.

We also have $g(n)=3f(n-1)+3g(n-1)$ because the first letter of g(n) is not an $A$ so the substring starting from the second letter can be from either $f(n-1)$ or from $g(n-1)$. We have three choices for the first letter of $g(n)$ so hence the formula.

From this we now $g(n)=3g(n-1)+3g(n-2)$ by sub $f(n-1)=g(n-2)$ into the second equation.

Then from $g(n-1)=3g(n-2)+3g(n-3)$ we sub in $f(n)=g(n-1),f(n-1)=g(n-2),f(n-2)=g(n-3)$ and get $f(n)=3f(n-1)+3f(n-2)$ as well.

Now adding the two equations up, we get $(f(n)+g(n))=3(f(n-1)+g(n-1))+3(f(n-2)+g(n-2))$ hence $h(n)=3h(n-1)+3h(n-2)$ as well.

We have $h(1)=4$ and $h(2)=15$ for initial condition.