Changing-sided dice probability problem. Suppose you roll a fair $6$-sided dice, and that the number you roll is $m$.
If $m=1$, stop. Otherwise, roll an $m$-sided dice. The number you roll is $n$. If $n=1$, stop. Otherwise roll an $n$-sided dice... etc.
What is the probability it will take exactly $x$ rolls to roll a 1?
So far I see a pattern, but I'm wondering if there's a better way of expressing these nasty sums, or if it's even possible?
$$P(1)=\frac{1}{6}$$
$$P(2)=\frac{1}{6}(\frac{1}{6}+\frac{1}{5}+\frac{1}{4}+\frac{1}{3}+\frac{1}{2})$$
$$P(x)=\underbrace{\frac{1}{6}\sum_{j_1=2}^{6}\left(\frac{1}{j_1}\sum_{j_2=2}^{j_1}\left[\frac{1}{j_2}\sum_{j_3=2}^{j_2}(\ldots)\right]\right)}_{x-1 \mbox{ sigmas}}$$
 A: This looks like a classic Markov Chain problem.
There are 6 states (6,5,4,3,2,1), and you start at 6 and end at 1.  The transition matrix is:
$P=\left(\begin{array}{cccccc}
\frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6}\\
0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5}\\
0 & 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4}\\
0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3}\\
0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2}\\
0 & 0 & 0 & 0 & 0 & 1\\
\end{array} \right)$
So the probability that the state will be 1 after n terms can be read off using matrix multiplication (which is basically a neat way of organising your summations!)
$(\begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0\end{array}) \cdot P^n$
Actually, this will give you the probabilities that the state will be [6,5,4,3,2,1] after n turns.
Edit: to ensure that the final state is captured on exactly $n$ throws:
$P=\left(\begin{array}{ccccccc}
\frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & 0\\
0 & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & 0\\
0 & 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0\\
0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0\\
0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{array} \right)$
Then figure out:
$(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0\end{array}) \cdot P^n$
The 6th number should be the probability that you're after (and the 7th number will be the cases where it reached 1 before $n$)
It can be confirmed that this spits out the 29/120 answer for n=2 at wolfram alpha here:
Wolfram Alpha Calculation (change the power if you want)
A: It's not necessary to add a 7th state to be able to read off the probability that it was at 1 on the nth throw and not earlier.  Just use the original 6x6 for P above except change the last row to all 0's as nathan suggested. We don't need a separate output for the absorbing state, so that last row need not sum to 1.  It's OK to use the 7x7 also, but the 7th output value will simply be 1 minus the sum of the other 6 values.
Also it should be P(2) = 29/120.
