Past exam of the mathematics course of the University of Cambridge / 2019 / ib / Paper 3 / 7D / Solution

Let $\omega =e^{2\pi i/N}$. Using the conventionthe discrete Fourier transform of the supplied sequence follows from the binomial theorem:The orthogonality of roots of unity givesSince $m,k$ both lie between zero and $N-1$, it follows that