$ \sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos{\left(\frac{2\pi}{M}kj\right)}=-M/2 $

Question

I'm trying to proof something right now. What exactly is not important. I was able to break down the whole thing to the following equation.

$ \sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos{\left(\frac{2\pi}{M}kj\right)}=-M/2 $

This should hold for all even values of $M\in\mathbb{N}$. Any ideas? I tried to substitute both summation by a single one, but that yields to a big mess....

I checked it in Mathematica with different values of $M$.

Answer 1

Change to exponential notation. Let $j$ be fixed and let $d=\gcd(j,M).$ Then $$\sum_{k=1}^{M-1} \exp(2\pi i j k/M)$$ adds up some $M$-th roots of unity. If you were to increase the upper limit to $M$, then you'd be adding all the $M/d$-th roots of unity $d$ times, which adds to $0$. So: $$\sum_{k=1}^{M-1} \cos(2\pi j k/M) = \Re\left(\sum_{k=1}^{M-1} \exp(2\pi i j k/M)\right)$$ $$= \Re\left(\sum_{k=1}^{M} \exp(2\pi i j k/M) -\exp(2\pi i jM/M)\right) = \Re(0 - 1) = -1.$$ And that should make the outer sum easy.

Answer 2

First, We know that $$ \cos x = \frac{e^{ix}+e^{-ix}}{2}$$

Now assume $$ x = \frac{2\pi ji}{M} $$

We can rewrite given expression as

$$ \sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M}) = \sum_{j=1}^{M/2}\sum_{k=1}^{M-1} \frac{e^{xk}+e^{-xk}}{2}$$

Let us first try to find value of $$ \sum_{k=0}^{M-1} \frac{e^{xk}+e^{-xk}}{2} $$ Notice that in your expression $k$ is starting from $1$ but it is starting from $zero$ now.

$$ \sum_{k=0}^{M-1} \frac{e^{xk}+e^{-xk}}{2} = \frac{1}{2}(\frac{e^{xM}-1}{e^x-1} - \frac{e^{-xM}-1}{e^x-1})$$

If with put the value of $ x=\frac{2\pi ji}{M} $ in $ e^{xM} $ we get $$ e^{xM} = e^{\frac{2\pi ji}{M}M} = e^{2\pi ji} = 1$$ Similarly $$ e^{-xM} = 1 $$

And therefore $$ \sum_{k=0}^{M-1}\cos(\frac{2\pi kj}{M}) = \sum_{k=0}^{M-1} \frac{e^{xk}+e^{-xk}}{2} = 0 = 1 + \sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M})$$

$$ \Rightarrow \sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M}) = -1 $$

Hence, $$ \sum_{j=1}^{M/2}\sum_{k=1}^{M-1}\cos(\frac{2\pi kj}{M}) = \sum_{j=1}^{M/2}-1 = \frac{-M}{2}$$

Answer 3

When $j<M$, $kj\bmod M$ is a permutation of the integers $0,1,\cdots M-1$.

Then by cancellatoin of the quadrants, $$\sum_{k=0}^{M-1}\cos\frac{2\pi kj}{M}=0$$ and

$$\sum_{k=1}^{M-1}\cos\frac{2\pi kj}{M}=-1.$$

The claim trivially follows.