Probability you end dice rolling sequence with 1-2-3 and odd total number of rolls Here's a question from the AIME competition:

Misha rolls a standard, fair six-sided die until she rolls 1-2-3 in that order on three consecutive rolls. The probability that she will roll the die an odd number of times is ${m\over{n}}$ where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

This is what I did. Let's add up the following cases with an odd number of rolls, where in each sequence of XXX... there is no subsequence of 123:

*

*Probability of 123: $({1/6})^3$

*Probability of XX123: $({1/6})^3$

*Probability of XXXX123: $(1/6)^3(1 - 2(1/6)^3)$

*Probability of XXXXXX123: $(1/6)^3(1 - 4(1/6)^3 + (1/6)^6)$

*Probability of XXXXXXXX123: $(1/6)^3 (1 - 6(1/6)^3 + \binom{4}{2} (1/6)^6) = (1/6)^3 (1 - 6(1/6)^3 + 6(1/6)^6)$

*Probability of XXXXXXXXXX123: $(1/6)^3 (1 - 8(1/6)^3 + \binom{6}{2} (1/6)^6 - 4(1/6)^9) = (1/6)^3 (1 - 8(1/6)^3 + 15(1/6)^6 - 4(1/6)^9)$

*Probability of XXXXXXXXXXXX123: $(1/6)^3 (1 - 10(1/6)^3 + \binom{8}{2} (1/6)^6 - \binom{6}{3}(1/6)^9 + (1/6)^{12}) = (1/6)^3 (1 - 10(1/6)^3 + 28 (1/6)^6 - 20(1/6)^9 + (1/6)^{12})$

*$\ldots$and so forth.

I notice some obvious patterns, but nonetheless I'm stuck with proceeding further. Any hints towards finding a way to add this all up would be well-appreciated. Please, no complete solutions.
Edit: For the record, the correct probability after you add this all up should be ${{216}\over{431}}$.
Edit 2: There are a number of solutions to this problem here: https://artofproblemsolving.com/wiki/index.php/2018_AIME_II_Problems/Problem_13
However, all the solutions at the link are extremely clever, whereas my approach is a naive brute force. I would like some hints/suggestions on how to make my brute force approach work.

I note that you want to make your own method work rather than consider other solutions. To see what is happening it is clearer to work with algebra rather than working out numerical values.
The basis of your method is the equation $$p_{n}=(\frac{1}{6})^3(1-p_3-p_4- ... -p_{n-3}).$$
The pattern to notice here is that the RHS only changes slightly as $n$ increases. So , for example, $$p_{n+1}=(\frac{1}{6})^3(1-p_3-p_4- ... -p_{n-3}-p_{n-2}).$$
Therefore the simplest form for your equation is $$p_{n+1}=p_{n}-(\frac{1}{6})^3p_{n-2}.$$
We then have
$$p_3=(\frac{1}{6})^3,p_5=p_4, p_7=p_6-(\frac{1}{6})^3p_4, p_9=p_8-(\frac{1}{6})^3p_6, ... $$
These equations are much easier to add than the original ones.
$$p_3+p_5+p_7+.....=(\frac{1}{6})^3+(p_4+p_6+p_8+...) -(\frac{1}{6})^3(p_4+p_6+p_8+...).$$
Therefore the probability of an odd number of rolls is $\frac{1}{216}$ plus $\frac{215}{216}$ times the probability of an even number of rolls.
