I'm working on a probability question, and I'm trying out a recursive approach, which I just learned, to solve this problem so I just need some verification of the correctness. If I do a step wrong, give me a hint about what's wrong. Here's the question.
You flip a fair coin 9 times in succession. The probability that no three consecutive heads appear in the sequence can be written as $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.
I create a recursion as follows: Let $S_n$ be the amount of sequences with no three consecutive heads of length $n$. I construct $S_n$ as follows: If the first flip is tails, then any sequence of length $n-1$ satisfies the conditions. If I get heads, then the second flip could be heads or tails. If I flip tails on the second flip, then as above, any sequence of length $n-2$ satisfies the conditions. If I flip heads on the second flip, then the third flip must be tails to satisfy the conditions, after which any sequence of length $n-3$ satisfies the conditions. Thus, I get the recursion $S_n=S_{n-1}+S_{n-2}+S_{n-3}$.
For $n=1$, we have H or T, so $S_1=2$. For $n=2$, any of the four sequences work, so $S_2=4$. For $n=3$, any sequence but HHH works, so we have $S_3=7$. I now use the recursion to compute $S_9=274$. Thus, the probability is $$\frac{274}{2^9}=\frac{137}{256}$$ from which we get $137+256=\boxed{393}$.
Your solution is correct. Another way of looking at it is, you are considering the strings of 3 states: that end in T (or are empty), TH, or THH. Then each "step" is to flip a coin and put the result on the end of the string, so you get the transition matrix:
$$M = \begin{array} {r|ccc} & T & TH & THH \\ \hline T & 1 & 1 & 0 \\ TH & 1 & 0 & 1 \\ THH & 1 & 0 & 0 \\ \end{array}$$
where $M_{y, x}$ is the number of ways to transition from state $y$ to state $x$. Then you want the number of ways to transition from the empty string to each of the states in 9 steps, which is $$(M^9)_{1,1} + (M^9)_{1,2} + (M^9)_{1, 3} = M^9 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = 274$$