关注公众号【算法码上来】，每日算法干货马上就来！
今天讲了一种将递归式转化为求和的方法。
考虑如下递归式：
<!–swig0–>
两边同时乘以$s_n$得到：
<!–swig2–>
要想转化成可以求和的递归式，那么必须有：
<!–swig3–>
也就是：
<!–swig4–>
这时令
<!–swig5–>
得到：
<!–swig6–>
这时就可以转化为求和了，解出：
<!–swig7–>
所以
<!–swig8–>
例题1
设$n$个数快速排序的操作次数为$C_n$，那么有
<!–swig11–>
用$n-1$取代$n$可以得到
<!–swig14–>
两式相减可以得到
<!–swig15–>
由上面方法可以得到
<!–swig16–>
所以
<!–swig17–>
进而可以求出
<!–swig18–>
这里介绍一个概念叫做调和级数：
<!–swig19–>
所以
<!–swig20–>
求和三大定律
结合律、分配率、交换律。这里就不展开说了，相信你们都知道的。
来两题简单的例题说明一下。
例题2
求
<!–swig21–>
普通的方法每个人应该都会，等差数列嘛。这里用求和定律来做一做。
用$n-k$取代$k$，得到
<!–swig24–>
即
<!–swig25–>
两式相加得到
<!–swig26–>
所以
<!–swig27–>
例题3
求
<!–swig28–>
这里用到另一种求和的方法。
两边同时加上第$n+1$项，得到
<!–swig30–>
所以
<!–swig31–>
这里介绍另一种方法来求解。
令
<!–swig32–>
求导得到
<!–swig33–>
所以
<!–swig34–>
同样可以得到
<!–swig35–>
