= Solution
Let $\omega=e^{2\pi i/N}$. Using the convention
$$
\widehat x_k=\sum_{n=0}^{N-1}x_n\omega^{-kn},
\qquad 0\leq k<N,
$$
the <discrete Fourier transform> of the supplied sequence follows from the <binomial theorem>:
$$
x_n=\frac1N\sum_{m=0}^{N-1}\binom{N-1}{m}\omega^{mn}.
$$
The <orthogonality of roots of unity> gives
$$
\sum_{n=0}^{N-1}\omega^{(m-k)n}
=\begin{cases}N,&m=k,\\0,&m\ne k.\end{cases}
$$
Since $m,k$ both lie between zero and $N-1$, it follows that
$$
\boxed{\widehat x_k=\binom{N-1}{k}},
\qquad k=0,\ldots,N-1.
$$
Back to article page
