Number Theory Number Theory Math Forum

 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.
June 27th, 2018, 03:48 PM   #2
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,552
Thanks: 1402

Quote:
 Originally Posted by ognjenmi 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 skipjack; June 28th, 2018 at 01:44 PM.

 June 27th, 2018, 08:19 PM #3 Global Moderator   Joined: Dec 2006 Posts: 20,969 Thanks: 2219 $\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$
 June 28th, 2018, 01:36 PM #4 Global Moderator   Joined: May 2007 Posts: 6,822 Thanks: 723 It has the look of Lagrange interpolation.
 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.
 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.
July 2nd, 2018, 01:43 PM   #7
Global Moderator

Joined: Oct 2008
From: London, Ontario, Canada - The Forest City

Posts: 7,963
Thanks: 1148

Math Focus: Elementary mathematics and beyond
Quote:
 Originally Posted by ognjenmi Waiting for moderator to publish it so I can finalize it.
Done.

 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$

 Tags interesting, proof, sum

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top