show this nice trigonometric identiy

Question

I was working on a book, which was asking me to prove that some product is equal to nn. I had reduced the problem to proving a trigonometric identity, but I couldn't prove it although I spent much time on it. Then, I checked the solution, and it solves the problem with a quite different approach that doesn't even enter to trigonometric expressions at all. But, still, this nice identity that I hadn't encountered before must be true then! I was wondering if people can think of a direct proof for that?

Show this following identity: $$\sum_{i=1}^{n-1}\left\{\left(\cos{\frac{2\pi}{n}}-\cos{\dfrac{2\pi i}{n}}\right)\left[\left(\sum_{j=1}^{n}x_{j}\cos{\dfrac{2ij\pi}{n}}\right)^2+\left(\sum_{j=1}^{n}x_{j}\sin{\dfrac{2ij\pi}{n}}\right)^2\right]\right\} $$$$=\left(1-\cos{\dfrac{2\pi}{n}}\right)\left(\sum_{i=1}^{n}x_{j}\right)^2+n\cos{\dfrac{2\pi}{n}}\sum_{i=1}^{n}x^2_{i}-n\sum_{i=1}^{n}x_{i}x_{i+1},$$ where $x_{i}\in \Bbb R$ and $x_{n+1}=x_{1}.$

Answer 1

This is an application of the Plancherel-Parseval identities of the isometry properties of the Fourier transform, here in finite dimension. Essentially, a properly scaled variant of the discrete Fourier transform is unitary.

One comes to the use of the Fourier transform as the second factor on the left side is the norm square of components of the discrete Fourier transform (DFT). Using the convention for the forward DFT $$ \hat x_m=\sum_{k=1}^nx_k\exp\left(-i\frac{2km\pi}{n}\right) =\sum_{k=1}^nx_k\cos\left(\frac{2km\pi}{n}\right) -i\sum_{k=1}^nx_k\sin\left(\frac{2km\pi}{n}\right) \tag{DFT} $$ the mentioned isometry is $$ n\langle {\bf x},{\bf y}\rangle =\langle {\bf \hat x},{\bf \hat y}\rangle. \tag{ISO} $$

The defining term in the claimed identity is the last one, which can be interpreted as scalar product of ${\bf x}$ with a shifted copy. Let $S$ be the left-shift operator, $(Sx)_i=x_{i+1}$, $(Sx)_n=x_1$, then the Fourier coefficients of it are $$ \widehat{(Sx)}_m =\sum_{k=1}^nx_{k+1}\exp\left(-i\frac{2km\pi}{n}\right) =\sum_{k=1}^nx_{k}\exp\left(-i\frac{2(k-1)m\pi}{n}\right) =\exp\left(i\frac{2m\pi}{n}\right)\,\hat x_m \tag1 $$ Thus we get for this last term $$ n\sum_{k=1}^nx_kx_{k+1}=n\langle {\bf x},S{\bf x}\rangle =\langle {\bf \hat x},\widehat{S{\bf x}}\rangle =\sum_{m=1}^n\cos\left(\frac{2m\pi}{n}\right)\,\left|\hat x_m\right|^2 \tag2 $$ This proves the non-trivial part of the claim.

---

All that remains is some window-dressing, essentially removing the outer terms of the last sum by using the identities $$ n\sum_{k=1}^nx_k^2=n\langle {\bf x},{\bf x}\rangle =\langle {\bf \hat x},{\bf \hat x}\rangle =\sum_{m=1}^{n-1}\left|\hat x_m\right|^2+\left(\sum_{k=1}^nx_k\right)^2 \tag3 $$ and $\hat x_0=\hat x_n=\sum_{k=1}^n x_k$.

In total the claimed identity is \begin{align} &\sum_{m=1}^{n-1}\left(\cos\left(\frac{2\pi}{n}\right)-\cos\left(\frac{2m\pi}{n}\right)\right)\,\left|\hat x_m\right|^2 \\ &=\cos\left(\frac{2\pi}{n}\right)\sum_{m=1}^{n-1}\left|\hat x_m\right|^2 -\sum_{m=1}^{n-1}\cos\left(\frac{2m\pi}{n}\right)\,\left|\hat x_m\right|^2 \\ &=\cos\left(\frac{2\pi}{n}\right)\left(\|\hat{\bf x}\|^2-|\hat x_n|^2\right) -\left(\langle {\bf \hat x},\widehat{S{\bf x}}\rangle-\left|\hat x_n\right|^2\right) \\ &=n\cos\left(\frac{2\pi}{n}\right)\sum_{k=1}^nx_k^2 +\left(1-\cos\left(\frac{2\pi}{n}\right)\right)\left(\sum_{k=1}^nx_k\right)^2 -n\sum_{k=1}^nx_kx_{k+1} \tag4 \end{align}

Answer 2

It is easy to check that moving the first summand from the right hand side of the equality to its left hand side, we simplify it to $X=Y$, where

$$X=\sum_{i=1}^{n}\left(\cos{\dfrac{2\pi}{n}}-\cos{\dfrac{2\pi i}{n}}\right) \left[\left(\sum_{j=1}^{n}x_{j}\cos{\dfrac{2ij\pi}{n}}\right)^2+\left(\sum_{j=1}^{n}x_{j}\sin{\dfrac{2ij\pi}{n}}\right)^2\right]$$

and $$Y=n\cos{\dfrac{2\pi}{n}}\sum_{i=1}^{n}x^2_{i}-n\sum_{i=1}^{n}x_{i}x_{i+1}.$$

We have $$\left(\sum_{j=1}^{n}x_{j}\cos{\dfrac{2ij\pi}{n}}\right)^2+\left(\sum_{j=1}^{n}x_{j}\sin{\dfrac{2ij\pi}{n}}\right)^2=$$ $$\sum_{j=1}^{n}\sum_{k=1}^{n} x_jx_k\left(\cos{\dfrac{2ij\pi}{n}}\cos{\dfrac{2ik\pi}{n}}+\sin{\dfrac{2ij\pi}{n}}\sin{\dfrac{2ik\pi}{n}}\right)=$$ $$\sum_{j=1}^{n}\sum_{k=1}^{n} x_jx_k\cos \dfrac{2i(j-k)\pi}{n}.$$

Thus

$$X=\sum_{i=1}^{n}\left(\cos{\frac{2\pi}{n}}-\cos{\dfrac{2\pi i}{n}}\right)\sum_{j=1}^{n}\sum_{k=1}^{n} x_jx_k\cos \dfrac{2i(j-k)\pi}{n}=$$ $$\sum_{j=1}^{n}\sum_{k=1}^{n} x_jx_k \sum_{i=1}^{n}\left(\cos{\frac{2\pi}{n}}-\cos{\dfrac{2\pi i}{n}}\right) \cos \dfrac{2i(j-k)\pi}{n}.$$

Put $S_1=\sum_{i=1}^{n}\cos \dfrac{2i(j-k)\pi}{n}$. That is, $S_1$ is the $x$-coordinate of the sum $S_1’$ of an indexed family $\mathcal S=\left\{\left(\cos \dfrac{2i(j-k)\pi}{n}, \sin\dfrac{2i(j-k)\pi}{n}\right): i:=1\dots n\right\}$ of unit vectors. If $j=k$ then $\cos \dfrac{2i(j-k)\pi}{n}=1$ for each $i$, so $S_1=n$. Otherwise it is easy to that rotation of the plane $\Bbb C$ by $\dfrac{2(j-k)\pi}{n}$ with the center at the origin induces a permutation of the vectors of the family $\mathcal S$. Thus $S’=S’\cdot \left(\cos \dfrac{2(j-k)\pi}{n},\sin\dfrac{2(j-k)\pi}{n}\right) $, which is possible only if $S_1’=0$.

We have $$\sum_{i=1}^{n}\cos \dfrac{2\pi i}{n}\cos \dfrac{2i(j-k)\pi}{n}=S’_2+S’’_2,$$ where $$S_2’=\sum_{i=1}^{n}\frac 12\cos \dfrac{2i(j+1-k)\pi}{n}$$ and $$S_2’’=\sum_{i=1}^{n}\frac 12\cos \dfrac{2i(j-k-1)\pi}{n} .$$

Similarly to the above, we have $S_2’=n/2$, if $j+1-k=0\pmod n$ and $S_2’=0$, otherwise. Also $S_2’’=n/2$, if $j-1-k=0\pmod n$ and $S_2’’=0$, otherwise.

Taking the above into account, we obtain

$$X=\sum_{j=1}^{n} n\cos{\frac{2\pi}{n}}x_j^2-n\sum_{j=1}^{n} x_jx_{j+1}=Y.$$