Dorin Marghidanu's Spanish Problem

Source

Dorin  Marghidanu's Spanish Problem, source

Problem

I'd like but am unable to follow on the beautiful original notations and, thus, forced to use a different kind of disambiguation:

For integer $n\gt 0,$ define

$\displaystyle n^*=1^1\cdot 2^2\cdot 3^3\cdot\ldots\cdot (n-1)^{n-1}\cdot n^n,\,$ and
$\displaystyle n_*=1^n\cdot 2^{n-1}\cdot 3^{n-2}\cdot\ldots\cdot (n-1)^2\cdot n^1.$

Prove that $\displaystyle n^*\le (n_*)^2.$

Solution 1

Let's remark that if $n\ge 2,\,$ then $n^*=(n-1)^*\cdot n^n\,$ while $(n_*)^2=((n-1)_*)^2\cdot (n!)^2.\,$ This suggests mathematical induction.

We assume that $((n-1)_*)^2\ge (n-1)^*\,$ is true and derive that $((n-1)_*)^2\cdot (n!)^2\ge (n-1)^*\cdot n^n\,$ is also true.

Suffice it to show that $(n!)^2\ge n^n,\,$ for $n\ge 2.\,$ Consider the sequence $\displaystyle z_n=\frac{(n!)^2}{n^n},\,$ $n\ge 2.\,$ We have $\displaystyle \frac{z_{n+1}}{z_n}=(n+1)\left(\frac{n}{n+1}\right)^n.\,$ But

$\displaystyle \begin{align} \left(\frac{n}{n+1}\right)^n\gt \frac{1}{e}&\Rightarrow\,(n+1)\left(\frac{n}{n+1}\right)^n\gt \frac{n+1}{e}\ge\frac{3}{e}\gt 1\\ &\Rightarrow\,z_{n+1}\gt z_{n}\\ &\Rightarrow\,z_{n}\ge z_{2}=1\\ &\Rightarrow\,(n!)^2\ge n^n, \end{align}$

for $n\ge 2.$ That's it.

Solution 2

For $k,n\in\mathbb{N}^*,\,$ $1\le k\le n,\,$ we have $(n-k)(k-1)\ge 0,\,$ or, equivalently,

(1)

$k\cdot(n-k+1)\ge n.$

Multiplying up, $\displaystyle \prod_{k=1}^n[k\cdot(n-k+1)]\ge n^n,\,$ in other words,

(2)

$(n!)^2\ge n^n$

Multiplying up, $\displaystyle \prod_{n=1}^N(n!)^2\ge \prod_{n=1}^Nn^n,\,$ in other words, $\displaystyle \left(\prod_{n=1}^Nn!\right)^2\ge \prod_{n=1}^Nn^n,\,$ i.e., $(N_*)^2\ge N^*.$

Equality holds only for $N=1.$

Solution 3

Let's define $\displaystyle f(n):=\prod_{i=1}^ni^i,\,$ $\displaystyle f_2(n):=\left(\prod_{i=1}^ni^(-i+n+1)\right)^2,\,$ and observe that $\displaystyle \log f(n)=\sum_{i=1}^n i\log(i)\,$ and $\displaystyle \log f_2(n)=\sum_{i=1}^n 2(-i+n+1)\log(i).$

1 - Calculus intuition

We prove that for large enough values of $n:\,$

$\displaystyle \int_0^n(n-x)\log(x)dx\ge\int_0^nx\log(x)dx,$

since both $\log f(n)\,$ and $\log f_2(n)\,$ calculated for discrete $n\,$ minus their integral approximation is of order $O(n\log(n)),\,$ dwarfed by both factorials.

$n^2(2\log(n)-5)\ge 0,\,$ which holds for all values of $n\ge e^{5/2}\approx 12.18.$

For smaller values, we can easily check manually.

2 - Using special functions

This part is just out of love for engineering functions.

$f\,$ is the hyperfactorial function; for $n\,$ large we have

$\displaystyle f\asymp Ae^{-\frac{n^2}{4}}n^{\frac{1}{12}(6n^2+6n+1)}\,$ (see wikipedia)

As approximations for $f\,$ and $f_2,$

$\displaystyle \begin{align} f&=e^{-\zeta^{(1,0)}(-1,n+1)-\zeta'(-1)}\\ f_2&=\frac{\displaystyle \Gamma(n+1)^{2n+2}e^{\frac{1}{6}-2\zeta^{(1,0)}(-1,n+1)}}{\displaystyle A^2}, \end{align}$

where $A\,$ is the Glaisher constant. Below are the MathWorld entry abd the simpler Wikipedia one:

MathWorld

Taleb's reference to MathWorld

wikipedia

Taleb's reference to wikipedia

Solution 4

Taking the logarithm of both sides the inequality becomes

$\displaystyle \sum\limits_{k=1}^{n}k\log (k)\leq \sum\limits_{k=1}^{n}(2n-2k+2)\log (k)$

that can be written as

$\displaystyle \sum\limits_{k=1}^{n}(2n-3k+2)\log (k)\geq 0.$

Setting

$\displaystyle f(n):=\sum\limits_{k=1}^{n}(2n-3k+2)\log (k)$

we have that $f(1)=0;$ now we prove that $f$ is increasing. We have that

$\displaystyle \begin{align}f(n+1)-f(n) &= \sum\limits_{k=1}^{n+1}(2n+2-3k+2)\log (k)-\sum\limits_{k=1}^{n}(2n-3k+2)\log (k) \\ &= \sum\limits_{k=1}^{n}(2n+2-3k+2)\log (k)\\ &\qquad\qquad-(n-1)\log(n+1)-\sum\limits_{k=1}^{n}(2n-3k+2)\log (k) \\ &= 2\sum\limits_{k=1}^{n}\log (k)-(n-1)\log (n+1) \end{align}$

and so it is enough to show that

$\displaystyle \sum\limits_{k=1}^{n}\log (k)\geq \frac{n-1}{2}\log (n+1)$

that can be transformed with a simple calculation as

$\displaystyle 2\sum\limits_{k=1}^{n+1}\log (k)\geq (n+1)\log (n+1)$

and coming back to the exponentials

$\displaystyle \lbrack (n+1)!]^{2}\geq (n+1)^{n+1}.$

The last one is a very well known inequality but we will prove it for sake of completeness. Note that we can rewrite the LHS as

$\displaystyle \prod\limits_{k=1}^{n+1}k(n-k+2)$

and now simply note that

$\displaystyle k(n-k+2)\geq n+1\text{ for every }k=1,2,\ldots n$

because

$\displaystyle k(n-k+2)-n+1=\left( k-1\right) \left( n+1-k\right)$

and both factors are greater than or equal to $0$.

Acknowledgment

This problem has been kindly posted at the CutTheKnotMath facebook page by Dorin Marghidanu. Solution 1 is by Leo Giugiuc; Solution 2 is Dorin Marghidanu; Solution 3 is by N. N. Taleb; Solution 4 is by Giulio Francot.

 

|Contact| |Up| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71470997