写一些重要过程,其他忽略

$F(\omega_{n}^k)=FL(\omega^{k}_{n/2})+\omega_{n}^kFR(\omega_{n/2}^k)$

$F(\omega_{n}^{k+n/2})=FL(\omega^{2k+n}_n)+\omega_{n}^{k+n/2}FR(\omega_{n}^{2k+n})$

$~~~~~~~~~~~~~~~~~=FL(\omega_{n/2}^k)-\omega_{n}^{k}FR(\omega_{n/2}^k)$

$G(i)=\sum\limits_{k=0}^{n-1}(\omega_{n}^i)^kF[k]$

其中 $F[k]$ 是多项式系数,$G(i)$ 表示在 $x=\omega^i_{n}$ 的点值 $y$ 。

有结论:
$n*F[k]=\sum\limits_{i=0}^{n-1}(\omega_n^{-k})^iG(i)$

证明:

$\begin{aligned}\sum\limits_{i=0}^{n-1}(\omega_n^{-k})^iG(i)&=\sum\limits_{i=0}^{n-1}(\omega_n^{-k})^i\sum\limits_{j=0}^{n-1}(\omega_{n}^i)^j F[k]\\&=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\omega_{n}^{i(j-k)}F[k]\end{aligned}$

$j-k=0$ 时,为 $n*F[k]$

$j-k\ne 0$ 时,为$ \sum\limits_{j-k=1}^{n-1}\omega_{n}^{j-k}\sum\limits_{i=0}^{n-1}\omega_{n}^iF[k]$

由于 $\sum\limits_{i=0}^{n-1}\omega_{n}^i=0$ ,故得证。