My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
June 27th, 2018, 03:37 PM   #1
Newbie
 
Joined: Jun 2018
From: Belgrade, Serbia

Posts: 4
Thanks: 0

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?

Last edited by skipjack; June 28th, 2018 at 01:43 PM.
ognjenmi is offline  
 
June 27th, 2018, 03:48 PM   #2
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,009
Thanks: 1042

Quote:
Originally Posted by ognjenmi View Post
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 skipjack; June 28th, 2018 at 01:44 PM.
romsek is offline  
June 27th, 2018, 08:19 PM   #3
Global Moderator
 
Joined: Dec 2006

Posts: 19,186
Thanks: 1648

$\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 $
skipjack is offline  
June 28th, 2018, 01:36 PM   #4
Global Moderator
 
Joined: May 2007

Posts: 6,540
Thanks: 591

It has the look of Lagrange interpolation.
mathman is offline  
July 1st, 2018, 03:15 PM   #5
Newbie
 
Joined: Jun 2018
From: Belgrade, Serbia

Posts: 4
Thanks: 0

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 skipjack; July 2nd, 2018 at 06:41 PM.
ognjenmi is offline  
July 2nd, 2018, 11:02 AM   #6
Newbie
 
Joined: Jun 2018
From: Belgrade, Serbia

Posts: 4
Thanks: 0

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.
ognjenmi is offline  
July 2nd, 2018, 01:43 PM   #7
Global Moderator
 
greg1313's Avatar
 
Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,823
Thanks: 1049

Math Focus: Elementary mathematics and beyond
Quote:
Originally Posted by ognjenmi View Post
Waiting for moderator to publish it so I can finalize it.
Done.
greg1313 is offline  
July 3rd, 2018, 10:30 AM   #8
Newbie
 
Joined: Jun 2018
From: Belgrade, Serbia

Posts: 4
Thanks: 0

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$
ognjenmi is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
interesting, proof, sum



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Interesting Proof Exercise Timios Algebra 5 December 9th, 2014 10:05 PM
interesting!! benten Algebra 10 May 14th, 2013 08:36 PM
interesting one fride Algebra 1 February 23rd, 2013 09:49 PM
Hmm, Interesting. Eval New Users 6 April 22nd, 2011 05:54 AM





Copyright © 2018 My Math Forum. All rights reserved.