# Counting with recurrence DNA

Let X(n) be the number of length n DNA sequences (sequences using only the letters ATCG) that avoid the substring AA. Write a recurrence for X(n) and explain in words why it satisfies the recurrence.

Any length n DNA sequence must start with either A; T; C; G. If it starts with T; C; G, then it does not affect the later bases and so the number of length $n$ DNA sequences that avoid AA and start with T; C or G is $3X_{n - 1}$. If it starts with A, then the next base cannot be A, the next base must be either T, C or G ($3$ choices) and then the rest of the sequence can be any $n - 2$ length sequence that avoids AA and so the number of length $n$ sequences that start with A and avoid AA is $3X_{n - 2}$. There is one sequence of length $0$ (the empty sequence.)

Therefore the recursion is: \begin{align*} X_0 & = 1\\ X_1 & = 4X_n = 3X_{n - 1} + 3X_{n - 2}~\text{for}~n \geq 2 \end{align*}

Let's say this $N$ is $5$ : _ _ _ _ _, as the case when it starts with A, namely, A _ _ _ _. Yes, we need the second blank either be filled with T,G, C, namely . A _ _ _ _ . Yes, $5-2 =3$, which is the remaining blanks. My question is: how come $n-2$ can ensure the second bank is not filled with A. Thank you again.

Why does avoiding AA make it become $n-2$ length ? I spent half hour on this part and can't visualize it. Please help and thank you in advance.

• Who said "avoiding AA make it become $n-2$ length"?? Taking away the first two letters makes it $n-2$ length. If the sequence has length $n$, and it starts with AT (or AC or AG), then the part after the AT has length $n-2$. – bof Dec 1 '17 at 4:24
• ok when we are taking away the first two letters, how do we know what they are filled with? We could take away AT, which should be counted. Thank you. – Dmomo Dec 1 '17 at 6:54

It is not a question of avoiding $AA$ that makes $n-2$ slots available.

What is the recursive method? It says "break up a given case into smaller cases, so that one must solve only the base case".

What we are doing here is precisely that. We are breaking the task, of writing an $n$ string which avoids the substring $AA$, into smaller tasks, namely those of writing $n-1$ and $n-2$ length strings which avoid $AA$. How are we doing this? We claim that we can proceed in any one of these ways:

1) We fill the first blank with a $G,T$ or $C$. Now, there are $n-1$ places which are left, and these must be filled with $A,T,G,C$ such that $AA$ does not appear. How many ways can this be done? As we mentioned, we broke the large task into a smaller task, and you can see why the answer is $X(n-1)$.

2) We fill the first blank with an $A$. Here, we have to be careful. We have $n-1$ remaining blanks. Can we fill these however we want, as long as $AA$ does not occur twice? We can , almost.

To give an example, the string $AGTAGC$ is good on it's own, but if I put an $A$ in front of it, the string which is formed is $AAGTAGC$ which is not good. On the other hand, if I put a $G,$ or $C$ in front of it, it would still remain legitimate. That is why we have to break into cases.

So, what we must ensure, is that if the first blank is filled by an $A$, the second blank is filled by something that isn't $A$. So that must be $G,T,C$. Then, the remaining $\mathbf{n-2}$ blanks (note that now two blanks are filled : we put an $A$ in the first one and something not an $A$ in the second one) can be filled in any manner as long as $AA$ does not occur. As we know, this can be done in $X(n-2)$ ways.

Hence, we conclude that since either case 1 or 2 must occur, the recurrence is given by $X(n) = 3X(n-1) + 3X(n-2)$, along with the initial conditions $X(0) = 1$ and $X(1) = 4$.

For example, $X(2) = 3 \times 4 + 3 \times 1 = 15$, which is true, since you can take all strings in $A,T,G,C$ of length $2$ except $AA$, so the answer expected is $4^2 - 1 = 15$.

• Hi @actoh, let's say this is N is 5 : _ _ _ _ _. as the case when it starts with A, namely, A _ _ _ _. Yes, we need the second blank either be filled with T,G, C, namely . A _ <T,G,C> _ _ _ . Yes, 5-2 =3, which is the remaining blanks. My question is: how come (n-2) can ensure the second bank is not filled with A. thank you again. – Dmomo Dec 1 '17 at 6:29
• I already told you why the second blank should not be filled with an $A$ : it is so that we avoid $AA$ coming as the first two letters. $n-2$ does not ensure anything, it is what is left after ensuring that the first two letters are not $AA$. – астон вілла олоф мэллбэрг Dec 1 '17 at 6:34
• ok. if n-2 does not ensure anything. Yes. 5-2 =3. we have _ _ _ left. then how do these three empty bars know that the first two letters are not AA? – Dmomo Dec 1 '17 at 6:44
• They don't , but they don't need to! Note that these can be filled independent of what the previous letters are! They don't care if the previous letters were $GG$ or $AT$ or whatever, except it did not end with an $A$, since we ensured that. Once it did not end with an $A$, we can assume that we are starting our string afresh from that point onwards, and that's why we can use the recursion formula. – астон вілла олоф мэллбэрг Dec 1 '17 at 6:47
• you lost me when you said "since we ensured that." Can you please point out when and how? – Dmomo Dec 1 '17 at 6:51