好像有点用又好像没什么用的求和小寄巧

· · 算法·理论

累加法推广

已知 a_{n+1}=a_{n}+f(n)（f(n) 已知）和 a_1，求 \{a_n\} 的通项公式。

显然改写成 a_{n+1}-a_n=f(n) 就可以转化为 f(n) 求和了，非常简单。

已知 a_{n+1}=pa_n+f(n)（f(n),p 已知）和 a_1，求 \{a_n\} 的通项公式。

这个可以尝试构造 a_{n+1}+g(n+1)=p[a_n+g(n)] 然后用等比数列相关内容，但是还有一种做法：

pa_{n}-p^2a_{n-1}=pf(n-1)\\ \dots\\ p^{n-1}a_2-p^n=p^{n-1}f(1)

所以如果 f(n) 在乘上等比数列后好求和，那么累加法也是可以做的（例如 f(n) 是多项式或指数函数，多项式乘等比不会求和请出门左转 Gosper 算法）。

求导的妙用

求导，可以帮助我们把等差数列弄到指数上去，方便组合数或等比数列相关求和，例如：

已知 a_n=(kn+b)q^n（k,b,q 已知，q 不等于 1），求前 n 项和 S_n。

设：

f(x)=\sum_{i=1}^nx^{ki+b}q^i

根据等比数列求和公式可知：

f(x)=\frac{x^{k+b}q(x^{kn}q^n-1)}{x^kq-1}

显然 S_n=f'(1)。

求 \sum_{i=1}^niC_n^ip^i(1-p)^i。（二项分布的期望）

设 f(x)=\sum_{i=1}^nx^iC_n^ip^i(1-p)^{n-i}，这是二项式定理的形式，易知 f(x)=(px+1-p)^n，原式等于 f'(1)=np。（这也即是概率母函数求导。）