I was looking at the Fast-Fourier Transformation today, on this site [if you cannot read Russian, simply use Google Translate, which is what I am doing right now].
http://e-maxx.ru/algo/fft_multiply
In the section titled "Fast Fourier Transformation" [starting with "Fast Fourier Transform (fast Fourier transform) - a method to calculate the DFT of the time..."], the article states that:
$$A_0(x)=a_0 x^0+a_2 x^1+\dots+a_{n-2}x^{n/2-1}$$ $$A_1(x)=a_1 x^0+a_3 x^1+\dots+a_{n-1}x^{n/2-1}$$ From this, we get:
$$A(x)=A_0(x^2)+x A_1(x^2)$$ Now this is where my question comes in... the article says that:
$$y_k=y_{{0}{k}}+w_{{n}{k}}y_{{k}{1}}$$
Again, see the article for better formatting, this is the best I can do on stackoverflow.
My question is, where did the $x^2$ in $A_0(x^2)$ and $A_1(x^2)$ go?
Clearly, we should have:
$$DFT(A(x))=DFT(A_0(x^2))+w_nDFT(A_1(x^2))$$ However, from there, the $x^2$ seems to have disappeared... my question is, where has it gone?