Determining a recurrence relation (Homework)

Let ${d_n}$ be the number of DNA strings of length n that contain a pair of consecutive nucleotides of the same type. There are four symbols used in strings of DNA: A, C, G, T. The nucleotides are divided into two types: purines, A and G, and pyrimidines, C and T.

The first part of the problem involves determining the first values of ${d_n}$ with n = 1, 2, 3, which I'm pretty sure I have correct:

${d_1}$ = 0 (impossible for a string of length 1 to have a pair of consecutive nucleotides)

${d_2}$ = 8 {AG, CT, GA, TC, AA, GG, CC, TT}

${d_3}$ = ${4^3}$ - 12 = 64 - 16 = 48 (set of all strings of length 3 minus strings with out 2 consecutive nucleotide types):

{ACA, ACG, GCA, GCG, ATA, ATG, GTA, GTG, TAT, TAC, CAT, CAC, TGT, TGC, CGT, CGC}

The second part of the problem I'm having some more trouble with, which is determining the recurrence relation for ${d_n}$.

I know a good first step is to come up with cases, but this is a problem much different from any others I've done in my discrete mathematics class. Any help, even hints would be much appreciated. If you would like me to clarify anything, please let me know.

-
An overview of serveral methods for solving recurrences was given here: How does one find a formula.... Maybe you'll find something, that's suits you. – draks ... Apr 20 '12 at 8:17
@draks, thanks for the link - that's a pretty good reference for solving recurrence relations. The problem I'm having though is actually building the relation from a set of given conditions, and the first few values for the relation. – Mike Grimes Apr 20 '12 at 8:31

This is the key phrase of your solution:

set of all strings of length 3 minus strings with out 2 consecutive nucleotide types

The only problem is that for some reason you subtract 17, not 16.

How many strings do not contain two consecutive same types? You start a string with any type (4 possibilities), and at each step add one of the two possible letters of the type opposite to the last added. For $n=3$ you have $4*2^2=16$.

In general, $d_n=4^n-4\cdot2^{n-1}=4^n-2^{n+1}$. So, the sequence starts with 0, 8, 48, 224 etc.

But this is not a recurrence relation. For that, consider how you would build all the strings of length $n$: first, you may take any string of length $n-1$ satisfying the condition and add any letter to it ($4\cdot d_{n-1}$), or take a string of length $n-1$ not satisfying the condition and add one letter of the type the same as the last letter ($2\cdot(4^{n-1}-d_{n-1})$). Now sum the two to obtain the recurence relation, and check that the closed form solution for it as above.

-

Without loss of generality, let the first symbol be $A$. If the second symbol is $A$ or $G$, the rest of the string may be arbitrary. Result: $2\cdot 4^{n-2}$ strings.

If the second symbol is $C$ or $T$, then the substring you get by leaving out the first symbol must already contain a pair of consecutive nucleotides. Result: $2 \cdot x$ strings, where $x$ is the number of strings of length $n-1$ which contain a pair of consecutive nucleoids and start with a fixed symbol. Express this in terms of $d_{n-1}$.

Then, $d_n = 4 \cdot ( 2 \cdot 4^{n-2} + 2 \cdot x )$, if I am not mistaken.

-