Expected number of times to roll die before getting higher number Consider the following cute problem:
I roll a fiar 10-sided die (with sides labeled 1-10) until I get a number greater than or equal to my previous roll. If the epxexted value for the number of rolls is $m/n$ with $m,n$ relatively prime positive integers, find $m+n$ modulo $1000$. 
Forgive the useless stuff at the end, this problem is from a math contest similar to the AIME.
Now I heard from someone that there is a recursive solution to this but I haven't found using recursion. Instead I have an ugly solution with a silly mistake somewhere. I wish 2 things:


*

*Can anyone find a nice recursion solution?

*Please identify the mistake in my solution. I know my method works, but I must have made some mistake somewhere because I am not getting the desired answer $601$.
Here is my solution.
We approach this in the least cleverest way possible by using the standard definition of expected value. 
Suppose it takes $k$ rolls before we stop rolling. If we roll $r_1,...,r_k$ in that order, we need $r_k \ge r_{1}>r_{2}>...>r_{k-1}$. We shall first count the number of instances like this, and then compute the probability by dividing by $10^k$. If $r_k>r_{k-1}$, then we can choose $r_1,...r_k$ in $\dbinom{10}{k}$ ways and they are automatically ordered. If $r_k=r_{k-1}$ we similarly have $\dbinom{10}{k-1}$. We sum the binomial coefficients to find the total number of ways, and applying Pascal's formula we have $\dbinom{11}{k}$ ways total. Thus the probability is $\dbinom{11}{k}/10^k$ and the term in the expectation is $k\dbinom{11}{k}/10^k$. 
Note that $2 \le k \le 11$. The lowerbound is trivial and the upperbound is achieved by $r_1,..r_k=10,9,...1,10$. Thus the expected number of rolls is the sum of $k\dbinom{11}{k}/10^k$ from $k=2$ to $k=11$. Now, this sum is quite easy to evaluate by hand if you use the clever identity that sum from $k=0$ to $N$ of $kx^k\dbinom{N}{k}$ equals $Nx(x+1)^{N_1}$, which is obtained by taking the derivative of the binomial theorem identity. Hopefully its clear how to apply it. Using this trick, I find the expectation is 
$11/(10)^{11}(11^{10}-10^{11})$
which is confirmed by wolfram alpha: http://www.wolframalpha.com/input/?i=sum+of+k%2811+choose+k%29%2F10%5Ek+from+k%3D2+to+k%3D11
Note tht the demoniator is prime to the numerator so we simply take the numerator modulo $1000$ which is easy by the Binomial Theorem (again!) and evaluates to $611$. Hence the answer to the problem is $611$.
Note that my answer is similar to the official answer of $601$. Perhaps the official answer is wrong.
Note: this is definitely not intended solution because it involves evaluating a sum using an obscure identity I derived using calculus, as well as the Binomial theorem applied twice, and pascal's identity, and its too long. i know the intended solution involves recursion.
 A: For $i=1,2,3,\ldots\;$ let $A_i$ be the event that the $i^{th}$ roll occurs, and let $I_{A_i}$ be its indicator function. Note that the maximum number of rolls possible is $11$, for the case that the first $10$ rolls are $10,9,8,7,6,5,4,3,2,1$. Then
\begin{eqnarray*}
E(\text{#Rolls}) &=& E\left(\sum_{i=1}^{11}{I_{A_i}}\right) \\
&=& \sum_{i=1}^{11}{E\left(I_{A_i}\right)} \\
&=& \sum_{i=1}^{11}{P\left(A_i\right)} \\
\end{eqnarray*}
For the $i_{th}$ roll to occur we need rolls $1,\ldots,i-1$ to be a descending sequence of integers each taking a value between $1$ to $10$ inclusive. The number of ways for this to occur is the number of ways to choose $i-1$ of $10$ available values. This is $\binom{10}{i-1}$. The total number of ways for $i-1$ rolls to occur is $10^{i-1}$. Therefore,
\begin{eqnarray*}
E(\text{#Rolls}) &=& \sum_{i=1}^{11}{\binom{10}{i-1} \left(\dfrac{1}{10}\right)^{i-1}} \\
&=& \left(1+\dfrac{1}{10}\right)^{10}\qquad\text{(by the Binomial Theorem)} \\
&=& \left(\dfrac{11}{10}\right)^{10} \\
&=& \dfrac{25937424601}{10000000000}.
\end{eqnarray*}
Taking modulo $1000$ of numerator plus denominator gives $601$.
Sorry, I don't see a recursive solution.
A: As Mick A notes, the correct condition is $r_{1}>r_{2}>...>r_{k-1} \le r_k$. What happened is I misread "previous roll" as "previous rolls" which led me to believe that $r_k \ge r_{1}>r_{2}>...>r_{k-1}$. Now we can proceed as a similar manner as my solution.
If $r_k$ is equal to any of $r_1,...,r_{k-1}$ there $k-1$ choices for which one its equal to. Then there are $\dbinom{10}{k-1}$ ways and everything is automatically ordered. So total $(k-1)\dbinom{10}{k-1}$. Else there are $k-1$ ways to choose the $i$ such that $r_i<r_k<r_{i+1}$ and then we can choose $r_1,..,r_k$ in $\dbinom{10}{k}$ ways and again everything is ordered. So the total number of ways is 
$(k-1)\dbinom{10}{k-1}+(k-1)\dbinom{10}{k}=(k-1)\dbinom{11}{k}$
and the correct sum for the expected value is sum from $k=2$ to $11$ of
$k(k-1)\dbinom{11}{k}/(10^k)=11\dbinom{10}{k}(k-1)/10^{k}$ which we can evaluate in a similr way to my first solution (break up the sum and use the same technique) and does give the correct answer $601$.
