An awful identity

Solution 1:

Idea:

Use the Lagrange interpolation formula for the $(r+p)$th degree polynomial $$f(z)=\prod_{j=1}^r(z-x_j)\prod_{k=0}^p(z-u'_k)-\prod_{j=1}^p(z-x'_j)\prod_{k=0}^r(z-u_k),$$ interpolated at $r+p+1$ points $x_1,\ldots,x_r,u'_0,\ldots,u'_p$. Computing the coefficient of $z^{r+p}$ at both sides gives the identity you want to prove.

Proof:

Let us first recall the formula for the Lagrange interpolation polynomial $$L(z)=\sum_{i=1}^{N} f_i\prod_{j\neq i}^{N}\frac{z-z_j}{z_i-z_j}.\tag{$\spadesuit$}$$ This is the unique $(N-1)$th degree polynomial passing through $N$ points $(z_i,f_i)$ (with $i=1,\ldots, N$).

Next let us consider a specific polynomial (note that it also has degree $N-1$) $$P(z)=\prod_{i=1}^{N}(z-z'_i)-\prod_{i=1}^{N}(z-z_i),\tag{$\clubsuit$}$$ which depends on $2N$ parameters $z_1,\ldots,z_{N}$, $z_1',\ldots,z_N'$. The values of this polynomial at $z=z_i$ are given by $$P(z_i)=\prod_{j=1}^N(z_i-z'_j).$$

Hence, using ($\spadesuit$) with $f_i=P(z_i)$, we obtain the identity $$\sum_{i=1}^N\prod_{k=1}^N(z_i-z'_k)\prod_{j\neq i}^{N}\frac{z-z_j}{z_i-z_j}= \prod_{i=1}^{N}(z-z'_i)-\prod_{i=1}^{N}(z-z_i).\tag{$\diamondsuit$}$$ This is an equality between two polynomials. Now compute the coefficient in front of $z^{N-1}$ at both sides of ($\diamondsuit$). This leads to the identity $$\sum_{i=1}^N\frac{\prod_{j=1}^N(z_i-z'_j)}{ \prod_{j\neq i}^N(z_i-z_j)}= \sum_{i=1}^N z_i-\sum_{i=1}^Nz'_i.\tag{$\heartsuit$}$$

Finally, let us set $N=r+p+1$ and choose $\{z_i\}$, $\{z'_i\}$ in ($\heartsuit$) in the following way: \begin{align*} z_i&=\begin{cases}x_i & \text{for }i=1,\ldots,r,\\ u'_{i-r-1} & \text{for } i=r+1,\ldots,r+p+1, \end{cases}\\ z'_i&=\begin{cases}u_i & \text{for }i=1,\ldots,r,\\ x'_{i-r-1} & \text{for } i=r+1,\ldots,r+p+1. \end{cases} \end{align*} Then ($\heartsuit$) transforms into \begin{align*} \sum_{i=1}^r\frac{\prod_{j=1}^r(x_i-u_j)\prod_{j=0}^p (x_i-x'_j)}{\prod_{j\neq i}^r(x_i-x_j)\prod_{j=0}^p(x_i-u'_j)}+ \sum_{i=0}^{p}\frac{ \prod_{j=1}^r(u'_i-u_j)\prod_{j=0}^p (u'_i-x'_j) }{\prod_{j=1}^r(u'_i-x_j)\prod_{j\neq i}^p(u'_i-u'_j)}=\\ =\sum_{i=1}^r x_i+\sum_{i=0}^p u'_i-\sum_{i=1}^r u_i-\sum_{i=0}^p x'_i, \end{align*} and this is nothing but the necessary identity. $\blacksquare$