Please help with this interesting sum proof

Jun 2018
4
0
Belgrade, Serbia
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
Sep 2015
2,967
1,676
USA
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?
reposted for readability
 
Last edited by a moderator:

skipjack

Forum Staff
Dec 2006
21,481
2,470
\(\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
May 2007
6,932
774
It has the look of Lagrange interpolation.
 
Jun 2018
4
0
Belgrade, Serbia
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:
Jun 2018
4
0
Belgrade, Serbia
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.
 
Jun 2018
4
0
Belgrade, Serbia
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\)