The "magic step" is simply an algebraic observation. I'll use python/scipy notation, since HN has no latex.
Let f = [ f1, f2, ..., fN] be the sequence you want to take the DFT of (has size N = power of 2). Let x = arange(0,N) = [0,1,...,N]. More numpy notation: exp(x) = [exp(0), exp(1), ..., exp(N)], and x * y = [x1 * y1, x2 * y2, ..., xN * yN].
The DFT of f can be written as:
F[k] = sum( exp(2 pi i k x /N) * f) = sum( exp(2 pi i k x /N)[0::2] * f[::2]) + sum( exp(2 pi i k x /N)[1::2] * f[1::2])
I.e., all I did was break up the sum into a sum over the odd indices and the even indices. The second sum can be rewritten as exp(2 pi i / N) sum(exp(2 pi i k x /N)[0::2] * f[1::2]) .
So we've now written F[k] as a sum of two DFT's: the DFT over the odd indices and the DFT over the even indices. Each of these DFT's has size N/2.
That's the divide step, now you just conquer by working down recursively.
Let f = [ f1, f2, ..., fN] be the sequence you want to take the DFT of (has size N = power of 2). Let x = arange(0,N) = [0,1,...,N]. More numpy notation: exp(x) = [exp(0), exp(1), ..., exp(N)], and x * y = [x1 * y1, x2 * y2, ..., xN * yN].
The DFT of f can be written as:
I.e., all I did was break up the sum into a sum over the odd indices and the even indices. The second sum can be rewritten as exp(2 pi i / N) sum(exp(2 pi i k x /N)[0::2] * f[1::2]) .So we've now written F[k] as a sum of two DFT's: the DFT over the odd indices and the DFT over the even indices. Each of these DFT's has size N/2.
That's the divide step, now you just conquer by working down recursively.