My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Number Theory (http://mymathforum.com/number-theory/)
-   -   Please help with this interesting sum proof (http://mymathforum.com/number-theory/344478-please-help-interesting-sum-proof.html)

ognjenmi June 27th, 2018 04:37 PM

Please help with this interesting sum proof
 
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?

romsek June 27th, 2018 04:48 PM

Quote:

Originally Posted by ognjenmi (Post 595945)
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

skipjack June 27th, 2018 09:19 PM

$\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 June 28th, 2018 02:36 PM

It has the look of Lagrange interpolation.

ognjenmi July 1st, 2018 04:15 PM

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.

ognjenmi July 2nd, 2018 12:02 PM

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.

greg1313 July 2nd, 2018 02:43 PM

Quote:

Originally Posted by ognjenmi (Post 596126)
Waiting for moderator to publish it so I can finalize it.

Done.

ognjenmi July 3rd, 2018 11:30 AM

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$


All times are GMT -8. The time now is 09:34 PM.

Copyright © 2019 My Math Forum. All rights reserved.