# Prove $1 + \sum_{i=0}^n(\frac1{x_i}\prod_{j\neq i}(1+\frac1{x_j-x_i}))=\prod_{i=0}^n(1+\frac1{x_i})$

Prove the identity

$$1 + \sum_{i=0}^n \left(\frac1{x_i}\prod_{j\neq i} \left(1+\frac1{x_j-x_i} \right) \right)=\prod_{i=0}^n \left(1+\frac1{x_i} \right)$$

and hence deduce the inequality in Problem 2:

http://www.imc-math.org.uk/imc2010/imc2010-day2-solutions.pdf

Of course here we need all the $x_i$s distinct. (By the way, this somehow resembles the Lagrange Interpolation formula.)

• The question would be clearer if you wrote the inequality you mention. – Seirios Sep 21 '13 at 7:36
• Make several variable transforms, and proceed by induction. – Ethan Sep 21 '13 at 7:59

Method 1

Let $f(z) = \prod_i (z - x_i)$, we have

$$\prod_{j\ne i}(1 + \frac{1}{x_j-x_i}) = \prod_{j\ne i}\frac{(x_i - 1) - x_j}{x_i - x_j} = - \frac{f(x_i-1)}{f'(x_i)}$$

We can rewrite LHS of the equality as

$$1 - \sum_i \frac{f(x_i-1)}{x_if'(x_i)} = 1 - \sum_i \frac{1}{2\pi i}\int_{C_i} \frac{f(z-1)}{zf'(x_i)(z-x_i)} dz = 1 - \frac{1}{2\pi i}\int_{\sum_i C_i} \frac{f(z-1)}{zf(z)} dz$$ where $C_i$ is a bunch of small circular contours surrounding $x_i$ counterclockwisely. By deforming the contours, it is easy to see above contour integral is equal to the difference of two contour integral, one with a big circle $C_{\infty}$ near infinity and another small circle $C_o$ at origin:

$$\frac{1}{2\pi i}\int_{\sum_i C_i} \frac{f(z-1)}{zf(z)} dz = \frac{1}{2\pi i} \left( \int_{C_\infty} - \int_{C_o} \right) \frac{f(z-1)}{zf(z)} dz$$

Since $\displaystyle\;\;\frac{f(z-1)}{z f(z)} = \frac{1}{z} + O(\frac{1}{z^2})\;\;$ for large $z$, we have

$$\frac{1}{2\pi i} \int_{C_\infty} \frac{f(z-1)}{zf(z)} dz = \frac{1}{2\pi i} \int_{C_\infty} ( \frac{1}{z} + O(\frac{1}{z^2}) ) dz = 1$$

This cancels out the $1$ in LHS of inequality and we get

$$\text{LHS} = \frac{1}{2\pi i}\int_{C_o}\frac{f(z-1)}{zf(z)}dz = \frac{f(-1)}{f(0)} =\frac{\prod_i(-1 - x_i)}{\prod_i ( -x_i )} = \prod_i (1+\frac{1}{x_i}) =\text{RHS}$$

Method 2

If one don't want to use complex analysis, an alternate way is apply Lagrange interpolation formula to polynomial $f(z-1) - f(z)$ whose degree is one less than the number of $x_i$, we have:

$$f(z-1) - f(z) = \sum_i \frac{f(z)(f(x_i-1) - f(x_i))}{(z-x_i)f'(x_i)} = f(z) \sum_{i}\frac{f(x_i-1)}{(z-x_i)f'(x_i)}$$ This implies $$1 + \sum_i \frac{f(x_i-1)}{(z-x_i)f'(x_i)} = \frac{f(z-1)}{f(z)}$$ Set $z = 0$, we obtain $$\text{LHS} = 1 - \sum_i \frac{f(x_i-1)}{x_if'(x_i)} = \frac{f(-1)}{f(0)} = \text{RHS}.$$