离散傅里叶逆变换（IDFT）公式的证明方法问询
Hey，我注意到你在研究傅里叶级数和DFT算法，现在正卡在证明IDFT公式的环节，而且已经自己尝试用归纳法推进了，这点真的很赞！我来帮你梳理下思路，结合你已经做的尝试，再给你补全最通用的标准证明路径~
首先先明确你的问题背景：
你提到根据DFT的定义，对于长度为N的序列$(x_n){n=0,...,N-1}$（N≥1，元素可以是实数或复数），它的离散傅里叶变换序列$(y_n){n=0,...,N-1}$满足：
$$y_n=\sum_{k=0}{N-1}x_ke{-\frac{2\pi i}{N}kn} \quad \forall n=0,...,N-1$$
现在你要证明对应的逆变换公式：
$$x_n=\frac{1}{N}\sum_{k=0}{N-1}y_ke{\frac{2\pi i}{N}kn}$$
你已经尝试用归纳法入手，这点思路没问题：
- N=1的情况确实 trivial：此时DFT就是$y_0 = x_0e{0}=x_0$，代入逆变换公式直接得到$x_0=\frac{1}{1}y_0e0=y_0$，完全成立。
- N=2的情况你已经写出了矩阵形式：
$$\begin{pmatrix} y_0 \ y_1\end{pmatrix}=\begin{pmatrix}1 & 1\ 1 & -1 \end{pmatrix}\begin{pmatrix}x_0 \ x_1\end{pmatrix}$$
其实这里直接求DFT矩阵的逆矩阵就行——这个矩阵的逆矩阵是$\frac{1}{2}\begin{pmatrix}1 & 1\ 1 & -1 \end{pmatrix}$，两边乘逆矩阵就能得到：
$$\begin{pmatrix}x_0 \ x_1\end{pmatrix}=\frac{1}{2}\begin{pmatrix}1 & 1\ 1 & -1 \end{pmatrix}\begin{pmatrix}y_0 \ y_1\end{pmatrix}$$
展开后就是N=2时的IDFT公式，完美验证。
不过要推广到任意N的话，归纳法其实不是最直观的路径，利用正交性引理的方法才是证明IDFT的标准操作，步骤更直接也更通用：
首先我们需要用到这个关键的正交性结论：对于任意整数m、n，有
$$\sum_{k=0}{N-1}e{\frac{2\pi i}{N}k(m-n)} = \begin{cases}
N, & \text{当 } m \equiv n \pmod{N} \
0, & \text{其他情况}
\end{cases}$$
这个引理很好证：
- 当m≡n mod N时，每一项都是$e^0=1$，N项加起来自然是N；
- 当m≠n mod N时，这是首项为1、公比为$q=e^{\frac{2\pi i}{N}(m-n)}$的等比数列（q≠1，因为m-n不是N的倍数），求和公式是$\frac{1-qN}{1-q}$，而$qN=e^{2\pi i(m-n)}=1$，分子为0，所以和为0。
接下来我们把DFT的定义直接代入IDFT公式的右边，一步步推导到左边的$x_n$：
把$y_k = \sum_{l=0}^{N-1}x_l e^{-\frac{2\pi i}{N}lk}$代入$\frac{1}{N}\sum_{k=0}^{N-1}y_k e^{\frac{2\pi i}{N}kn}$：
$$
\begin{align*}
\frac{1}{N}\sum_{k=0}^{N-1}y_k e^{\frac{2\pi i}{N}kn} &= \frac{1}{N}\sum_{k=0}^{N-1}\left( \sum_{l=0}^{N-1}x_l e^{-\frac{2\pi i}{N}lk} \right) e^{\frac{2\pi i}{N}kn} \
&= \frac{1}{N}\sum_{l=0}^{N-1}x_l \sum_{k=0}{N-1}e{\frac{2\pi i}{N}k(n-l)} \quad \text{（交换求和顺序，这一步在复序列下是合法的）}
\end{align*}
$$
然后应用刚才的正交性引理：
只有当l=n时，内层的求和结果是N；其他所有l≠n的情况，内层求和都是0。所以上面的式子就只剩下l=n的那一项：
$$
\frac{1}{N}x_n \cdot N = x_n
$$
这样就完美推导出了IDFT的公式，和我们要证明的结论完全一致。
如果你特别想用归纳法继续推进，其实可以参考FFT的分治思路，把N分解成更小的因子（比如偶数N分成两个N/2长度的序列），但步骤会比正交性方法繁琐不少，还是后者更高效~
备注：内容来源于stack exchange，提问作者Steppenwolf
