I would like to approximate the following when $n \gg k$.
$\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$
The formula can be re-written as
$\sum_{y = k + 1}^n \frac{(y - 1) + \sum_{m = 1}^{k - 1} {y - 1 \choose m + 1} (m + 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$
However since the partial sum of binomial coefficient does not closed form, I could not see any way to further simplify the formula. Any help is much appreciated. Thanks!
First, we can reindex using $j=y-1$ to simplify:
$$ \sum_{j=k}^{n-1}\frac{\sum_{m=0}^{k-1}\binom{j-1}mj}{\sum_{m=0}^k\binom jm}\;. $$
For $n\gg k$, most terms have $j\gg k\ge m$, so we can approximate the sums by their largest terms and $\binom jm$ by $j^m/m!$, yielding
\begin{align} \sum_{j=k}^{n-1}\frac{j(j-1)^{k-1}/(k-1)!}{j^k/k!} &= k\sum_{j=k}^{n-1}\left(1-\frac1j\right)^{k-1} \\ &\approx k\int_k^{n-1}\left(1-\frac{k-1}x\right)\mathrm dx \\ &\approx kn-k(k-1)\log n \;. \end{align}
This is of course just a rough estimate without any error analysis.