$2n! \geq (n-k)! n^{k-1} (2n+k-k^2)$

Question

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.

Answer 1

It's equivalent to demonstrating : $$2\prod_{m=0}^{k-1}(1-\frac{m}{n})\geq\frac{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 $$2\prod_{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}$$.

Answer 2

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$$

Answer 3

$$ \begin{align} \frac{n!}{(n-k)!\,n^k} &=\prod_{j=0}^{k-1}\left(1-\frac jn\right)^{-1}\\ &\ge\prod_{j=0}^{k-1}\left(1+\frac jn\right)\\ &\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) $$

Answer 4

I may present another way to solve the problem, using Combinatorial argument and Induction.

The inequality can be written as:

$$ (n)(n-1)(n-2)…(n-(k-1)) \ge n^{k} - \frac{(k)(k-1)}{2} n^{k-1} $$

And let $f_{k} = (n)(n-1)(n-2)…(n-(k-1))$. Now if $n < \frac{(k)(k-1)}{2}$, then the right hand side is negative and proof is done.

If $n \ge \frac{k(k-1)}{2}$: we will use induction on $k$ to prove it.

Starting at $k=0,1,2$, it is clear the inequality is true. Now for $2 \le k = m \le n$, assume that the inequality is true

$$ f_{m} = (n)(n-1)(n-2)…(n-(m-1)) \ge n^{m} - \frac{(m)(m-1)}{2} n^{m-1} $$

and we wish to prove for $k=m+1 \le n$:

$$ (n)(n-1)(n-2)…(n-(m)) \ge n^{m+1} - \frac{(m+1)(m)}{2} n^{m} $$

Now, if wee see the terms as counting problem: we notice that $f_{m}$ is the same as the number of arrangements of $n$ different objects in $m$ positions. And notice that $n^{m}$ is the same thing but with repetition allowed. We also know that:

$$ f_{m} = n^{m} - \alpha_{m} $$

where $\alpha_{m}$ is the number of ways there is at least one repetition in the arrangement. So to prove the inequality is the same as proving $$ \alpha_{m+1} \le \frac{(m+1)(m)}{2} n^{m}$$

knowing already that $ \alpha_{m} \le \frac{(m)(m-1)}{2} n^{m-1}$.

Now, since $\alpha_{m+1}$ is the number of arrangements where at least one repetition appears, we can use the result of $\alpha_{m}$ with one position left to be filled with $n$ choices,... plus $f_{m}$. So it must be $\alpha_{m+1} = n \alpha_{m} + f_{m} = (n-1)\alpha_{m} + n^{m} $. Thus

$$ \alpha_{m+1} \le (n-1)\frac{(m)(m-1)}{2} n^{m-1} + n^{m} = \frac{(m)(m-1)}{2} n^{m} + n^{m} - \frac{(m)(m-1)}{2} n^{m-1} = \frac{(m^{2}-m + 2}{2} n^{m} - \frac{(m)(m-1)}{2} n^{m-1} \le \frac{(m^{2}-m + 2}{2} n^{m} \le \frac{(m^{2}+m)}{2} n^{m} $$