 My Math Forum Please help with this interesting sum proof
 User Name Remember Me? Password

 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{\small \prod_{\large r=1}^{\large n-1}}(y_k-z_r)}{\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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      