Proving an identity of quadratic form

Question

Let $n$ be even and $x_1,x_2,⋯,x_n$ be reals. Show that$$\sum_{1\le i<j\le n}\min(|i-j|,n-|i-j|)x_ix_j\\=\sum_{j=1}^{\frac n2}(x_j+x_{j+1}+⋯+x_{j+\frac n2-1})(x_{j+\frac n2}+x_{j+\frac n2+1}+⋯+x_{j+n-1}),$$where $x_{n+k}=x_k$ for $k=1,2,\cdots,n-1$.

This identity looks interesting, which comes from one of my students. I think is right, but I am unable to prove it.

When $n=2$, $$\text{LHS}=\sum_{1\le i<j\le 2}\min(|2-1|,2-|2-1|)x_{i}x_{j}=x_{1}x_{2},\\\text{RHS}=x_{1}x_{2}.$$ When $n=4$, $$\text{LHS}=x_{1}x_{2}+2x_{1}x_{3}+x_{1}x_{4}+x_{2}x_{3}+2x_{2}x_{4}+x_{3}x_{4},\\\text{RHS}=\sum_{j=1}^{2}(x_{j}+x_{j+1})(x_{j+2}+x_{j+3})=(x_{1}+x_{2})(x_{3}+x_{4})+(x_{2}+x_{3})(x_{4}+x_{1})=\text{LHS}.$$

Answer 1

Let's compare the coefficient of $x_ix_j$ on both sides. On the LHS it's the distance between i and j in $Z/(nZ)$ On the RHS it's the number of ways of dividing $Z/nZ$ into two disjoint intervals of equal length such that one contains i and the other j. These are clearly the same number.

Answer 2

We set $n=2N$ and show for integral $N\geq 1$

\begin{align*} \sum_{j=1}^N&\left(x_j+\cdots+x_{j+N-1}\right)\left(x_{j+N}+\cdots+x_{j+2N-1}\right)\\ &=\sum_{1\leq i<j\leq 2N}\min(|i-j|,2N-|i-j|)x_ix_j\\ \\ &\text{where } x_{2N+k}=x_k\text{ for }k=1,\ldots,2N-1\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{j=1}^N}&\color{blue}{\left(x_j+\cdots+x_{j+N-1}\right)\left(x_{j+N}+\cdots+x_{j+2N-1}\right)}\\ &=\sum_{j=1}^N\left(x_j+\cdots+x_{j+N-1}\right)\\ &\qquad\quad\cdot\left(\left(x_{j+N}+\cdots+x_{2N}\right)+\left(x_{2N+1}+\cdots+x_{j+2N-1}\right)\right)\\ &=\sum_{j=2}^N\left(x_1+\cdots x_{j-1}\right)\left(x_j+\cdots+x_{j+N-1}\right)\\ &\qquad+\sum_{j=1}^N\left(x_j+\cdots+x_{j+N-1}\right)\left(x_{j+N}+\cdots+x_{2N}\right)\tag{2}\\ &=\sum_{j=2}^N\left(x_1+\cdots x_{j-1}\right)\left(x_j+\cdots+x_{j+N-1}\right)\\ &\qquad+\sum_{j=1}^N\left(x_j+\cdots+x_N\right)\left(x_{j+N}+\cdots+x_{2N}\right)\\ &\qquad+\sum_{j=1}^N\left(x_{N+1}+\cdots+x_{j+N-1}\right)\left(x_{j+N}+\cdots+x_{2N}\right)\tag{3}\\ &=\sum_{k=1}^{N-1}x_k\left(\sum_{l={k+1}}^{N+k}x_l+\sum_{l={k+2}}^{N+k+1}x_l+\cdots+\sum_{l=N}^{2N-1}x_l\right)\\ &\qquad+\sum_{k=1}^Nx_k\left(\sum_{l={N+1}}^{2N}x_l+\sum_{l=N+2}^{2N}x_l+\cdots+\sum_{l=N+k}^{2N}x_l\right)\\ &\qquad+\sum_{k={N+1}}^{2N-1}x_k\left(\sum_{l={k+1}}^{2N}x_l+\sum_{l={k+2}}^{2N}x_l+\cdots+\sum_{l={2N}}^{2N}x_l\right)\tag{4}\\ &=\sum_{k=1}^{N-1}x_k\left(\left(\sum_{l={k+1}}^{N+k}x_l+\sum_{l={k+2}}^{N+k}x_l+\cdots+\sum_{l=N}^{N+k}x_l\right)\right.\tag{5}\\ &\qquad\qquad+\left.\left(\sum_{l={N+k+1}}^{N+k+1}x_l+\sum_{l={N+k+1}}^{N+k+2}x_l+\cdots+\sum_{l=N+k+1}^{2N-1}x_l\right)\right)\tag{6}\\ &\qquad+\sum_{k=1}^{N-1}x_k\left(\left(\sum_{l={N+1}}^{N+k}x_l+\sum_{l=N+2}^{N+k}x_l+\cdots+\sum_{l=N+k}^{N+k}x_l\right)\right.\tag{7}\\ &\qquad\qquad+\left.\left(\sum_{l={N+k+1}}^{2N}x_l+\sum_{l=N+k+1}^{2N}x_l+\cdots+\sum_{l=N+k+1}^{2N}x_l\right)\right)\tag{8}\\ &\qquad+x_N\left(\sum_{l=N+1}^{2N}x_l+\sum_{l=N+2}^{2N}x_l+\cdots+\sum_{l=2N}^{2N}x_l\right)\tag{9}\\ &\qquad+\sum_{k=N+1}^{2N-1}x_k\sum_{j=k+1}^{2N}(j-k)x_j\tag{10}\\ &=\sum_{k=1}^{N-1}x_k\sum_{j=k+1}^{N+k}(j-k)x_j\tag{11}\\ &\qquad+\sum_{k=1}^{N-1}x_k\sum_{j=N+k+1}^{2N}(2N-j+1)x_j\tag{12}\\ &\qquad+\sum_{k=1}^{N-1}x_k\sum_{j=N+k+1}^{2N}(k-1)x_j\tag{13}\\ &\qquad+x_N\sum_{j=N+1}^{2N}(j-N)x_j\tag{14}\\ &\qquad+\sum_{k=N+1}^{2N-1}x_k\sum_{j=k+1}^{2N}(j-k)x_j\\ &=\sum_{k=1}^{N}x_k\sum_{j=k+1}^{N+k}(j-k)x_j\tag{15}\\ &\qquad+\sum_{k=1}^{N-1}x_k\sum_{j=N+k+1}^{2N}(2N-j+k)x_j\tag{16}\\ &\qquad+\sum_{k=N+1}^{2N-1}x_k\sum_{j=k+1}^{2N}(j-k)x_j\\ &=\sum_{{1\leq k<j\leq 2N}\atop{j\leq N+k}}(j-k)x_kx_j+\sum_{{1\leq k<j\leq 2N}\atop{N+k<j}}(2N-j+k)x_kx_j\\ &=\sum_{{1\leq k<j\leq 2N}\atop{|k-j|\leq N}}(j-k)x_kx_j+\sum_{{1\leq k<j\leq 2N}\atop{|k-j|>N}}(2N-j+k)x_kx_j\\ &\,\,\color{blue}{=\sum_{1\leq k<j\leq 2N}\min(|k-j|,2N-|k-j|)x_kx_j} \end{align*}

and the claim follows.

Comment:

• In (2) we use (1).

• In (3) we split the second sum of (2).

• In (4) we reorder the three sums of (3) by using the distributivity of sums. Think of fixing the $k$-th term of the left-hand product and sum the elements of the right-hand product. Then sum over $k$.

• In (5) to (8) we split the sums the first two sums.

• In (9) we extract the term with index $k=n$.

• In (10) we collect equal terms of (4).

• In (11) we collect equal terms of (5) and (7).

• In (12) we collect equal terms of (6).

• In (13) we collect equal terms of (8).

• In (14) we collect equal terms of (9).

• In (15) we add (11) and (14).

• In (16) we add (12) and (13).