Prove Ky Fan Inequality using Forward-Backward Induction

inductioninequality

The classical version of the inequality is:
$${\frac {{\bigl (}\prod _{{i=1}}^{n}x_{i}{\bigr )}^{{1/n}}}{{\bigl (}\prod _{{i=1}}^{n}(1-x_{i}){\bigr )}^{{1/n}}}}\leq {\frac {{\frac 1n}\sum _{{i=1}}^{n}x_{i}}{{\frac 1n}\sum _{{i=1}}^{n}(1-x_{i})}}~, \quad \text{where}~~ 0 ≤ x_i ≤ \frac12$$

The equality holds if and only if $x_1=x_2=\dots=x_n$.

How to prove the inequality using Forward-Backward induction?

Update:

Thank achille hui for the beautiful proof! But I think it's still useful to share my wrong way of doing it: Trying to use some direct calculations, only to get a monster. Moreover, I thought that the 'forward' step can only be $2^k\to 2^{k+1}$, but achille hui shows us that it can be $n\to 2n$.

Best Answer

For any $x_1,\ldots,x_n \in [0,\frac12]$, define $$f(x_1,\ldots,x_n) = \frac{\frac1n\sum_{k=1}^n x_k}{1 - \frac1n\sum_{k=1}^n x_k}$$ The inequality at hand can be rewritten as $$f(x_1,\ldots,x_n) \ge \prod_{k=1}^n f(x_k)^{\frac1n}\tag{*1}$$ For $n \ge 2$, let $\mathcal{S}_n$ be statement $(*1)$ is true for any $(x_1,\ldots,x_n) \in [0,\frac12]$.

  1. $\mathcal{S}_2$ is true.

    For any $x,y \in [0,\frac12]$, we have $$f(x,y)^2 - f(x)f(y) = \frac{(1-x-y)(x-y)^2}{(1-x)(1-y)(2-x-y)^2} \ge 0$$

  2. Assume $\mathcal{S}_n$ is true.

    For any $x_1,x_2,\ldots, , x_{2n} \in [0,\frac12]$, let $z_k = \frac12(x_{2k-1} + x_{2k})$ for $k = 1,\ldots, n$.
    Since $\frac{1}{2n}\sum_{k=1}^{2n} x_n = \frac{1}{n}\sum_{k=1}^n z_k$, we have $$\begin{align} f(x_1,\ldots,x_{2n}) = & f(z_1,\ldots,z_n)\\ \stackrel{\mathcal{S}_n}{\ge} & \prod_{k=1}^n f(z_k)^{\frac1n} = \prod_{k=1}^n f(x_{2k-1},x_{2k})^{\frac1n}\\ \stackrel{\mathcal{S}_2}{\ge} & \prod_{k=1}^n \left( f(x_{2k-1})^{\frac12}f(x_{2k})^{\frac12} \right)^{\frac1n} = \prod_{k=1}^{2n} f(x_k)^{\frac{1}{2n}}\end{align}$$ This means $\mathcal{S}_n \implies \mathcal{S}_{2n}$.

  3. Assume $\mathcal{S}_{n+1}$ is true for some $n \ge 2$.

    For any $x_1,x_2,\ldots, , x_{n} \in [0,\frac12]$, let $x_{n+1} = \bar{x} \stackrel{def}{=} \frac1n\sum_{k=1}^n x_k$.

    If $\bar{x} = 0$, then all $x_k = 0$ and $(*1)$ is satisfied trivially.

    Assume $\bar{x} \ne 0$. Notice $\displaystyle\;\frac{1}{n+1}\sum_{k=1}^{n+1} x_k = \bar{x} = \frac{1}{n}\sum_{k=1}^n x_k$, we find $$f(x_1,\ldots,x_n) = f(\bar{x}) = f(x_1,\ldots,x_{n+1}) \stackrel{\mathcal{S}_{n+1}}{\ge} \left(\prod_{k=1}^{n+1} f(x_k)\right)^{\frac{1}{n+1}} = \left(f(\bar{x})\prod_{k=1}^n f(x_k)\right)^{\frac{1}{n+1}}$$ Rising both side to power $\frac{n+1}{n}$ and remove a common factor $f(\bar{x})^{\frac1n}$, we find $(*1)$ is satisfied again. This means $\mathcal{S}_{n+1} \implies \mathcal{S}_n$.

By Forward-Backward induction, $\mathcal{S}_n$ is true for all $n \ge 2$.

Update

Look at this question again, I notice I have overlooked the part "the equality holds if and only if $x_1 = \cdots = x_n$". The modification of above proof to cover that is relatively straight forward. I'll leave that as an exercise.

Related Question