# Inequality connected to Lagrange's interpolation formula

I hope it is okay that I re-post my question from Math.SE. I know it is very specific. I would be grateful for thoughts on how to tackle this problem. Any idea is welcome!

For $n \in \mathbb{N}$, let the positive real numbers $x_1, \dots, x_n, y_1, \dots, y_n$ satisfy the following interlacing inequalities: $$0 < x_1 < y_1 < x_2 < y_2 < \dots < x_n < y_n.$$ Show that $$a_{ij} := \sum_{k=1}^n \frac{y_k^2 - x_k^2}{x_k (y_i^2 - x_k^2) (y_j^2 - x_k^2)}\Big( \prod_{l \neq k} \frac{y_l^2 - x_k^2}{x_l^2 - x_k^2} \Big) > 0$$ for all $i,j = 1, \dots, n.$

My thoughts so far:

• The case $i=j$ is simple: $y_l^2 - x_k^2$ and $x_l^2-x_k^2$ have the same sign for all $k,l = 1, \dots, n.$ Since also $y_k^2 > x_k^2$ for all $k=1,\dots,n,$ every summand is positive.
• The problem is symmetric, so we only need to consider $i > j$. Then $(y_i^2 - x_k^2)(y_j^2-x_k^2) < 0$ if and only if $j < k \le i.$ I tried to apply Lagrange's interpolation formula, defining $$p(x) := \frac12\prod_{l=1}^n (x_l-x) \prod_{k=1}^n (x_l+x) = \frac12\prod_{k=1}^n (x_l^2 - x^2).$$ This is a polynomial of degree $2n$, and it holds that $$p'(x_k) = - x_k \prod_{l \neq k} (x_l^2-x_k^2) \qquad \text{ and } \qquad p'(-x_k) = x_k \prod_{l \neq k} (x_l^2 - x_k^2)$$ for $k = 1, \dots, n.$ Since $$\frac1{(y_i^2-x_k^2)(y_j^2-x_k^2)} = \frac1{y_i^2-y_j^2} \Big( \frac1{y_i^2-x_k^2} - \frac1{y_j^2 - x_k^2}\Big),$$ we may write \begin{align*} a_{ij} &= \frac1{y_i^2 - y_j^2}\Big( \sum_{k=1}^n \frac{f_i(-x_k)}{p'(-x_k)(y_i+x_k)} - \sum_{k=1}^n \frac{f_j(-x_k)}{p'(-x_k)(y_j+x_k)}\Big)\\ &= \frac1{y_i^2 - y_j^2}\Big( \sum_{k=1}^n \frac{f_i(x_k)}{p'(x_k)(y_i-x_k)} - \sum_{k=1}^n \frac{f_j(x_k)}{p'(x_k)(y_j-x_k)}\Big) \end{align*} with $$f_m(x) := -\frac{\text{sgn}(x)}{y_m+x} \prod_{l=1}^n (y_l^2-x^2), \qquad m \in \{i,j\}.$$ Unfortunately, this is not a polynomial.
• With a similar approach, one can show that $$\sum_{k=1}^n \Big( \prod_{l \neq k} \frac{y_l^2 - x_k^2}{x_l^2 - x_k^2} \Big) \frac{y_k^2 - x_k^2}{(y_i^2 - x_k^2) (y_j^2 - x_k^2)} = \delta_{i=j}.$$ Maybe this is helpful?

Write $x_i$ for $x_i^2$ and $y_i$ for $y_i^2$, our sum is $$a_{ij}=\sum_{k=1}^n \frac{f(x_k)}{\prod_{l\ne k} (x_k-x_l)},\,f(t)=-t^{-1/2}\prod_{l\ne i,j} (t-y_j).$$
By Lagrange interpolation, it is a coefficient of $t^{n-1}$ in the polynomial $g(t)$ of degree at most $n-1$, which interpolates the function $f$ in the points $x_1,\dots,x_n$. Thus by Rolle's theorem we have $a_{ij}\cdot (n-1)!=f^{(n-1)}(\theta)$ for a certain positive $\theta$. But $(n-1)$-st derivative of $f$ is clearly positive term-wise: $f=(-1)^{n-1}(c_1t^{-1/2}-c_2t^{1/2}+c_3t^{3/2}-\dots+(-1)^{n-2}c_{n-1}t^{n-5/2})$ for positive coefficients $c_1,c_2,\dots,c_{n-1}$.

Note that we did not use that $x$'s and $y$'s interlace, only that they are positive.

• Why is it clear that $f^{(n-1)}$ is positive? – Elias Strehle Feb 28 '17 at 9:53
• look at the formula for $f$ (written now in the answer) and differentiate each term $n-1$ times. The sign is always positive. – Fedor Petrov Feb 28 '17 at 10:46
• I am having trouble with the signs. The Lagrange polynomial is $$\Big(\sum_{k=1}^n \frac{f(x_k)}{\prod_{l \neq k}(x_l-x_k)}\Big)x^{n-1} + ...$$ (not $(x_k - x_l)$). If I follow your proof I get that $(-1)^{n-1}a_{ij} > 0$? – Elias Strehle Feb 28 '17 at 12:53
• Why? $x_k-x_l$, not $x_l-x_k$ – Fedor Petrov Feb 28 '17 at 13:19
• To interpolate $f$ at the $x_1, \dots, x_n$, I chose $$g(x) = \sum_{k=1}^n f(x_k) \Big( \prod_{l \neq k} \frac{x-x_l}{x_k-x_l}\Big) = \Big(\sum_{k=1}^n \frac{f(x_k)}{\prod_{l\neq k} x_k-x_l} \Big) x^{n-1} + \tilde{g}(x),$$ for some polynomial $\tilde{g}$ of degree $n-2$. – Elias Strehle Feb 28 '17 at 13:39

The expression is equivalent to $$a_{ij}=\sum_k \frac{\prod_{l\neq i,j} (y_l^2-x_k^2) }{x_k\prod_{l\neq k} (x_l^2-x_k^2)}.$$ This is a linear function in each $y^2_m$ for every $m$. Assume that there exist $y_m\in [x_1,x_n]$. Then the term gets smaller or equal if we replace $y_m$ by $x_1$ or $x_n$. However after the cancellations what is left is an expression of the same form with a smaller $n$. Hence one can prove the inequality by induction.

• The assumption $y_m \in [x_1,x_n]$ makes this difficult: We are cancelling $y_m$ and $x_1$ (or $x_n$). For the induction to work, we now need another $y_{m'} \in [x_2, x_n]$ etc. – Elias Strehle Feb 28 '17 at 11:27

Just assume $x_k, y_k>0$ without interlacing. If necessary by indexing, write $$a=\sum_k \frac{\prod_{l=1}^{n-2}(y_l^2-x_k^2)}{x_k\prod_{l\neq k}^{1,n}(x_l^2-x_k^2)}.$$ If $e_m(y_1^2,\dots,y_{n-2}^2)$ denotes the elementary symmetric polynomials, then $$\prod_{l=1}^{n-2}(y_l^2-x_k^2)=\sum_{r=0}^{n-2}(-1)^rx_k^{2r}\,e_{n-2-r}(y_1^2,\dots,y_{n-2}^2).$$ Since $e_m>0$, to prove $a>0$ it suffices to check that $$(-1)^r\sum_{k=1}^nx_k^{2r-1}\prod_{\ell\neq k}^{1,n}\frac1{x_{\ell}^2-x_k^2}>0 \qquad \text{for each \,\,0\leq r\leq n-2}.$$ I claim that there exists a homogeneous symmetric polynomial $P_r(x_1,\dots,x_n)$ with positive coefficients such that $$(-1)^r\sum_{k=1}^nx_k^{2r-1}\prod_{\ell\neq k}^{1,n}\frac1{x_{\ell}^2-x_k^2} =\frac{P_r(x_1,\dots,x_n)}{\prod_{j=1}^nx_j}\prod_{i<j}^{1.n}\frac1{x_i+x_j}.$$ This has now become a new query on MO. Update. There's a cute answer given now. Check it out!

• Maybe Fedor Petrov's answer helps with your query as well? I can post my full proof if you want. – Elias Strehle Feb 28 '17 at 18:39