Lower bound for falling factorial

Question

Show that the falling factorial $(n)_k=\dfrac{n!}{(n-k)!}$ satisfies the following inequality: $$(n)_k\ge \frac{\sqrt{2\pi}}{e} n^ke^{\frac{-k^2}{2(n-k)}}$$ I am also given the hint to use the inequality: $\sqrt{2\pi m}\left(\dfrac{m}{e}\right)^m\le m! \le e\sqrt{m}\left(\dfrac{m}{e}\right)^m$

I first applied the inequalities for $m=n$ and $m=n-k$ to get a lower bound for the LHS. Then after cancelling everything and applying the the inequality $1+x\ge e^{x-\frac{x^2}{2}}$, for $x\ge 0$, in the case where $1+x=\dfrac{n}{n-k}$, then I am done for all $k<\frac{2n}{3}$. What can I do next?

Answer 1

It follows fairly simply from the fact that $e^x\ge1+x$ for all $x$ that $$ \log(1-x)\ge-\frac x{1-x}\tag{1} $$ for $x\lt1$.

Therefore, $$ \begin{align} \log\left(\frac{n!}{(n-k)!}\right) &=\sum_{j=0}^{k-1}\log(n-j)\tag{2}\\ &=k\log(n)+\sum_{j=0}^{k-1}\log\left(1-\frac jn\right)\tag{3}\\ &\ge k\log(n)-\sum_{j=0}^{k-1}\frac{j}{n-j}\tag{4}\\ &\ge k\log(n)-\sum_{j=0}^{k-1}\frac{j}{n-k}\tag{5}\\ &=k\log(n)-\frac{k^2-k}{2(n-k)}\tag{6}\\ &\ge k\log(n)-\frac{k^2}{2(n-k)}\tag{7} \end{align} $$ Explanation:
$(2)$: the log of a product is the sum of the logs
$(3)$: pull $\log(n)$ out of the sum
$(4)$: apply $(1)$
$(5)$: $j\lt k$ for all terms of the sum
$(6)$: sum of consecutive integers
$(7)$: $k\ge0$

Inequality $(7)$ says $$ \bbox[5px,border:2px solid #C0A000]{\frac{n!}{(n-k)!}\ge n^ke^{-\frac{k^2}{2(n-k)}}}\tag{8} $$ which is stronger than the desired inequality since $\frac{\sqrt{2\pi}}e\lt1$.

---

Skipping step $(7)$ above (which only weakens the inequality), we get a tighter lower bound. Then using $\log(1-x)\lt-x$ to get an upper bound, we have $$ n^ke^{-\frac{k^2-k}{2(n-k)}}\le\frac{n!}{(n-k)!}\le n^ke^{-\frac{k^2-k}{2n}}\tag{9} $$

Answer 2

Assuming you have solved the case for $k<2n/3$, here is a proof for the case $k\geq 2n/3$. Assume that $k,n>0$ and that $k\geq 2n/3$.

Using the hint, we get $n!\geq (n/e)^n\sqrt{2\pi n}$ and $(n-k)!\leq e\sqrt{n-k}\left(\frac{n-k}{e}\right)^{n-k}$. Thus, $\frac{n!}{(n-k)!}\geq \frac{(n/e)^n \sqrt{2\pi n}}{e\sqrt{n-k}\left(\frac{n-k}{e}\right)^{n-k}}=\frac{n^n}{(n-k)^{n-k}}\sqrt{2\pi n/(n-k)}\cdot\frac{1}{e^{k+1}}\geq \frac{n^n}{n^{n-k}}\sqrt{2\pi (n-k)/(n-k)}\cdot\frac{1}{e^{k+1}}=\frac{\sqrt{2\pi}}{e}n^k e^{-k}$. Now the question is: Is $\exp(-k)\geq \exp\left(-\frac{k^2}{2(n-k)}\right)$ for $k\geq 2n/3$, i.e. is $\exp(k)\leq \exp\left(\frac{k^2}{2(n-k)}\right)$ for $k\geq 2n/3$? Yes, this is true: the previous inequality holds iff $k\leq \frac{k^2}{2(n-k)}$ since $\exp(x)$ is increasing, i.e. iff $1\leq \frac{k}{2(n-k)}$ i.e. iff $2n\leq 3k$ i.e. it holds iff $k\geq 2n/3$.