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?