Solution
= Solution
The radix-two <Fast Fourier transform> recursively applies part (a) until it reaches one-point transforms, then combines adjacent even and odd transforms in butterfly operations. For $n=8$, the decomposition tree is
$$
\mathcal F_8^{-1}
\longrightarrow2\mathcal F_4^{-1}
\longrightarrow4\mathcal F_2^{-1}
\longrightarrow8\mathcal F_1^{-1},
$$
followed by the reverse sequence of twiddle-factor butterfly combinations. This is the usual three-stage FFT network.