反演随记

零、反演的本质

$$A\vec{x} = \vec{y} \iff B\vec{y} = \vec{x}$$

其中 \(\vec{x}, \vec{y}\) 为列向量，\(A, B\) 为任意矩阵。所以反演的证明即证明 \(A, B\) 互逆，可以通过带入一组特殊的 \(\vec{x_0}, \vec{y_0}\) 满足 \(A\vec{x_0} = B\vec{y_0}\) 证明。

一、二项式反演

$$f_i = \sum_{j = 0}^i \binom{i}{j} g_j \iff g_i = \sum_{j = 0}^i (-1)^j \binom{i}{j} f_j$$

$$f_i = \sum_{j = i}^n \binom{j}{i} g_j \iff g_i = \sum_{j = i}^n (-1)^{j - i} \binom{j}{i} f_j$$

证明：对于形式一，带入 \(f_i = 1, g_j = [j = 0]\)，根据二项式定理显然成立。对于形式二，考虑其矩阵为形式一的转置，同样互逆。