Fourier series
Let f be a periodic function of period 2π, such that
f(x_{k})=y_{k}, x_{k}=   , k=0..N−1 
Suppose that the Fourier serie of f converges to f (this will
be the case if for example f is continuous). If N is large,
a good approximation of f will be given by:
Hence we want a numeric approximation of
The numeric value of the integral ∫_{0}^{2π}f(t)exp(−int)dt may be
computed by the trapezoidal rule
(note that the Romberg algorithm would not work here,
because the Euler Mac Laurin developpement
has it’s coefficients equal to zero, since the integrated function is
periodic, hence all it’s derivatives have the same value at 0 and at 2π).
If c_n is the numeric value of c_{n} obtained by the
trapezoidal rule, then
c_n=     y_{k}exp(−2i   ),
−   ≤ n<   
Indeed, since x_{k}=2kπ/N and f(x_{k})=y_{k}:
f(x_{k})exp(−inx_{k})  =  
 =  y_{0}=y_{N} 

Hence :
[c_{0},..c   ,c   ,..c_{−1}]=
  F_{N}([y_{0},y_{1}...y_{(N−1)}]) 
since

if n≥0, c_{n}=y_{n}
 if n<0 c_{n}=y_{n+N}
 ω_{N}=exp(2iπ/N),
then ω_{N}^{n}=ω_{N}^{n+N}
Properties

The coefficients of the trigonometric polynomial that interpolates f
at x=2kπ/N are
 If f is a trigonometric polynomial P of degree m≤ N/2,
then
f(t)=P(t)=   c_{k}exp(2ikπ t) 
the trigonometric polynomial that interpolate f=P is P, the numeric
approximation of the coefficients are in fact exact (c_{n}=c_{n}).
 More generally, we can compute c_{n}−c_{n}.
Suppose that f is equal to it’s Fourier serie, i.e. that :
f(t)=   c_{m}exp(2iπ mt),
  c_{m}<∞ 
Then :
f(x_{k})=f(   )=y_{k}=   c_{m}ω_{N}^{km},
c_n=    y_{k}ω_{N}^{−kn} 
Replace y_{k} by it’s value in c_n:
c_n=    
c_{m}ω_{N}^{km}ω_{N}^{−kn} 
If m≠ n (mod N ), ω_{N}^{m−n} is a Nth root of unity different
from 1, hence:
ω_{N}^{(m−n)N}=1,   ω_{N}^{(m−n)k}=0 
Therefore, if m−n is a multiple of N (m=n+l· N) then
∑_{k=0}^{N−1}ω_{N}^{k(m−n)}=N, otherwise
∑_{k=0}^{N−1}ω_{N}^{k(m−n)}=0.
By reversing the two sums, we get
c_n  =  
 =  
 =  ...c_{n−2· N}+c_{n−N}+c_{n}+c_{n+N}+c_{n+2·
N}+..... 

Conclusion: if n<N/2, c_n−c_{n} is a sum of c_{j} of large indices
(at least N/2 in absolute value), hence is small (depending on the
rate of convergence of the Fourier series).
Example, input
f(t):=cos(t)+cos(2*t)
x:=f(2*k*pi/8)$(k=0..7)
Output :
x={2,(√2)/2,1,((√2)/2),0,((√2)/2),1,(√2)/2}
fft(x)=[0.0,4.0,4.0,0.0,0.0,0.0,4.0,4.0]
After a division by N=8, we get
c_{0}=0,c_{1}=4.0/8,c_{2}=4.0/2,c_{3}=0.0,
c_{−4}=0,c_{−3}=0,c_{−2}=4.0/8,=c_{−1}=4.0/8
Hence b_{k}=0 and a_{k}=c_{−k}+c_{k} is equal to 1 if k=1,2 and 0 otherwise.