I am interested in checking how small $k$ should be with respect to $n$, so that the following inequality holds (asymptotically).
$\binom{n-1}{k-1} \Big(\binom{n-1}{k-1}(1-k) + \binom{n-k-1}{k-1}k +1 - 2k\Big) + \binom{n-k-1}{k-1}\cdot (k-2) - k \geqslant 0$.
I tried to express $\binom{n-k-1}{k-1}$ as $\binom{n-1}{k-1}\cdot \prod_{i=1}^{k} (1-\frac{k}{n-i})$ and use the inequality
$(1-\frac{k}{n-k+1})^{k-1}\geqslant \prod_{i=1}^{k-1}( 1-\frac{k}{n-i}) \geqslant 1 - \sum_{i=1}^{k-1} \frac{k}{n-i}$
to bound it somehow, but unfortunately things get messy. How to obtain a condition of the form that $k$ should be of order $O(f(n))$?