1\documentclass{article}
 2\begin{document}
 3
 4The Fast Fourier Transform (FFT) is a fast method for evaluating the complex exponential sum,
 5
 6\begin{displaymath}
 7X_n = \sum_{j=0}^{N-1} x_k W^{nk} \quad n = 0 \ldots N-1
 8\end{displaymath}
 9
10in \begin{math} O(n \: lg \: n) \end{math} operations where \begin{math} W = e^{-2 \pi i / N} \end{math}
11is an nth root of unity and the symbol i denotes \begin{math} \sqrt {-1} \end{math}
12and N is a power of 2:  \begin{math}N = 2^g \end{math}.
13
14Express the summation indices in binary, 
15
16\begin{displaymath}
17n = 2^{g-1} n_{g-1} + 2^{g-2} n_{g-2} + \ldots + n_0
18\end{displaymath}
19
20\begin{displaymath}
21k = 2^{g-1} k_{g-1} + 2^{g-2} k_{g-2} + \ldots + k_0
22\end{displaymath}
23
24to expand the sum into
25
26\begin{displaymath}
27X(n_{g-1}, n_{g-2}, \ldots, n_0 ) = 
28\sum_{k_0=0}^1 \: \sum_{k_1=0}^1\ldots \sum_{k_{g-1}=0}^1 \quad x(k_{g-1}, k_{g-2}, \ldots , k_0) W^{nk}
29\end{displaymath}
30
31Expand out the complex exponential term
32
33\begin{eqnarray}
34W^{n k} = 
35W^{(2^{g-1} n_{g-1} + \ldots + n_0) (2^{g-1}k_{g-1})} \times \nonumber \\
36W^{(2^{g-1} n_{g-1} + \ldots + n_0) (2^{g-2}k_{g-2})}  \times \ldots \times \nonumber \\
37W^{(2^{g-1} n_{g-1} + \ldots + n_0) (k_0)} \nonumber
38\end{eqnarray}
39
40Simplify using
41
42\begin{displaymath}
43W^{(m 2^g)} = W^{mN} = (W^N)^m = 1^m = 1
44\end{displaymath}
45
46using
47
48\begin{displaymath}
49W^N = (e^{2 \pi i / N})^N = e^{2 \pi i}=1
50\end{displaymath}
51
52which gives us,
53
54\begin{displaymath}
55W^{n k} = 
56W^{ (n_0) (2^{g-1}k_{g-1})} 
57W^{(2 n_1 + n_0) (2^{g-2}k_{g-2})}  \ldots 
58W^{(2^{g-1} n_{g-1} + \ldots + n_0) (k_0)}
59\end{displaymath}
60
61Substitute back into the sum to give
62\begin{displaymath}
63\sum_{k_0=0}^1 \: \sum_{k_1=0}^1\ldots \sum_{k_{g-1}=0}^1 \quad x(k_{g-1}, k_{g-2}, \ldots , k_0)
64W^{ (n_0) (2^{g-1}k_{g-1})} 
65W^{(2 n_1 + n_0) (2^{g-2}k_{g-2})} 
66W^{(2^{g-1} n_{g-1} + \ldots + n_0) (k_0)}
67\end{displaymath}
68
69\end{document}