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.