Translation of a certain proof of $(\sum k)^2 = \sum k^3 $

Solution 1:

Yes Christoph is on the right idea and there is some technical details involved here. Some FFTs normalize the sum to be $1/n$ and some don't and some normalize in a third way and so on, so I need to check which of these my local FFT actually does to be able to check myself. Anyway first of all we need a function to work with, and we choose the linear function below, basically $f(x) = x$ :

The theory behind this all is based on applying the convolution theorem of Fourier transforms:

$$\mathcal{F}(f^3) = \mathcal{F}(f)*\mathcal{F}(f)*\mathcal{F}(f)$$ together with the fact that for the frequency 0, the exponential factor becomes 1 and the fourier transform is a sum (or in the continous case an integral): $$\mathcal{F}(g)[0] = \sum_{k=1}^N g(k)$$ possibly times a factor, depending on normalization. This is what the left hand side amounts to. The right hand side is with the same reasoning $(\mathcal{F}(f)[0])^2$. Note the square is last so it is on the result of the sum.