An Inequality with Factorial


inequality with factorial

Solution 1

Define an affine function $f:\;[0,n]\rightarrow\mathbb{R}\,$ as

$f(x)=a_1\cdot a_2\cdot\ldots\cdot a_{n-1}\cdot x+(1-a_1)\cdot (2-a_2)\cdot\ldots\cdot ((n-1)-a_{n-1})(n-x).$

Since an affine function is either increasing or decreasing (or both), we deduce that $\displaystyle\max_{x\in [0,n]} f(x)\in\{f(0),f(n)\}.\,$ But $f(0)=1-a_1)\cdot (2-a_2)\cdot\ldots\cdot ((n-1)-a_{n-1})n\le n!\;$ and $f(n)=a_1\cdot a_2\cdot\ldots\cdot a_{n-1}\cdot n\le n!\,$ It follows that, on $[0,n],$ $f(x)\le n!\;$ In particular, this is true for any $a_n\in [0,n].$

The equality holds only if $a_k=0,\;$ for for some $k\in [0,n],\,$ or $a_k=k,\;$ for some $k\in [0,n].$

Solution 2

If $a_k,b_k\ge 0,\,$ then it is obvious that


$\displaystyle\prod_{cycl}(a_k+b_k)\ge \prod_{cycl}a_k+\prod_{cycl}b_k,$

because, when expanded, the product on the left contains $2^n\;$ terms, whereas on the right we keep only the first and the last of this enormity. Equality holds if $n=1,\;,$ or when $a_k=0,\;$ for all $k\in [0,n],\,$ or $b_k=0,\;$ for all $k\in [0,n].$

Taking in (*) $b_k=k-a_k,\,$ insures $b_k\ge 0\,$ and $a_k+b_k=k,\,$ for all $k\in \overline{1,n}.\,$ We get

$\displaystyle n!=\prod_{cycl}k\ge \prod_{cycl}a_k+\prod_{cycl}b_k,$

as required.

As we already observed, equality holds if $n=1,\;,$ or when $a_k=0,\;$ for all $k\in [0,n],\,$ or $b_k=0,\;$ for all $k\in [0,n].$


Assume $b_k\gt a_k\gt 0,\,$ $k=1,2,\ldots,n.\,$ Then

$\displaystyle\prod_{k=1}^n(b_k-a_k)\ge \prod_{k=1}^nb_k -\prod_{k=1}^na_k.$

For a proof, define $\displaystyle\frac{a_k}{b_k}=x_k\lt 1,\,$ and observe that $\displaystyle\prod_{k=1}^n(1-x_k)\le 1-\prod_{k=1}^nx_k\,$ which we prove by induction.

For $n=2\,$ and $a,b\in(0,1],\;$ $(1-b)(1-a)\le 1-ab\,$ because it's equivalent to $2ab\le a+b,\;$ whereas $a+b\ge2\sqrt{ab}\ge 2ab.$ (Remember that $ab\le 1.)$

Now assume that the claim holds for $n-1\,$ numbers: $\displaystyle\prod_{k=1}^{n-1}(1-x_k)\le 1-\prod_{k=1}^{n-1}x_k.\,$ We have

$\displaystyle\prod_{k=1}^{n}(1-x_k)= \left[\prod_{k=1}^{n-1}(1-x_k)\right](1-x_n)\le \left(1-\prod_{k=1}^{n-1}x_k\right)(1-x_n)$


$\displaystyle \left(1-\prod_{k=1}^{n-1}x_k\right)(1-x_n)\le 1- \left(\prod_{k=1}^{n-1}x_k\right)(x_n)=1-\prod_{k=1}^{n}x_k.$

which completes the proof.

Solution 3

Taking in the above $b_k=k,\,$ $k=1,2,\ldots,n.\,$ we obtain $\displaystyle\prod_{k=1}^{n}a_k+\prod_{k=1}^{n}(k-a_k)\le \prod_{k=1}^{n}k=n!.$

Solution 4

Set $a_k=k\,\cos^2x_k\,$ and $k-a_k=k\,\sin^2x_k.\,$ Then

$\displaystyle\begin{align}\prod_{k=1}^{n}a_k+\prod_{k=1}^{n}(k-a_k) &=n!\left(\prod_{k=1}^{n}\cos^2x_k+\prod_{k=1}^{n}\sin^2x_k\right)\\ &\le n!\left(\cos^2x_1+\sin^2x_1\right)\\ &=n!. \end{align}$

Solution 5

Let, for $k\in\{1,\ldots,n\},\,$ $\displaystyle b_k=\frac{a_k}{k}\in [0,1].\,$ Then

$\displaystyle n!\ge \prod_{k=1}^{n}a_k+\prod_{k=1}^{n}b_k$

is equivalent to $\displaystyle 1\ge \prod_{k=1}^{n}b_k+\prod_{k=1}^{n}(1-b_k).$ But $\displaystyle\prod_{k=1}^{n}b_k\le\left(\prod_{k=1}^{n}b_k\right)^{1/n}\le\frac{1}{n}\sum_{k=1}^{n}b_k.\,$ Similarly,


Summing up the two inequalities poves the desired result.

Solution 6

The substitution, $\displaystyle b_k=\frac{a_k}{k},\,$ reducs the required inequality to


$\displaystyle 1\ge \prod_{k=1}^{n}b_k+\prod_{k=1}^{n}(1-b_k),\;$ $(0\le b_k\le 1.)$

  • For $n=1,\,$ (1) is true.

  • For the inductive step, assume that (1) is true for $n=m,\,$ for some positive integer $m.$

  • Let $n=m+1.\,$ Since $0\le b_{m+1}\le 1,\,$ we have $\displaystyle \prod_{k=1}^{m+1}b_k\le\prod_{k=1}^{m}b_k\,$ and $\displaystyle \prod_{k=1}^{m+1}(1-b_k)\le\prod_{k=1}^{m}(1-b_k)\,$ such that

    $\displaystyle \prod_{k=1}^{m+1}b_k+\prod_{k=1}^{m+1}(1-b_k)\le \prod_{k=1}^{m}b_k+\prod_{k=1}^{m}(1-b_k)\le 1.$


The problem in integers has been kindly posted at the CutTheKnotMath facebook page by Dorin Marghidanu, followed by Leo Giugiuc's comment with a solution (Solution 1), followed by Dorin Marghidanu's solution (Solution 2) and Marian Dinca's generalization and solution (Solution 3). Solution 4 is by Rachid El Moussaoui; Solution 5 is by Sami Fersi; Solution 6 is by Lampros Katsapas


|Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny