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 series 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 development
has its coefficients equal to zero, since the integrated function is
periodic, hence all its 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_{N−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 its Fourier series, 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 its value in c_n:
c_n=    
c_{m}ω_{N}^{km}ω_{N}^{−kn} 
If m≠ n (mod N ), ω_{N}^{m−n} is an 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 indexes
(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)
Then :
x={2,sqrt(2)/2,1,(sqrt(2)/2,0,(sqrt(2))/2,1,sqrt(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/8,c_{3}=0.0,
c_{−4}=0.0,c_{−3}=0.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.