数学杂记（技）

经典组合数求和等于斐波那契等式

\(\sum\limits_{i=0}^n \dbinom{n-i}{i}=f_{n+1}\)，其中 \(f\) 为斐波那契数列。

证法 \(1\)：

\(\sum\limits_{i=0}^n \dbinom{n-i}{i}=\sum\limits_{i=0}^n [x^i](1+x)^{n-i}=[x^n]\sum\limits_{i=0}^n x^{n-i}(1+x)^{n-i}=[x^n] \dfrac{1}{1-x-x^2}=[x^{n+1}] \dfrac{x}{1-x-x^2}=f_{n+1}\)

由斐波那契数列递推式易证其生成函数式 \(\dfrac{x}{1-x-x^2}\)。

证法 \(2\)：

考虑组合意义：\(f_{n+1}\) 表示选若干个 \(1\) 和 \(2\) 和为 \(n\) 的方案数。

枚举选取的数的个数 \(i\)，则接下来要在 \(i\) 个数中选 \(n-i\) 个数 \(+1\)，方案为 \(\dbinom{i}{n-i}\)。

于是 \(f_{n+1}=\sum\limits_{i=0}^n \dbinom{i}{n-i}=\sum\limits_{i=0}^n \dbinom{n-i}{i}\)。