Danielson-Lanczos 引理

長度為 (其中 為偶數) 的離散傅立葉變換可以被重寫為兩個離散傅立葉變換的和，每個變換的長度為 。一個由偶數編號的點構成；另一個由奇數編號的點構成。將離散傅立葉變換的第 個點表示為 。則

			(1)
			(2)
			(3)

其中 且 。此過程可以遞迴應用，將 個偶數和奇數點分解為它們各自的 個偶數和奇數點。如果 是 2 的冪，此過程將原始變換分解為 個長度為 1 的變換。單個點的每個變換都具有 ，對於某個 。透過反轉偶數和奇數的模式，然後令 和 ，可以得到 的二進位制值。這是快速傅立葉變換的基礎。