How to find the expected number of times required to empty the bag Suppose we have  balls in a bag. Each time we pick a random positive integer  ≤  and remove  balls from the bag. 
The process is repeated until the bag becomes empty. 
How can I find the expected number of times required to empty the bag. 
 A: Let's say the expected value of the number of times the bag is emptied when we start with $n$ balls is $f(n)$. First, let's get rid of the obvious base case: $f(0)=0$ times as the bag is already empty from the beginning.
If you pick $k$ balls, you have then picked from the bag once and you are expected to pick $f(n-k)$ since that's the number of balls left. Therefore, picking $k$ balls makes us expect to pick $1+f(n-k)$ times. We have $k=1$ to $n$ and each has a $\frac 1 n$ probability of happening, so we get:
$$f(n)=\sum_{k=1}^n \frac{1}{n}(1+f(n-k))=\sum_{k=1}^n\left(\frac{1}{n}+\frac{f(n-k)}{n}\right)=\sum_{k=1}^n\frac{1}{n}+\sum_{k=1}^n\frac{f(n-k)}{n}=1+\frac{\sum_{k=1}^n f(n-k)}{n}$$
Now, let's try to relate this to $f(n-1)$:
$$f(n-1)=1+\frac{\sum_{k=1}^{n-1} f(n-1-k)}{n-1}=1+\frac{\sum_{k=2}^{n} f(n-k)}{n-1}$$
Now, if we subtract $1$ from both sides here, we can then multiply by $\frac{n-1}{n}$ to get the denominator of the fraction on the right-hand side to be $n$ like it is in the equation for $f(n)$:
$$\frac{n-1}{n}f(n-1)-\frac{n-1}{n}=\frac{\sum_{k=2}^{n} f(n-k)}{n}$$
Now, if we add by $\frac{f(n-1)}{n}$, we will get the sum to start at $k=1$ like it is in the equation for $f(n)$.
$$f(n-1)-\frac{n-1}{n}=\frac{\sum_{k=1}^{n} f(n-k)}{n}$$
Now, add both sides by $1$ to get it exactly like the equation for $f(n)$:
$$f(n-1)+\frac 1 n=1+\frac{\sum_{k=1}^{n} f(n-k)}{n}=f(n)$$
Thus, we are simply adding $\frac 1 n$ from $f(n-1)$ to get to $f(n)$, so we get:
$$f(n)=\sum_{k=1}^n \frac{1}{n}$$
