具体数学-第3课（递归式转化为求和求解）

原文链接：

今天讲了一种将递归式转化为求和的方法。

考虑如下递归式：

两边同时乘以 得到：

要想转化成可以求和的递归式，那么必须有：

也就是：

这时令

得到：

这时就可以转化为求和了，解出：

所以

例题1

设 个数快速排序的操作次数为 ，那么有

用 取代 可以得到

两式相减可以得到

由上面方法可以得到

所以

进而可以求出

这里介绍一个概念叫做调和级数：

所以

求和三大定律

结合律、分配率、交换律。这里就不展开说了，相信你们都知道的。
来两题简单的例题说明一下。

例题2

求

普通的方法每个人应该都会，等差数列嘛。这里用求和定律来做一做。
用 取代 ，得到

即

两式相加得到

所以

例题3

求

这里用到另一种求和的方法。
两边同时加上第 项，得到

所以

这里介绍另一种方法来求解。
令

求导得到

所以

同样可以得到