$\binom{n}{k}$ for $n>k^{100}$

Question

This paper I'm reading says this

"We used the fact that $4k^2n^{k-1}<4(k+1)!\binom{n-1}{k-1}$ for $n>k^{100}$." The only condition here is that $k\geq3$ and $n$ can be sufficiently large. However, this seems incorrect to me.

Answer 1

Note that $$\begin{align}\frac{(k-1)!{n-1\choose k-1}}{n^{k-1}} &=\frac{(n-1)!}{n^{k-1}(n-k)!}\\ &>\frac{(n-k+1)^{k-1}}{n^{k-1}}\\ &=\left(1-\frac{k-1}{n}\right)^{k-1}\\ &>1-\frac{(k-1)^2}n \end{align}$$(where we first use that $\frac{(n-1)!}{(n-k)!}$ consists of $k-1$ factors $\ge n-k+1$ and in the last step use Bernoulli's inequality). As we are given that $k\ge 1$ and $n\ge k^3$, we have $$ n\ge k^3>(k^2-1)(k-1)=(k+1)(k-1)^2,$$ so that $$ 1-\frac{(k-1)^2}n>1-\frac1{k+1}$$ and ultimately $$\begin{align}4(k+1)!{n-1\choose k-1}&=4(k+1)k\cdot \frac{(k-1)!{n-1\choose k-1}}{n^{k-1}}\cdot n^{k-1}\\&>4(k+1)k\left(1-\frac1{k+1}\right)n^{k-1}\\&=4k^2 n^{k-1}.\end{align}$$