An Inequality with Permutations, I


Assume, for $i=1,2,\ldots,n,$ $a_{i}\in \bigg[\displaystyle\frac{1}{2},2\bigg].$

Prove that, for any permutation $\sigma$ of the set $\mathbb{N}_{n}=\{1,2,\ldots,n\},$ $\displaystyle\prod_{i=1}^{n}\bigg(a_{i}+\frac{1}{a_{\sigma (i)}}\bigg)\le \bigg(\frac{5}{2}\bigg)^{n}.$

Solution 1

Any permutation, if not a cycle itself, is a product of non-intersecting cycles: $\sigma = \sigma_{1}\sigma_{2}\ldots\sigma_{k},$ $k\ge 1.$ Denote the product in question $\displaystyle\prod_{\sigma}.$ Then, clearly,


This suggests a proof by induction because, with $|\tau |$ being the length of a permutation $\tau,$ $|\sigma |=|\sigma _{1}|+|\sigma _{2}|+\ldots +|\sigma_{k}|$ and we would have on the induction step

$\displaystyle{\prod_{\sigma}=\prod_{j=1}^{k}}\prod_{\sigma_{j}}\le \prod_{j=1}^{k}\bigg(\frac{5}{2}\bigg)^{|\sigma_{j}|}=\bigg(\frac{5}{2}\bigg)^{n}.$

Thus we may assume to deal exlusively with cycles. For $n=1$ suffice it to abserve that, for $\displaystyle x\in\bigg[\displaystyle\frac{1}{2},2\bigg],$ function $\displaystyle f(x)=x+\frac{1}{x}$ attends its maximum value of $\displaystyle\frac{5}{2}$ at the end points:

graph of function f(x) = x + 1/x

Next assume, that for the cycles of length $n$ and less the statement holds true. Consider a permutation $\sigma$ of length $n+1.$ Above we already dispensed with the case where $\sigma$ is not a cycle. So now assume $\sigma$ is a cycle of length $n+1.$

Consider any two consecutive terms in the product $\displaystyle\prod_{\sigma}$ which, to simplify the notations, I shall denote $\prod_{1}=\displaystyle(a_{1}+\frac{1}{a_{2}})(a_{2}+\frac{1}{a_{3}}).$ I wish to compare this product with $\prod_{2}=\displaystyle(a_{1}+\frac{1}{a_{3}})(a_{2}+\frac{1}{a_{2}}).$

It is easy to see (or check) that $\prod_{1}\le\prod_{2}$ iff $(a_{1}-a_{2})(a_{2}-a_{3})\le 0.$ Since $\sigma$ is assumed to be a cycle there such a product of two consecutive factors can always be found, thus, replacing $\sigma$ with aproduct of two cycles: one of length $n,$ the other of length $1.$ Applying to each of these the inductive assumption completes the inductive step.

Fixing a flaw in the solution

However, the above solution has a flaw. Have you noticed?

An induction process is like a chain of dominoes: when one falls it fells the next one that in turn fells the next after it and so on. The "domino effect" does not survive gaps in the chain. Our proof has such a gap!

Observe that we checked the statement for $n=1$ but then - on the inductive step - tacitly assumed that $n$ is at least $3.$ This is not a fatal mistake but to be flawless the proof needs an additional observation, viz., that, for $n=2,$ ${a_{3}}$ needs to be simply taken equal to ${a_{1}}.$ In this case, the requisite inequality $(a_{1}-a_{2})(a_{2}-a_{1})\le 0$ holds automatically.

The last remark (an inequality holding automatically) brings up the question of what if $a_{1}=a_{2}?$ Well, in this case, we may apply the properties of function $f(x)$ introduced earlier. If $a_{1}=a_{2}=a$ then the product $\displaystyle\prod_{(1)(2)}=(a+\frac{1}{a})^{2}\le\bigg(\frac{5}{2}\bigg)^{2},$ as required.

This cleans up the proof.

Solution 2

We'll use the AM-GM (Arthmetic Mean - Geometric Mean) inequality:

$\displaystyle\sqrt[n]{a_{1}a_{2}\cdot\ldots\cdot a_{n}}\le\frac{a_{1}+a_{2}+\ldots +a_{n}}{n}$

that holds for non-negative $\{a_{i}\}.$


$\displaystyle\begin{align} \bigg[\prod_{i=1}^{n}\bigg(a_{i}+\frac{1}{a_{\sigma (i)}}\bigg)\bigg]^{\frac{1}{n}}&\le\frac{1}{n}\sum_{i=1}^{n}\bigg(a_{i}+\frac{1}{a_{\sigma (i)}}\bigg)\\ &=\frac{1}{n}\bigg(\sum_{i=1}^{n}a_{i}+\sum_{i=1}^{n}\frac{1}{a_{\sigma (i)}}\bigg)\\ &=\frac{1}{n}\bigg(\sum_{i=1}^{n}a_{i}+\sum_{i=1}^{n}\frac{1}{a_{i}}\bigg)\\ &=\frac{1}{n}\sum_{i=1}^{n}\bigg(a_{i}+\frac{1}{a_{i}}\bigg)\\ &\le\frac{1}{n}\sum_{i=1}^{n}\frac{5}{2}=\frac{5}{2}. \end{align}$


The problem has been posted by Leo Giugiuc at the Short Mathematical Idea facebook page. Solution 2 is Leo's.

|Contact| |Front page| |Contents| |Induction| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny