# Combinatorial problem, (resursive functions).

1. Jun 15, 2007

### MathematicalPhysicist

my question is as follows:
how many words with n letters, you can construct with A,T,G,C such that ACT and TTT will apear in the word?
well i thought to count the number of the words where ACT and TTT do not appear and then substract this from 4^n.
now if we write the number of ways to do so with a_n.
then if the first word is either G or C then we have 2a_n-1 way to do so.
if the the first word is either T or A then we have 2a_n-1 words, from this we substract the number of words where in the second letter and the third letter appears C or T, or T respectively, i.e we have 2a_n-2+a_n-3, i.e
we have this recursive formula:
a_n=2a_n-1-2a_n-2-a_n-3, where a0=1, a1=4, a2=4^2=16
im not sure my explnantion is 100 percent valid, now i only need to find a_n (which is easy cause this a linear equation), and then substract this from 4^n.
but is the equation correct?