A basis for the DFT can be found in the following identity about $n$-th roots of unity $\zeta_k$, the sequence of which $(\zeta_k)$ builds for all $k\in\mathbb Z,$ an $n$-periodical complex sequence.

Lemma: Sum of Roots Of Unity in Complete Residue Systems

For any positive integer $n > 0,$ the sum of $n$ consecutive $n$-th roots of unity equals $0.$

$$\sum_{k=0}^{n-1}\zeta_k=\sum_{k=0}^{n-1}\exp\left(2\pi i\frac {k}n\right)=0.$$

This result is only a special case for the complete residue system represented by the numbers $k=\{0,1,\ldots,n-1\}.$ By introducing a factor $(a-b)$ for arbitrary integers $a,b\in\mathbb Z,$ we have $$\sum_{k=0}^{n-1}\exp\left(2\pi i\frac {(a-b)k}n\right)=\begin{cases}n&\text{ if }a(n)\equiv b(n)\\0&\text{else.}\end{cases}$$

Proofs: 1


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Butz, T.: "Fouriertransformation für Fußgänger", Teubner, 1998