和式以及递归式的求解

算法

---

和式

1. 和式简介
   和式，简而言之就是我们高中学的数列求和。等差数列以及等比数列求和我们可以直接套用公式，除此之外我们应该记住一些特殊的和式。

2. 常见和式
   1）算术级数

   $$\sum_{i=1}^ni = {n(n+1)\over2} = \Theta(n^2)$$
   2）平方和 $$\sum_{i=1}^n i^2 = {n(n+1)(2n+1)\over6} = \Theta(n^3)$$
   3）几何级数 $$\sum_{i=0}^nc^i=\sum_{i=0}^n {c^{n+1}-1\over c-1} = \Theta(c^n)$$

3. 求和的积分近似
   如果$sum_{i=1}^nf(i)$是一个单调序列，就可以通过积分来近似估计这个和式的值。

   　如果$f(i)$是单调递减的，那么:

   $$\int_m^n f(x) \,{\rm d}x \leq \sum_{i=m}^n f(i) \leq \int_{m-1}^n f(x)\,{\rm d}x$$
   　如果$f(i)$是单调递增的，那么: $$\int_m^n f(x) \,{\rm d}x \leq \sum_{i=m}^n f(i) \leq \int_m^{n+1} f(x)\,{\rm d}x$$

递推关系

1. 齐次方程求解
   $$f(n) = a_1f(n-1) + a_2f(n-2) + {\ldots} + a_kf(n-k)$$

一般都含有$f(n)=x^n$形式的特解，于是可用$x^n$来替换$f(n)$。
先看一下一阶齐次方程，

$$f(n) = af(n-1) = a^2f(n-2) = a^nf(0)$$
接着我们看二阶齐次方程， $$f(n) = af(n-1) + bf(n-2)$$

那么，特征方程就变成了，

$$x^2 = ax + b$$

可以解得方程有两个解$x_1,x_2$，当$x_1!=x_2$时，$f(n) = c_1{x_1}^n + c_2x_2^n$。否则，$f(n) = c_1x^n + c_2nx^n$
2. 非齐次方程求解
先来看两种比较简单的形式:

$$f(n) = f(n-1) + g(n) = f(0) + \sum_{i=1}^ng(i)$$

$$f(n) = g(n)f(n-1) = \prod_{i=1}^ng(i)\times f(0)$$

接下来介绍如何用待定系数法求解非齐次方程
假定我们有一个非齐次递推式：

$$f(n) = 2f(n-1) + n$$

第一步，求出齐次方程的通解，对应的齐次方程为

$$f(n) = 2f(n-1)$$

求得通解，

$$f(n) = 2^{n+1}$$

第二步，求特解。根据原方程是可以得出特解满足,

$$f(n) = An^2 + Bn +C$$

接下来将原式代入，

$$2[A(n-1)^2+B(n-1)^2+C]+C=An^2+Bn+C$$

通过待定系数求解$A,B,C$。

最后非齐次方程的解应为，

$$f(n) = 齐次方程通解 + 非齐次方程特解$$