Sampling without replacement until hitting a subset I randomly sample uniformly from $ \{1,..,N \}$ without replacement until drawing a number  $ \leq k$. Denote the expected number of draws by $R(N,k)$. I want a good approximation for $\sum_{k=1}^N R(N,k)$.
I'm guessing this is a well known distribution, but I don't know how to search for it.
Update: 
The motivation is the following story. There are $N$ people, and $N$ items. Each person has a randomly uniformly drawn preference order over the $N$ items. The first person gets his favorite item, the second gets his favorite item out of what's left after the first person took his item, and so on, the $k$-th person gets his favorite item out of what's left after $1,..,k-1$ took theirs. So $R(N,N-k)-1$ is the expected number of items that person $k$ wanted but were already gone. 
Thanks!
 A: Here's a small alternative to Robert Israel's derivation of $R(N,k) = (N+1)/(k+1)$.  On your first draw, you'll either be done, with probability $k/N$, or you'll continue with $N-1$ elements, with probability $(N-k)/N$.  Hence
$$R(N,k) = {k\over N} 1 + {N-k\over N} (1+R(N-1,k)) = 1 + {N-k\over N}R(N-1,k)$$
(I suppose I could have skipped over the middle step:  you definitely draw once, and you may have to keep drawing.)  If, inductively, $R(N-1,k) = N/(k+1)$, then
$$R(N,k) = 1+{N-k\over N}{N\over k+1} = {N+1\over k+1}$$
follows.  (I'm omitting some of the niceties of a proper proof by induction, but I don't think I'm skipping anything essential or skating on any thin ice.)
A: The probability that it will take at least $m+1$ draws, i.e. that the first $m$ results are all numbers $> k$, is ${{N-k} \choose {m}}/{N \choose {m}}$ for $0 \le m \le N-k$.
So 
$$R(N,k) = \sum_{m=0}^{N-k} \dfrac{{{N-k} \choose m}}{N \choose m} = \frac{N+1}{k+1}$$ 
So you want
$$\eqalign{\sum_{k=1}^N \frac{N+1}{k+1} &= (N+1)(\Psi(N+2)-1+\gamma)\cr
&=  \left( \ln  \left( N \right) -1+\gamma \right) N+\ln  \left( N
 \right) +\frac12+\gamma+{\frac {5}{12N}}-\frac{1}{12 N^2}+{\frac {1}{
120 N^3}}+{\frac {1}{120 N^4}}+O \left( \frac{1}{N^5} \right)\cr}$$
