# How to prove Ky Fan Inequality using Forward-Backward Induction?

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$$.

• Isn't $0\le x_i\leq\frac12$ required? – saulspatz Apr 20 at 2:31
• @saulspatz thank you for reminding me! I'll update the details right now. – Zoe Desvl Apr 20 at 2:35
• Interesting question. In order to get responses that suit your needs, please include your own thoughts, the effort made so far, and the specific difficulties that got you stuck. When doing so, please click on the tiny edit and use MathJax and improve the body of the post instead of commenting. – Lee David Chung Lin Apr 20 at 12:28

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.