初二的时候想到的魔怔东西

· · 算法·理论

& x^n\\ =& (x-1+1)^n\\ =& \sum\limits_{i=0}^n\dbinom{n}{i}(x-1)^i\\ =& \sum\limits_{i=0}^n\dbinom{n}{i}\sum\limits_{j=0}^i(-1)^{i-j}\dbinom{i}{j}x^j\\ =& \sum\limits_{i=0}^n\sum\limits_{j=0}^i(-1)^{i-j}\dbinom{n}{i}\dbinom{i}{j}x^j\\ \end{aligned}

比较两边 x^n 的系数，发现应该有 [j=n]=\sum\limits_{i=0}^n\sum\limits_{j=0}^i(-1)^{i-j}\dbinom{n}{i}\dbinom{i}{j}。我们通过二项式定理 + GF 的技巧就推出了二项式反演结论。