I have came across this equality while reading a paper but can't figure out why this holds. For a given $N \in \mathbb{N}$, which is a power of 2, and $k,k' <N$. and $k,k' \in \mathbb{N}.$
$$\frac{1}{N}\sum_{j=0}^{N-1} e^{2\pi ij(k-k')/N} = 0$$
if $k \neq k'$. Does somebody sees why this holds?
It's a geometric progression, so you could explicitly compute it (and find that it's $0$) if you want. Note that this does not depend on $N$ being a power of $2$, but instead just that $N > 1$.
Alternately, this is the average of the $N$th roots of unity. These are equispaced around the unit circle, and their average is the center of the unit circle, which is $0$.
Alternately, this is a sum of each of the additive characters on $\mathbb{Z}/N\mathbb{Z}$ (or, if $(k - k')$ divides $N$, some multiple of the sum of additive characters on a subgroup of $\mathbb{Z}/N\mathbb{Z}$), and is thus zero. This is closely related to the following proof.
Call $\exp(2\pi i m (k - j') / N) = \psi(m)$. Note that $\psi(n)\psi(m) = \psi(n+m)$ from properties of exponentials. Note also that $\psi(n) = \psi(n + mN)$ for any $m$, since $e^{2\pi i} = 1$. Finally, note that the map $(\mathbb{Z}/N\mathbb{Z},+) \longrightarrow (\mathbb{Z}/N\mathbb{Z},+)$ given by addition by $m$ (i.e. $j \mapsto j + m$) is a bijection (with inverse subtracting by $m$).
Call $$S = \sum_{0 \leq j \leq N-1} \psi(j).$$ Since $k - k' \neq 0$, there is some $m$ so that $\psi(m) \neq 1$. Of course $\| \psi(m) \| = 1$, but $\psi(m) \neq 1$. Multiply $S$ by $\psi(m)$ to get $$\psi(m) S = \psi(m) \sum_{0 \leq j \leq N-1} \psi(j) = \sum_{0 \leq j \leq N-1} \psi(j + m) = \sum_{0 \leq \ell \leq N-1} \psi(\ell).$$ The last equality comes from the fact that $j+m$ covers all the residue classes mod $N$, so reordering we get them all. (This is a rephrasing of the bijection noted above).
So $S = \psi(m) S$, but $\psi(m) \neq 1$. Thus $S = 0$.
This is the other standard proof, and this generalized so sums of characters on finite groups.