I'm trying to understand the Fast Fourier Transform. On several articles I read, I found this formula for dividing polynomials into even and odd terms (example).
Given $ A(x)=a_0x^0+a_1x^1+⋯+a_{n−1} x^{n−1} $
When divided into even and odd terms,
$$ A(x)=A_0(x^2)+xA_1(x^2) $$
My question is, how did the $x^2$ come to be? Obviously, both versions give different answers when evaluated. So, what does it really mean?
I'm not very math savvy. So, please avoid as much jargon as possible :)
We are given \begin{aligned} A(x)&=a_0x^0+a_1x^1+\cdots+a_{n-1}x^{n-1}\\ A_0(x)&=a_0x^0+a_2x^1+\cdots+a_{n-2}x^{(n/2)-1}\\ A_1(x)&=a_1x^0+a_3x^1+\cdots+a_{n-1}x^{(n/2)-1}\\ \end{aligned}
We get \begin{aligned} A_0(x^2) &=a_0(x^2)^0+a_2(x^2)^1+\cdots+a_{n-2}(x^2)^{(n/2)-1}\\ &=a_0x^0+a_2x^2+\cdots+a_{n-2}x^{n-2}\\ \end{aligned}
Similarly, \begin{aligned} xA_1(x^2) &=x\left(a_1(x^2)^0+a_3(x^2)^1+\cdots+a_{n-1}(x^2)^{(n/2)-1}\right)\\ &=x\left(a_1x^0+a_3x^2+\cdots+a_{n-1}x^{n-2}\right)\\ &=a_1x^1+a_3x^3+\cdots+a_{n-1}x^{n-1}\\ \end{aligned}
Thus, $A(x)=A_0(x^2)+xA_1(x^2)$