定义

如果我们知道\(\{ f_n \}, \{ g_n \}\)有这种情况时：

\[ f_n = \sum_{i = 0}^n a_{ni} g_i \]

那么我们就可以用已知的\(f_0, f_1, \dots, f_n\)的值来求出\(g_n\)：

\[ g_n = \sum_{i = 0}^n b_{ni} f_i \]

上面这种求值方式叫做反演。

反演条件

我们先列出上面的式子：

\[ \begin{aligned} g_n &= \sum_{i = 0}^n b_{ni} f_i \\ &= \sum_{i = 0}^n b_{ni} \sum_{j = 0}^i a_{ij} g_j \\ &= \sum_{i = 0}^n b_{ni} \sum_{j = 0}^n a_{ij} g_j [j \leq i] \\ &= \sum_{i = 0}^n g_i \sum_{j = i}^n a_{ji} b_{nj} \end{aligned} \]

很显然，我们可以发现反演成立，当且仅当：

\[ \sum_{j = i}^n a_{ji} b_{nj} = [i = n] \]

这就是反演的条件。