Fourier Series of $f(x) = x^n$ - Fast Method? Is there a fast way to compute the real Fourier series of 
$$f(x) = x^n \ ?$$
How about the complex fourier series?
If there isn't a fast way for arbitrary $n$, how about $n = 5$ or something at least?
It takes me like half an hour to compute it for something like $x^3$, is it supposed to be this painful or are there tricks?
 A: Yes, by induction. I'll do the complex Fourier series on $(0,2\pi)$.
Let $c_n(k)$ be the $n$th coefficient of $x^k$. It's easy to get $c_0( k)=(2\pi)^k/(k+1)$, so the rest of computations is about $c_n(k)$ with $n\ne 0$.
Integrate by parts:
$$\begin{split}c_n(k) &= \frac{1}{2\pi}\int_0^{2\pi} x^k e^{-inx}\,dx
\\&=  -\frac{(2\pi)^{k-1}}{in} + \frac{k}{in}\frac{1}{2\pi}\int_0^{2\pi} x^{k-1} e^{-inx}\,dx \\& = -\frac{(2\pi)^{k-1}}{in} + \frac{k}{in}c_n(k-1)\end{split} \tag{1}$$
To make (1) easier to work with, introduce 
$$b_n(k)=(in)^{k} c_n(k) \tag{2}$$
Then simplify (1) into
$$  b_n(k) = - (2\pi in)^{k-1} + k b_n(k-1)   \tag{3}$$
Use (3) repeatedly, starting with the trivial $b_n(0)=0$  (recall that $n\ne 0$ throughout this computation). After a few steps you will
see the pattern 
$$  b_n(k) = - k! \sum_{j=0}^{k-1} \frac{(2\pi in)^j}{(j+1)!} \tag{4}$$
 Hence, 
$$c_n(k) = 
- \frac{k!}{(in)^k} \sum_{j=0}^{k-1} \frac{(2\pi in)^j}{(j+1)!} \tag{5}$$
Of course, once you have (5), you can  prove it by induction from (1) without intermediate steps. 
Example with $k=3$: 
$$c_n(3) = 
- \frac{6}{(in)^3} \left( 1 + \pi in - \frac{ (2\pi n)^2}{6}\right)$$
