Danielson-Lanczos Lemma

G. C. Danielson and C. Lanczos, ``Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids'', J. Franklin Inst. 233, 365 (1942).

For even $n = 2 m$:

$$\begin{eqnarray*} X_k &=& \sum_{j=0, {\rm even}}^{n-1} \omega_n^{k j} x_j + \sum... ... + \omega_n^k \sum_{j'=0}^{m-1} \omega_m^{k j'} x_{j'}^{\rm odd} \end{eqnarray*}$$

since $\omega_n^{2 k} = \omega_{n/2}^k$ and writing $x_k^{\rm even} = x_{2 k}$ and $x_k^{\rm odd} = x_{2 k + 1}$.