几何级数

概述

几何级数 是每一项与前一项之比为常数的级数，在递归树分析中广泛用于求和计算。

定义

几何级数（等比级数）

形如 ${\sum }_{i=0}^{k-1}a{r}^i=a+ar+a{r}^2+\cdots +a{r}^{k-1}$ 的级数，其中 $a$ 为首项，$r$ 为公比。

当 $r\ne 1$ 时，其封闭形式为：

${\sum }_{i=0}^{k-1}a{r}^i=a\cdot \frac{1-r^k}{1-r}$

当 $|r|<1$ 且 $k\to \infty$ 时，无穷几何级数收敛于 $a/(1-r)$。

核心性质

• 求和公式：封闭形式 $a(1-r^k)/(1-r)$ 是递归分析中最常用的恒等式之一
• 收敛性：$|r|<1$ 时无穷级数收敛，$|r|\ge 1$ 时发散
• 递归树应用：递归树的每一层贡献常构成几何级数，利用求和公式可快速得到总代价

章节扩展

第4章：递归树法中，每层的工作量常形成几何级数。例如递归关系 $T(n)=2T(n/2)+n$ 的递归树中，各层代价 $n,n,n,\dots$ 虽非严格几何级数，但更复杂的关系如 $T(n)=3T(n/4)+c{n}^2$ 中，层代价 $c{n}^2,\frac{3}{16}c{n}^2,\frac{9}{256}c{n}^2,\dots$ 构成公比 $r=3/16$ 的几何级数。

参见

• 4.4 递归树法 — 几何级数在递归树求和中的核心应用