Recurrence and Characteristic equation?

• Dec 4th 2012, 03:32 PM
elpermic
Recurrence and Characteristic equation?
Hey there, I'm in need of some help with this problem.

After careful and intensive study UCLA scientists have discovered the long lost
genes of the unicorn. The genes of the unicorn consist of sequences made up of 6 nucleotides,
the normal 4 present in DNA represented here by the letters C, G, T and A, plus 2 more
present only in unicorn genes, which they have represented with the letters U and L. The
sequences present in the unicorn DNA must all satisfy the following constraints
• the sequence starts with one of the nucleotides C,G,T or A and the rest of the sequence
(if any) qualifies as a unicorn DNA sequence,
• or the sequence starts with the nucleotide U followed by the nucleotide C and the rest
of the sequence (if any) qualifies as a unicorn DNA sequence,
• or the sequence starts with the nucleotide L followed by one of the nucleotides C, G, T
or A and the rest of the sequence (if any) qualifies as a unicorn DNA sequence.
Let Un be the number of unicorn DNA sequences of length exactly n. (You may assume for
convenience that the empty sequence of length 0 is a unicorn DNA sequence.) Examples of
unicorn DNA sequences are ¸, C, G, LT, UC, ACT, UCC, LAG, UCLA, TACT, ATUCLC,
UCLCAT,. . .
(a) Obtain a recurrence relation for Un and calculate its initial conditions.
(b) Solve the your recurrence for Un by obtaining a formula for Un in terms of n.

I've been trying to find the initial conditions for the characteristic equation Un. I'm hoping somebody can help guide me through this problem. Thank you!