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

原文链接：

具体数学-第3课 - WeiYang Bloggodweiyang.com

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

考虑如下递归式：

两边同时乘以

得到：

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

也就是：

这时令

得到：

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

所以

例题1

设

个数快速排序的操作次数为

，那么有

用

取代

可以得到

两式相减可以得到

由上面方法可以得到

所以

进而可以求出

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

所以

求和三大定律

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

例题2

求

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

取代

，得到

即

两式相加得到

所以

例题3

求

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

项，得到

所以

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

求导得到

所以

同样可以得到