#### ognjenmi

Hi,

I am trying to prove the following identity. I obviously can't see something here.

$$\displaystyle \sum_{1}^{n}\frac{\prod_{r=1}^{n-1}(y_k-z_r)}{\prod_{1<=r<=n, r\ne k}(y_k-y_r)}=1$$

Where $$\displaystyle y_1,y_2,...y_n$$ are different numbers and $$\displaystyle z_1,z_2,...z_{n-1}$$ is set of any numbers.

I obviously can't see something. Any hints?

Last edited by a moderator:

#### romsek

Math Team
Hi,

I am trying to prove the following identity. I obviously can't see something here.

$$\displaystyle \Large \sum_{1}^{n}\frac{\prod_{r=1}^{n-1}(y_k-z_r)}{\prod_{1<=r<=n, r\ne k}(y_k-y_r)}=1$$

Where $$\displaystyle y_1,y_2,...y_n$$ are different numbers and $$\displaystyle z_1,z_2,...z_{n-1}$$ is set of any numbers.

I obviously can't see something. Any hints?

Last edited by a moderator:

#### skipjack

Forum Staff
$$\displaystyle {\Large\sum_{k=1}^{n}}\frac{\displaystyle {\small \prod_{\large r=1}^{\large n-1}}(y_k-z_r)}{\displaystyle {\small \prod_{\large1\leqslant r\leqslant n, r\ne k}}(y_k-y_r)}=1$$

#### mathman

Forum Staff
It has the look of Lagrange interpolation.

#### ognjenmi

I finally did it

Hi,

I think I did it.

Actually, least common multiple of all sum members is

$$\displaystyle \prod_{i=1}^{n-1}\prod_{k=i+1}^{n}(y_i-y_k)$$.

In numerator, we have the sum with member with ordinal number i is

$$\displaystyle (-1)^{i+1} \prod_{k=1}^{n-1}(y_i-z_k)\prod_{1\le k\le n-1,k \ne i}\prod_{k+1 \le r \le n, r \ne i}(y_k-y_r)$$

For shorter notation, let's have

$$\displaystyle \pi(i) = \prod_{1\le k\le n-1,k \ne i}\prod_{k+1 \le r \le n, r \ne i}(y_k-y_r)$$

When we develop the the product, we get

$$\displaystyle (y_i^{n-1} + \sum_{k=1}^{n-1}((-1)^{k}y_i^{k-1}\sum_{r=1}^{\binom{n-1}{k}}C(k,r)))\cdot \pi(i)$$

where C(k,r) is r-th combination of k elements on array $$\displaystyle (z_1,z_2,...,z_{n-1})$$

When we get back to the sum in the numerator, we get
$$\displaystyle \sum_{i=1}^{n}y_i^{n-1}\cdot \pi(i) + \sum_{k=1}^{n-1}(-1)^{k}\sum_{r=1}^{\binom{n-1}{k}}C(k,r)\cdot \sum_{i=1}^{n}y_i^{k-1}\cdot \pi(i)$$

As we now got multipliers of z-array (their combinations) we have to prove that every

$$\displaystyle \sum_{i=1}^{n}y_i^{r}\cdot \pi(i)= \sum_{i=1}^{n}y_i^{r}\prod_{1\le k\le n-1,k \ne i}\prod_{k+1 \le r \le n, r \ne i}(y_k-y_r)=0$$

for r < n-1.

Approach used here uses the fact that all elements have the same polynomial degree and greatest degree of particular variable is n-2. Thus for each element (possible repeatable combination of y-array) we will have its negative pair as -1 is equally combined as all y-array elements.

Therefore result has to be zero.

When we look

$$\displaystyle \sum_{i=1}^{n}y_i^{n-1}\cdot \pi(i)$$

We see that it can't be zero as $$\displaystyle y_i^{n-1}$$ can't be found in other sum elements where as maximal degree of particular element there is n-2. However we can look for "similar" one that has $$\displaystyle -y_l^{n-1}y_y{n-2}$$ and the same products in continuation.

We then $$\displaystyle y_l^{n-2}y_i^{n-2}(y_i-y_l)(rest \; of \; product)$$

We now halved number of sum elements. This can be repeated recursively n-1 times and then we get one product that is

$$\displaystyle \prod_{i=1}^{n-1}\prod_{k=i+1}^{n}(y_i-y_k)$$

which gives what is wanted.

Last edited by a moderator:

#### ognjenmi

I finally did it

For some reason my yesterday reply is not published. I didn't actually finished the proof as I illustrated idea behind the proof. Waiting for moderator to publish it so I can finalize it.

Forum Staff

#### ognjenmi

And now to get to the point

Please first note that I made mistake by not including $$\displaystyle (-1)^{k}$$ and $$\displaystyle (-1)^{i+1}$$ in sums with $$\displaystyle y_i$$ elements which you will see below.

In divisor from the beginning we have

$$\displaystyle \prod_{i=1}^{n-1}\prod_{k=i+1}^{n}(y_i-y_k) = (-1)^{n-1}det(V_{n-1})$$

Where V is Vandermonde matrix of order of n-1 (n x n dimensions).

$$\displaystyle \pi(i) = (-1)^{n-2}det(V_{n-2}(i))$$ where V(i) is Vandermonde matrix of order of n-2 where $$\displaystyle y_i$$ is missing.

Then the sum $$\displaystyle \sum_{i=1}^{n}(-1)^{i}y_{i}^{k-1}\cdot \pi(i)$$ is determinant of matrix which has $$\displaystyle (-1)^{n-2}V(i)$$ as cofactor and vector $$\displaystyle (y_1^{k-1}, ...,y_n^{k-1})$$ where $$\displaystyle 1 \le k \le n-1$$ so it is less or equal to n-2. This means that in V(i) there is already such column of values

$$\displaystyle \begin{bmatrix} 1& y_1& \cdots & y_1^{k-1}& y_1^{k-1}& \cdots& y_1^{n-2}&\\ \vdots & \vdots& \vdots& \vdots& \vdots& \vdots& \vdots& \\ 1& y_n& \cdots& y_n^{k-1}& y_n^{k-1}& \cdots& y_n^{n-2}& \end{bmatrix}$$

And determinant of each such matrix is zero.

In $$\displaystyle \sum_{i=1}^{n}(-1)^{i+1}y_i^{n-1}\cdot \pi(i)$$ we have similar situation with V(i) as cofactors. However we now have vector $$\displaystyle (y_1^{n-1}, ...,y_n^{n-1})$$ as matrix column so we are getting Vandermonde matrix of order n-1. Therefore we have
$$\displaystyle \sum_{i=1}^{n}(-1)^{i+1}y_i^{n-1}\cdot \pi(i)=(-1)^{n-1}det(V)$$

At the end $$\displaystyle \frac{(-1)^{n-1}det(V)}{(-1)^{n-1}det(V)}=1$$