16
$\begingroup$

i found a equation that holds for any natural number of n and any $x_i \ne x_j$ as follows:

$$\sum\limits_{i = 1}^{n } {\prod\limits_{\substack{j = 1\\j \ne i}}^{n } {\frac{{x_i }}{{x_i - x_j }}} } = 1$$

when n=2, it is given by

$$\frac{x_1}{x_1-x_2}+\frac{x_2}{x_2-x_1}=\frac{x_1 - x_2}{x_1 - x_2} = 1$$

when n=3, it is given by

$$\frac{x_1^2}{(x_1-x_2)(x_1-x_3)}+\frac{x_2^2}{(x_2-x_1)(x_2-x_3)}+\frac{x_3^2}{(x_3-x_1)(x_3-x_2)}=1$$

But, how can I prove for general $n$?

  • 0
    You're probably 90% there. I know that you know that n = 3 works. But for n = 3 write: LHS = [(x1^2(x2-x3) + x2^2(x1-x3) + x3^2(x1-x2)] / (x1-x2)(x2-x3)(x1-x3) = (1), i.e. make the denominator equal to Product(x_i - x_j). Now try the same thing for n = 4. The tricky part is this: try to notice a way in which you can cancel down (1) and your similar result for n=4 so that you can generalise.2012-11-20
  • 0
    Thanks for your comments. Acctually i cound't dare to try the n=4 case. Even i tried the n=3 case with the help of mathematica. :)2012-11-20

2 Answers 2

18

Consider the Lagrange interpolation of the polynomial $f(x)=x^{n-1}$ with interpolation points $x_1,\ldots,x_n$. We have: $$x^{n-1}=\sum_{i=1}^{n}x_i^{n-1}\prod_{j\neq i}\frac{x-x_j}{x_i-x_j},$$ so, by comparing the leading coefficients of RHS and LHS, the result follows.

  • 0
    Thanks for your comments. When $x=1$, then I get $1=\sum \prod \frac{x_i}{x_i - x_j} \prod (1 - x_j)$, where I have no idea how to remove the second prod term in the RHS...2012-11-20
  • 0
    and.... i get $\frac{1}{\prod \limits_{j=1}^{n} (1- x_j)} = \sum \limits_{i=1}^{n} \prod \limits_{j \ne i} \frac{x_i}{x_i - x_j} -\sum \limits_{i=1}^{n} x_i \prod \limits_{j \ne i} \frac{x_i}{x_i - x_j}$..........which means $\frac{1}{\prod \limits_{j=1}^{n} (1- x_j)} + \sum \limits_{i=1}^{n} x_i \prod \limits_{j \ne i} \frac{x_i}{x_i - x_j} = 1$ .....2012-11-20
  • 1
    You have not to take the evaluations of both sides for a specific $x$, you have to compare the coefficients of the monomial $x^{n-1}$: in the LHS you have $1$, in the $RHS$ you have $\sum_{i=1}^{n}x_i^{n-1}\prod_{j\neq i}\frac{1}{x_i-x_j}=\sum_{i=1}^{n}\prod_{j\neq i}\frac{x_i}{x_i-x_j}$, QED.2012-11-20
  • 0
    I'm afraid that i don't get how the $x_j$ is gone in the above equation; i expected $\sum\nolimits_{i=1}^{n} x_i^{n-1} \prod \nolimits_{j \ne i} \frac{1- x_j}{x_i - x_j}$.2012-11-21
  • 0
    Again: for each $i$, $\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}$ is a polynomial in $x$ with degree $(n-1)$, and the coefficient of the leading monomial is $\prod_{j\neq i}\frac{1}{x_i-x_j}$, so if you multiply this quantity by $x_i^{n-1}$ and sum over $i$ you get your identity.2012-11-21
  • 0
    Please forgive my ignorance. I don't understand from which 'the coefficient of the leading monomial is $\prod \nolimits_{j \ne i} \frac{1}{x_i - x_j}$' comes..... actually i'm not familiar with 'interpolating Polynomials'.....and how can i know that the result of multiplying and summing is 1?2012-11-22
  • 0
    If you have a polynomial $ a_m x^m + a_{m-1} x^{m-1} + \ldots + a_0$, the leading monomial is $ a_m x^m $ and the coefficient of the leading monomial is $a_m$. If you have a polynomial in the form $ C(x-b_1)\cdot\ldots\cdot(x-b_k)$, the leading monomial is $C x^k$. Now, back to Lagrange interpolation, the RHS and the LHS are the same polynomial since they have degree $(n-1)$ and equal values in $n$ points, i.e. $x_1,\ldots,x_n$.2012-11-22
  • 1
    So, $x^{n-1}$ can be written as $a + a_1 x + \cdots + a_{n-1} x^{n-1}$, which means $a_{n-1} = 1$. And $a_{n-1}$ in the Lagrange inperplation polynomial is, $\sum x_i^{n-1} \prod \frac{1}{x_i-x_j}$ as you said... Wow! its proved. oh my god... Thank you so much, i really appriciate. It really helped.2012-11-23
  • 0
    i wonder how about those $a, \cdots a_{n-2}$. doesn't i need to show that they are zero?2012-11-23
  • 0
    No i don't. beacause less or equal to $n$th polynomial is unique... so, $a_k = (\sum \prod ~~ )x^{k}$ for $k are zero from the origin....2012-11-23
6

For $n>1$, the partial fractional decomposition of $$ \frac1z\prod_{j=1}^{n-1}\frac{z}{z-x_j} =\frac{z^{n-2}}{\prod\limits_{j=1}^{n-1}(z-x_j)} =\sum_{i=1}^{n-1}\frac{A_i}{z-x_i}\tag{1} $$ using the Heaviside method yields $$ A_i=\frac{x_i^{n-2}}{\prod\limits_{\substack{j=1\\j\ne i}}^{n-1}(x_i-x_j)} =\prod_{\substack{j=1\\j\ne i}}^{n-1}\frac{x_i}{x_i-x_j}\tag{2} $$ Combine $(1)$ and $(2)$: $$ \begin{align} \prod_{j=1}^{n-1}\frac{z}{z-x_j} &=\sum_{i=1}^{n-1}A_i\frac{z}{z-x_i}\\ &=\sum_{i=1}^{n-1}\frac{z}{z-x_i}\prod_{\substack{j=1\\j\ne i}}^{n-1}\frac{x_i}{x_i-x_j}\\ &=\sum_{i=1}^{n-1}\left(1-\frac{x_i}{x_i-z}\right)\prod_{\substack{j=1\\j\ne i}}^{n-1}\frac{x_i}{x_i-x_j}\tag{3} \end{align} $$ Set $z=x_n$ in $(3)$: $$ \prod_{j=1}^{n-1}\frac{x_n}{x_n-x_j} =\sum_{i=1}^{n-1}\prod_{\substack{j=1\\j\ne i}}^{n-1}\frac{x_i}{x_i-x_j} -\sum_{i=1}^{n-1}\prod_{\substack{j=1\\j\ne i}}^n\frac{x_i}{x_i-x_j}\tag{4} $$ Add the second term of the right side of $(4)$ to both sides: $$ \sum_{i=1}^n\prod_{\substack{j=1\\j\ne i}}^n\frac{x_i}{x_i-x_j} =\sum_{i=1}^{n-1}\prod_{\substack{j=1\\j\ne i}}^{n-1}\frac{x_i}{x_i-x_j}\tag{5} $$ Noting that the case $n=1$ follows vacuously, using $(5)$ and induction proves that $$ \sum_{i=1}^n\prod_{\substack{j=1\\j\ne i}}^n\frac{x_i}{x_i-x_j}=1\tag{6} $$

  • 0
    Thank you for your answer. It's relatively straitforward to follow up.2012-11-23