Danielson-Lanczos Lemma

The Discrete Fourier Transform of length $N$ (where $N$ is Even) can be rewritten as the sum of two Discrete Fourier Transforms, each of length $N/2$. One is formed from the Even-numbered points; the other from the Odd-numbered points. Denote the $k$th point of the Discrete Fourier Transform by $F_n$. Then

$F_n=\sum_{k=0}^{N-1} f_ke^{-2\pi i nk/N}$
$= \sum_{k=0}^{N/2-1} e^{-2\pi ikn/(N/2)} f_{2k}+W^n\sum_{k=0}^{N/2-1} e^{-2\pi ikn/(N/2)} f_{2k+1} = F_n^e+W_nF_n^o,$

where $W\equiv e^{-2\pi i/N}$ and $n=0, \ldots, N$. This procedure can be applied recursively to break up the $N/2$ even and Odd points to their $N/4$ Even and Odd points. If $N$ is a Power of 2, this procedure breaks up the original transform into $\lg N$ transforms of length 1. Each transform of an individual point has $F_n^{eeo\cdots} = f_k$ for some $k$. By reversing the patterns of evens and odds, then letting $e=0$ and $o=1$, the value of $k$ in Binary is produced. This is the basis for the Fast Fourier Transform.

See also Discrete Fourier Transform, Fast Fourier Transform, Fourier Transform

References

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in C: The Art of Scientific Computing. Cambridge, England: Cambridge University Press, pp. 407-411, 1989.