官方证明太 Ad-hoc 了，在和 AI 的激烈交流下，得到基于留数定理的证明。
文中所有有理分式都需要约分并保证分母为首 $1$ 多项式。
定义：
- 极点：对于有理分式 $G(x)=\frac{A(x)}{B(x)}$，“极点”为分母的所有根；
- Laurent 展开：对函数 $f(x)$，定义 $f(x)$ 在 $a$ 处的 Laurent 展开为 $f(x)=\sum\limits_{n=-\infty}^{+\infty}c_n(x-a)^n$；
- 留数：函数 $f(x)$ 在极点 $a$ 处的 Laurent 展开式中，系数 $c_{-1}$ 称为 $f(x)$ 在 $a$ 处的留数，记作 $\operatorname{Res}(f,c)$。
公式：
- 连乘求导：若 $F(x)=(x-x_0)H(x)$，则 $F'(x_0)=H(x_0)$。
推论：
- 推论 1（单极点留数公式）：若 $a$ 为 $G(x)=\frac{A(x)}{B(x)}$ 的一阶极点（即 $a$ 不是 $B$ 的重根），则其留数可通过洛必达法则快速求得： $$\operatorname{Res}(G, a)=\frac{A(a)}{B'(a)}$$ 证明：$\operatorname{Res}(G, a)=\lim_{x\to a}(x-a)G(x)=\lim_{x\to a}\frac{(x-a)A(x)}{B(x)}=\frac{A(a)}{B'(a)}$。
- 推论 2（全局留数定理推论）：对于有理函数 $G(x)=\frac{A(x)}{B(x)}$，若分母最高次幂比分子最高次幂 至少大 2（即 $\deg(B) \ge \deg(A) + 2$），则 $G(x)$ 所有极点处的留数之和为 $0$。即： $$\sum_k \operatorname{Res}(G, x_k)=0$$ 无穷远处 Laurent 展开形式为 $\displaystyle\sum_{n=-\infty}^{\infty}c_nz^n$，易知此时 $c_{-1}=0$，则 $\operatorname{Res}(G,\infty)=0$，代入留数定理可证。
第一步：构造全局有理函数
考虑以 $f_i$ 为主元，观察到求和式中包含 $\prod_{j \ne i}(f_i - f_j)$，这启发我们定义全局多项式：
$$F(x) = \prod_{j=1}^n (x - f_j)$$
其导数在 $x = f_i$ 处的值恰好为分母：$F'(f_i) = \prod_{j \ne i} (f_i - f_j)$。
对于分子 $\prod_{j \ne i}(1 + f_i - f_i f_j)$，为了补齐 $j=i$ 的项以形成全局对称，我们乘上对应的因子 $(1 + f_i - f_i^2)$，并定义：
$$G(x) = \prod_{j=1}^n (1 + x - x f_j), H(x)=1+x-x^2$$
于是，原式可被改写为（每一项其实都是在 $f_i$ 处的极限）：
$$S=\sum_{i=1}^n\frac{G(f_i)}{H(f_i)F'(f_i)}$$
这自然地引导我们构造出如下辅助有理函数： $$P(x) = \frac{G(x)}{H(x)F(x)}$$
第二步：分析极点并计算留数
由于连乘求导性质，注意到 $H(f_i)F'(f_i)$ 其实是 $H(x)F(x)$ 在 $f_i$ 处导数，于是发现 $S$ 为一部分留数和，考虑利用留数定理。
函数 $G(x)$ 的分母包含两部分，对应两类极点，注意可能有高阶极点（分母有重根），导致无法裂项，但我们可以利用连续性微调 $f$，排除重根影响。
第一类极点：这些极点的和就是 $S$。
第二类极点：$x = \phi_1, \phi_2$，其中 $\phi$ 为 $x^2 - x - 1 = 0$ 的根。
$$ \begin{align*} \operatorname{Res}(P(x),\phi_1)&=\frac{G(\phi_1)}{-(\phi_1-\phi_2)F(\phi_1)} \\ &=-\frac{\prod\limits_{i=1}^n(1+\phi_1-\phi_1f_i)}{(\phi_1-\phi_2)\prod\limits_{i=1}^n(\phi_1-f_i)} \\ &=-\frac{\prod\limits_{i=1}^n(\phi_1^2-\phi_1f_i)}{(\phi_1-\phi_2)\prod\limits_{i=1}^n(\phi_1-f_i)} &(\phi_1^2-\phi_1-1=0\Rightarrow\phi_1+1=\phi_1^2) \\ &=-\phi_1^n\frac{\prod\limits_{i=1}^n(\phi_1-f_i)}{(\phi_1-\phi_2)\prod\limits_{i=1}^n(\phi_1-f_i)} \\ &=\frac{\phi_1^n}{\phi_2-\phi_1}=\frac{1}{\sqrt5}\left(\frac{1-\sqrt5}{2}\right)^n \\ \end{align*} $$
同理
$$\operatorname{Res}(P(x),\phi_2)=\frac{\phi_2^n}{\phi_1-\phi_2}=-\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n$$
第三步：应用全局留数定理求和
检查 $G(x)$ 的多项式度数： 分子 $A(x)$ 的最高次数为 $x^n$。 分母 $-(x^2 - x - 1)P(x)$ 的最高次数为 $x^{n+2}$。 满足 $\deg(\text{分母}) = \deg(\text{分子}) + 2$，由推论 2 可知所有极点的留数和为 $0$： $$\sum_{i=1}^n \operatorname{Res}(G, f_i) + \operatorname{Res}(G, \phi_1) + \operatorname{Res}(G, \phi_2) = 0$$
将第一部分替换为原式 $S$，移项可得： $$S = -\left( \operatorname{Res}(G, \phi_1) + \operatorname{Res}(G, \phi_2) \right) = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$$
此式正是斐波那契数列的 Binet 通项公式。
最终结论
$$\sum_{i=1}^n\prod_{j\ne i}\frac{1+f_i-f_if_j}{f_i-f_j} = F_n$$ （其中 $F_n$ 为斐波那契数列第 $n$ 项，定义 $F_1=1, F_2=1$）。该式的值是常数，与输入序列 $f_i$ 完全无关。
