Can you prove this inequality involving factorials and powers?

[jostpuur]

Here's a nice problem: Prove that

$$\frac{k!}{k^k} \leq \frac{(k-j)!}{(k-j)^{k-j}} \frac{j!}{j^j}$$

for all natural numbers such that $0\leq j\leq k$. (Convention: $0^0=1$.)

I proved this myself, so I'm not asking for help any more. I merely decided to mention this problem to those of you who seek challenges

This claim seems to be so strong, that it cannot be proven with Stirling approximation. It will only tell you that the both sides of the inequality are roughly the same. You need to do some work before getting the precise result.

 

[Hurkyl]

Moderator's note: Off-topic discussion on $0^0$ moved here

 

[micromass]

OK, take k fixed. We can assume k>0, since the case k=0 is trivial.

The idea is to show that the minima of the integer function

$$\frac{(k-j)!j!}{(k-j)^{k-j}j^j}$$

occur at j=0 and j=k. In these two values, the inequality is easily seen to be true.

So, to prove that the minima occur at j=0 and j=k. I will show that the function is first increasing until a certain j₀ and then decreasing, this will apply the assertion. Note that

$$\frac{(k-j)!j!}{(k-j)^{k-j}j^j} \leq \frac{(k-j-1)!(j+1)!}{(k-j-1)^{k-j-1}(j+1)^{j+1}}$$

is equivalent to

$$\left(\frac{k-j-1}{k-j}\right)^{k-j-1}\left(\frac{j+1}{j}\right)^j\leq 1$$

and equivalently with the other inequality. So to show that the function is first increasing until j₀ and then decreasing, it suffices to show that the function

$$\left(\frac{k-x-1}{k-x}\right)^{k-x-1}\left(\frac{x+1}{x}\right)^x$$

is increasing. Our j₀ corresponds to the point when above equation is 1.

Now, we can take logarithms of the above function, since if the above function is increasing, so will the log of the function (note: log denotes the natural logarithm here). So, we need to show that

$$(k-x-1)\log(k-x-1)-(k-x-1)\log(k-x)+x\log(x+1)-x\log(x)$$

is increasing. Taking derivatives yields

$$\log(\frac{k+x(k-x-1)}{x(k-x-1)})+\frac{x(k-x-1)-1}{k+x(k-x-1)}-1$$

So we need to show that this is positive for x>0. Changing variables y=x(k-x-1) gives us that we need to show that

$$\log(\frac{k+y}{y})+\frac{y-1}{k+y}\geq 1$$

To show this, we prove that the function is monotonically decreasing if y>0 and that the limit of this function tends to 1.

Take the derivative of the function, this yields

$$\frac{k-1}{(k+y)^2}+\frac{1}{k+y}-\frac{1}{y}$$

this is smaller than 0 if and only if

$$y\leq (k+y)^2$$

this is certainly true since $k\geq 1$.

So, the function is decreasing. It suffices to calculate the limit

$$\begin{eqnarray*} \lim_{y\rightarrow +\infty}{\log(\frac{k+y}{y})+\frac{y-1}{k+y}} & = & \lim_{y\rightarrow +\infty}{\log(\frac{k+y}{y})}+\lim_{y\rightarrow +\infty}{\frac{y-1}{k+y}}\\ & = & 0+1\\ & = & 1\\ \end{eqnarray*}$$

this proves that the function is greater than 1. This completes the proof.

 

[jostpuur]

I think that the reason why this problem turns out to be difficult usually, is that the first idea is that one must fix arbitrary $k$, and then prove the relation for all $0\leq j\leq k$, and then, the only idea that comes to the mind is induction step $j\mapsto j+1$, since the case $j=0$ is clear. But it turns out that the induction step is extremely difficult.

I see micromass solved the problem by understanding, that you must do something else than the induction step $j\mapsto j+1$.

My own solution was different. It is that we first fix arbitrary $j$, then check the relation for $j=k$, and then carry out induction step $k\mapsto k+1$. It turns out that in this direction the induction step is quite possible.

Here's some details from intermediate steps:

We want to prove

$$\frac{j^j}{j!} \leq \frac{(k-j)!}{(k-j)^{k-j}} \frac{k^k}{k!}$$

for all $j\leq k$. In order to succeed in the induction step with respect to $k$, we should prove

$$\frac{(k-j)!}{(k-j)^{k-j}} \frac{k^k}{k!} \leq \frac{(k+1-j)!}{(k+1-j)^{k+1-j}} \frac{(k+1)^{k+1}}{(k+1)!}$$

If you do some algebra, this inequality turns out to be equivalent with

$$\Big(1 + \frac{1}{k-j}\Big)^{k-j} \leq \Big(1 + \frac{1}{k}\Big)^{k}$$

So the remaining task is to prove that

$$x\mapsto \Big(1 + \frac{1}{x}\Big)^x$$

is monotonically increasing for $x>0$, which can be accomplished by calculating some derivatives.

 

[micromass]

I found this problem quite entertaining, actually. I'm going to give it to my students next year as a challenge!

I see that you solved the problem by induction on k, that's quite nice. I've considered it, but for some (bad) reason I decided against it.

Thank you for letting me practise some fun calculus

 

[Hurkyl]

This claim seems to be so strong, that it cannot be proven with Stirling approximation.

If I've computed correctly, a proof for $0 < j < k$ by Stirling's approximation boils down to showing
$$1 \leq \sqrt{2 \pi \frac{j (k-j)}{k}} \exp\left( \frac{1}{12j+1} + \frac{1}{12(k-j)+1} - \frac{1}{12k} \right)$$

The exponential is clearly bigger than 1. and j(k-j)/k > 1 whenever 1 < j < k-1 for... k > 2, I think? And 1 * (k-1) / k > 1/(2 pi). So that's all the pieces.

 

[micromass]

Nice, I like it that there are already 3 different methods to solve this same problem.

Let me post a harder challenge: prove that for all x,y (with some silly conditions on x and y) holds that

$$\frac{\Gamma(x+1)}{x^x}\leq\frac{\Gamma(x-y+1)}{(x-y+1)^{x-y}}\frac{\Gamma(y+1)}{y^y}$$

I guess Hurkyl's method with Stirling approximation will still do here. But I think it becomes quite difficult to prove this without Stirling...

 

[Hurkyl]

I guess Hurkyl's method with Stirling approximation will still do here. But I think it becomes quite difficult to prove this without Stirling...

Certainly not so easily; I had to make good use of j and k-j were integers integer to keep them far enough away from zero.

 

[dimitri151]

.So the remaining task is to prove that

$$x\mapsto \Big(1 + \frac{1}{x}\Big)^x$$

is monotonically increasing for $x>0$, which can be accomplished by calculating some derivatives.

I think you can also prove monotonicity by expanding the binomial, so for $x_2>x_1$term for term (except the first two) $\Big(1 + \frac{1}{x_1}\Big)^{x_1} <\Big(1 + \frac{1}{x_2}\Big)^{x_2}$. So you can do this problem without calculus (but you need induction to prove the binomial theorem so you can't do it without induction).

 

[JSuarez]

A purely combinatorial proof:

The cases k = 0 or k = 1 are immediate, so let $k \ge 2, 2 \leq j \leq k$, $A$ a k-element set, $C \subseteq A$ a j-subset of A, $A\left(k\right)$ the set of all length k sequences over $A$ and $B\left(k\right)$ the set of length k binary sequences.

Take any elements $a \in A \setminus C$ and $c \in C$ and define a mapping between $A\left(k\right)$ and $B\left(k\right)$ as follows: for each $s \in A\left(k\right)$, substitute each element of s belonging to $A\setminus C$ for 0 and each belonging to $C$ for 1; the result is a sequence in B(k).

Now, if we consider the subset of B(k) consisting of binary sequences with exactly j 1's, its preimage is the set of A-sequences in A(k) that have exactly j occurrences, possibly repeated, of C-elements and its number is given by:

$$\frac{\left|A\left(k\right)\right|}{\left|C\left(j\right)\right|\left|A\setminus C\left(k-j\right)\right|}=\frac{k^k}{j^j \left(k-j\right)^{k-j}}$$

As this is a many-to-one mapping, we have:

$$\frac{k^k}{j^j \left(k-j\right)^{k-j}} \geq \frac{k!}{j! \left(k-j\right)!}$$

Which is the original inequality.

PS: regarding the branched-off thread, I just want to remark that in the case k = 0 the combinatorial statement $0^0=1$ just asserts that the set of functions taking the empty set to itself has just one member; so, at least in this context, it's definitely not conventional.

 

[Yuqing]

Perhaps I'm missing something, but how do you get $$\frac{k^k}{j^j(k-j)^{k-j}}$$ as the pre-image? That fraction is not an integer in most cases. Shouldn't the pre-image be something like $$\frac{k!}{j!(k-j)!}j^j(k-j)^{k-j}$$

 

[JSuarez]

Ups! Got a bit carried away, haven't I?

You're right: the number of elements in the preimage is given by:

$$\frac{k!}{j!(k-j)!}j^j(k-j)^{k-j}$$

But, as the preimage is a subset of A(k), who has k^k elements, we have:

$$k^k \geq \frac{k!}{j!(k-j)!}j^j(k-j)^{k-j}$$

Which is, again, the sought inequality.