Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2 / 39A / 4

For $y=(1,1,-1,-1)$, the even and odd subsequences are both $(1,-1)$ and each length-two inverse discrete Fourier transform is $(0,2)$. Since ${\omega }_4=i$, the FFT butterfly givesFor $y=(1,-1,1,-1)$, the even transform is $(2,0)$ and the odd transform is $(-2,0)$. The same assembly gives