Double sum involving binomial coefficients, relating to number of record lows Is there any way to simplify the following expression?
$$
\sum_{d = 1}^k \left(\sum_{i=1}^d \frac{1}{i}\right) \frac{{n-t \choose d}{t \choose k-d}}{{n \choose k}}
$$
This formula comes from the expected number of record lows over the first $k$ elements in a permutation of $[1,n]$, given some minimum threshold $t$ below which the elements don't count as a record low. 
Let $L$ be the number of record lows, and let $d$ be the number of elements above the threshold.
$$
E[L] = E[E[L|d]] = \sum_{d=1}^k E[L|d]\cdot P(d)
$$
where $P(d)$ is a hypergeometric distribution, with n-t success states, population size $n$, and $k$ draws.
This comes up for example in this question: Expected number of cards in the stack?
 A: I'm not sure whether this is the sort of simplification you're looking for, but you can determine the same expected number directly. The $j$-th element has probability
$$\frac1n\binom{n-1}{j-1}^{-1}\sum_{m=1}^d\binom{n-m}{j-1}$$
of being a record low, so the expected number is
$$\frac1n\sum_{j=1}^k\binom{n-1}{j-1}^{-1}\sum_{m=1}^d\binom{n-m}{j-1}\;.$$
Wolfram|Alpha gives a closed form for the inner sum:
$$\sum_{m=1}^d\binom{n-m}{j-1}=\frac1j\left(n\binom{n-1}{j-1}-(n-d)\binom{n-d-1}{j-1}\right)\;.$$
The first term gives the usual expected number of record lows for the case without a threshold, and the second term gives a correction:
$$\sum_{j=1}^k\frac1j-\left(1-\frac dn\right)\sum_{j=1}^k\frac{\binom{n-d-1}{j-1}}{j\binom{n-1}{j-1}}\;.$$
Note that the cases $d=0$ and $d=n$ come out right. Wolfram|Alpha also gives a "closed form" for the correction term, but it seems unlikely to help.
P.S.: I just noticed that the result can actually be considerably simplified. With the number $s=n-d$ of values below the threshold, we have
$$\sum_{j=1}^k\frac1j-\frac sn\sum_{j=1}^k\frac1j\frac{\binom{s-1}{j-1}}{\binom{n-1}{j-1}}=\sum_{j=1}^k\frac1j-\sum_{j=1}^k\frac1j\frac{\binom sj}{\binom nj}\;.$$
That should make us wonder whether there isn't a simpler way to derive that result.
A: Forget about my other answer; this is actually much simpler than that. Think of the elements below the threshold as above a threshold above all other elements instead. The crucial thing to notice is that the events "the $j$-th element is the lowest of the first $j$ elements" and "at least one of the first $j$ elements is below the threshold" are independent. The event "the $j$-th element is a record low" is simply the intersection of these events, so its probability is their product, $1/j$ times $1-{s\choose j}/{n\choose j}$, and the expected number of record lows is just the sum of these probabilities:
$$\sum_{j=1}^k\frac1j\left(1-\frac{s\choose j}{n\choose j}\right)\;.$$
Simplifying Wolfram|Alpha's take on this leads to the "closed form"
$$H_k+\psi(s-n)-\psi(-n)+\frac{\binom s{k+1}\,_3F_2(1,k+1,k-s+1;k+2,k-n+1;1)}{(k+1)\binom n{k+1}}\;,$$
where $H_k$ is the $k$-th harmonic number, $\psi$ is the digamma function and $F$ is the generalized hypergeometric function.
