Krdytkyu

Let $0 < k leq n$ and $k$ is an integer. Then prove that :
$$2 cdot (n)! geq (n-k)! n^{k-1} (2n+k-k^2)$$

The main problem I found in trying to prove this inequality is the term : $2n+k-k^2$. It’s hard to really have a good bound on this polynomial that will help solving this inequality.

We can notice that we only need to look at the $k$ for which : $2n+k-k^2 > 0$. Yet trying to compute the determinant in order to find the root of the polynomial is a bit cumbersome.

Moreover it’s quite hard to have an analytic way of proving this since taking derivative is impossible here.
Maybe there is some convexity argument but I didn’t figure anything.

It's equivalent to demonstrating :
$$2prod_{m=0}^{k-1}(1-frac{m}{n})geqfrac{2n+k-k^2}{n}$$
By induction, you may prove the following inequality :
$$prod_{i=1}^{n}(1-alpha_{i})geq 1-sum_{i=1}^{n}alpha_{i}$$
where $alpha_{i}$ are positive. #in fact, we need $α_i∈[0,1]$. Thanks for the comment of "Thinking" below#

Applying this inequality, we obtain
$$2prod_{m=0}^{k-1}(1-frac{m}{n})geq 2(1-sum_{m=0}^{k-1}frac{m}{n}) = frac{2n+k-k^2}{n}$$.

Here is a probabilistic way of proving the inequality.

As @曾靖國 noticed we have :

$$2 left ( 1 - sum_{m=0}^{k-1} frac{m}{n} right) = frac{2n+k-k^2}{n}$$

and thus the inequality we want to prove can be rewritten as :

$$2 prod_{m = 0}^{k-1} left ( 1- frac{m}{n} right ) geq 2 left ( 1 - sum_{m=0}^{k-1} frac{m}{n} right) $$

Now let's consider indepent events : $A_0, ..., A_{k-1}$ and a probability $mathbb{P}$ such that :
$$mathbb{P} left ( A_i right) = frac{i}{n}$$

Hence we have (since the $bar{A_i}$ are independent) :

$$mathbb{P} left ( bigcap_{i = 0}^{k-1} bar{A_i} right) = prod_{m = 0}^{k-1} left ( 1- frac{m}{n} right )$$

Thus :

$$mathbb{P} left ( overline{bigcap_{i = 0}^{k-1} bar{A_i}} right) = mathbb{P} left ( bigcup_{ i = 0}^{k-1} A_i right) leq sum_{i = 0}^{k-1} mathbb{P} left ( A_i right ) = sum_{m = 0}^{k-1} frac{m}{n} $$

Since :

$$mathbb{P} left ( overline{bigcap_{i = 0}^{k-1} bar{A_i}} right) = 1 - mathbb{P} left ( bigcap_{i = 0}^{k-1} bar{A_i} right)$$

We have the desired inequality :

$$2 prod_{m = 0}^{k-1} left ( 1- frac{m}{n} right ) geq 2 left ( 1 - sum_{m=0}^{k-1} frac{m}{n} right) $$

Using the same probabilistic argument (or simply using induction as suggest by @曾靖國) , we can prove more generally that if : $alpha_i in [0,1]$ then :

$$prod_{i = 1}^n left (1-alpha_i right ) geq 1 - sum_{i = 1}^n alpha_i$$

$$
begin{align}
frac{n!}{(n-k)!,n^k}
&=prod_{j=0}^{k-1}left(1-frac jnright)^{-1}\
&geprod_{j=0}^{k-1}left(1+frac jnright)\
&ge1+sum_{j=0}^{k-1}frac jn\
&=1+frac{k^2-k}{2n}
end{align}
$$
Thus, the inequality in the question should probably be the stronger
$$
2n! geq (n-k)! n^{k-1} (2n-k+k^2)
$$