The Danielson-Lanczos lemma states that the discrete Fourier transform of length 
(where 
is even) can be rewritten as
the sum of two discrete Fourier transforms,
each of length 
.
One is formed from the even-numbered points; the other
from the odd-numbered points. Denote the 
th point of the discrete
Fourier transform by 
. Then
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
where 
and 
.
This procedure can be applied recursively to break up the 
even and odd points to their
even and odd points. If
is a power of 2, this procedure breaks up the original
transform into 
transforms of length 1. Each transform of an individual point has 
for some 
. By reversing the patterns of evens and odds, then letting
and 
,
the value of 
in binary is produced. This is the basis for the fast
Fourier transform.
