Lagrange interpolation and Inverse Discrete Fourier Transform This question was given to me in my numerical analysis course, while we study Lagrange interpolation.
Question: Let $\zeta=e^{2{\pi}i/n}$ root of unity of order $n$, and $f(x)$ a polynomial with degree $n-1$.
Show that, if $\hat{f}=\sum^{n-1}_{k=0} f(\zeta^k)x^k$ $\quad\text{then}\quad$ $f(x)=\frac{1}{n}\sum^{n-1}_{k=0}\hat{f}(\zeta^{-k})x^k$
My Attempt:
\begin{align}
\frac{1}{n}\sum^{n-1}_{k=0}\hat{f}(\zeta^{-k})x^k=\ \frac{1}{n}\sum^{n-1}_{k=0} \left(\sum^{n-1}_{m=0}f(\zeta^m)\zeta^{-km} \right)x^k=\\\frac{1}{n}\sum^{n-1}_{m=0}\sum^{n-1}_{k=0} f(\zeta^m)
(\zeta^{-m}x)^k= \sum^{n-1}_{m=0}f(\zeta^m)\left(\frac{1}{n}\sum^{n-1}_{k=0} (\zeta^{-m}x)^k\right)\\
\end{align}
now, we know that $\zeta^{-m}=e^{-2{\pi}im/n}$ so if m=n we get $\zeta^{-m}=1$, therefore:
\begin{align}
\frac{1}{n}\sum^{n-1}_{k=0} (\zeta^{-m}x)^k=\frac{1}{n}\sum^{n-1}_{k=0} (e^{-2{\pi}im/n}x)^k=
\frac{1}{n}\sum^{n-1}_{k=0} x^k=\frac{1}{n}\frac{x^n-1}{x-1}
\end{align}
combing the above we get
\begin{align}
\sum^{n-1}_{m=0}f(\zeta^m)\left(\frac{1}{n}\sum^{n-1}_{k=0} (\zeta^{-m}x)^k\right)=\sum^{n-1}_{m=0}f(\zeta^m)\frac{1}{n}(x^{n-1}+...+x+1)
\end{align}
on the other hand, when $m{\neq}n$ we get:
\begin{align}
\frac{1}{n}\sum^{n-1}_{k=0} (\zeta^{-m}x)^k=\frac{1}{n}\sum^{n-1}_{k=0} (e^{-2{\pi}im/n}x)^k=
\frac{1}{n}\frac{x^n-1}{\zeta^{-m}x-1}
\end{align}
I don't know how to proceed from here. I remember that in the proof of IDFT we got $\delta_{ij}$ so I thought I should get $\delta_{mn}$ or something similar but it doesn't seem that way. Moreover, I can't see any way to get $f(x)$, all I have is $f(\zeta^m)$.
Thanks in advance!
 A: This seem like the convolution definition and why it returns a circular convolution, maybe you can use the approach in Lecture Notes for EE 261 The Fourier Transform and its Applications, page 267 and 275. The last step because of the peridicity of the complex exponential term, could be solve using:
$\displaystyle 1+z+z^{2}+\cdots+z^{N-1}=\left\{\begin{array}{ll}\frac{1-z^{N}}{1-z} & z \neq 1 \\ N & z=1\end{array}\right.$
if $z=\omega$ then
$\displaystyle 1+\omega+\omega^{2}+\ldots+\omega^{N-1}=\frac{1-\omega^{N}}{1-\omega}=\frac{0}{1-\omega}=0$
if $k$ in not an integer multiple of $N$ so that $\omega^k \neq 1 $ while $\omega^{kN}=1$
then
$\displaystyle 1+\omega^{k}+\omega^{2 k}+\ldots \omega^{(N-1) k}=\frac{1-\omega^{k N}}{1-\omega^{k}}=0$
while if $k$ is an integer multiple of $N$ then $\omega^{k}=1$ then
$\displaystyle 1+\omega^{k}+\omega^{2 k}+\ldots \omega^{(N-1) k}=1+1+\ldots+1=N$
$1+\omega^{k}+\omega^{2 k}+\cdots+\omega^{(N-1) k}=\left\{\begin{array}{ll}0 & k \neq 0 \bmod N \\ N & k \equiv 0 \bmod N\end{array}\right.$
This steps where taken from the lecture page 261
