expected value of number of selections from $\{ 1,2, \dots, n\}$ with replacement such that the selection process stops when the sum exceeds $n$ I was going through my old notebooks and saw this problem:
Determine $\lim _{n \rightarrow \infty} \mathbb{E}(X)$ where $X$ denotes the random variable corresponding to the output of the following algorithm, where all random choices made are mutually independent and has an integer $n \geq 1$ as input:

INPUT: n
 
sumOfSelections = 0;
j = 0;

while sumOfSelections <= n
    do 
       j = j + 1;
       x_j = uniformly random element in {1,2,...,n};
       sumOfSelections = sumOfSelections + x_j
endwhile;
return j


I really have a weak intuition for these kinds of problems and am basically lost on how to proceed. My first instinct is that the average value of x_j is $\frac{n+1}{2}$ and so $X$ is 2 on average, but I think this line of attack is wrong.
How does one get $\mathbb{E}(X)$ not by averaging arguments but by using the probabilities of the outcomes of the algorithm?
 A: Essentially, we roll a fair $n$-sided die, with faces number from $1$ through $n$, until the sum of the numbers rolled equals $n$ or more.  The questions asks for the expected number of rolls.
Let $E_s$ be the expected number of rolls remaining, if the sum of the numbers rolled so far is $s$.  We have $$E_s=\begin{cases}
0,&s\geq n\\
1+\frac1n\sum_{j=1}^nE_{s+j},&s<n
\end{cases}$$
The second case comes from the fact that if the current sum $s<n$ we have to roll once more, and for each $j$, with probability $\frac1n$ , the next roll is $j$, and we have an average of $E_{s+j}$ additional rolls yet to come.
We want to compute $E_0$.  For a specific $n$, this is easily done by working backwards.  We know that $E_{n-1}=1$ since any roll will get us to $n$.  Now,$$\begin{align}
E_{n-2}&=1+\frac1nE_{n-1}=\frac{n+1}n\\
E_{n-3}&=1+\frac1n(E_{n-2}+E_{n-1})=\left(\frac{n+1}n\right)^2\\
E_{n-4}&=1+\frac1n(E_{n-3}+E_{n-2}+E_{n-1})=\left(\frac{n+1}n\right)^3
\end{align}
$$
and it's easy to guess the pattern.  I haven't proved that this pattern will continue. Can you do it?
If the pattern does indeed continue, then $$E_0=\left(\frac {n+1}n\right)^{n-1}\to e\text{ as }n\to\infty$$
