Danielson-Lanczos 引理

长度为 (其中 为偶数) 的离散傅里叶变换可以被重写为两个离散傅里叶变换的和，每个变换的长度为 。一个由偶数编号的点构成；另一个由奇数编号的点构成。将离散傅里叶变换的第 个点表示为 。则

			(1)
			(2)
			(3)

其中 且 。此过程可以递归应用，将 个偶数和奇数点分解为它们各自的 个偶数和奇数点。如果 是 2 的幂，此过程将原始变换分解为 个长度为 1 的变换。单个点的每个变换都具有 ，对于某个 。通过反转偶数和奇数的模式，然后令 和 ，可以得到 的二进制值。这是快速傅里叶变换的基础。