Show that the falling factorial $(n)_k=\dfrac{n!}{(n-k)!}$ satisfies the following inequality: $$(n)_k\le n^ke^{\frac{-k(k-1)}{2n}}$$

I rewrote the inequality as $\left(1+\frac{1}{n-1}\right)\left(1+\frac{2}{n-2}\right)\ldots\left(1+\frac{k-1}{n-(k-1)}\right)\ge e^{\frac{k(k-1)}{2n}}$.

Then I tried to apply directly the inequality $1+x\ge e^{x-\frac{x^2}{2}}$, for $x\ge 0$.

Then it suffices to show $\displaystyle \sum^{k-1}_{i=1} \left(\frac{i}{n-i}-\frac{i}{n}-\frac{i^2}{2(n-i)^2}\right)\ge 0\iff \sum^{k-1}_{i=1} \left(\frac{i^2}{n(n-i)}-\frac{i^2}{2(n-i)^2}\right)\ge 0$

However this is only good enough for $k<\frac{n}{2}$. Any way from here?


An inequality $1+x\le\exp(x)$ which holds for all real $x$ implies the following chain

$$\frac {(n)_k}{n^k}=\prod_{i=0}^{k-1} \left (1-\frac{i}{n}\right) \le \prod_{i=0}^{k-1} \exp\left (-\frac{i}{n}\right)= \exp\left(\sum_{i=0}^{k-1}-\frac{i}{n}\right)= \exp\left(-\frac{(k-1)k}{2n}\right). $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.