求解递推关系有许多方法，这里我们简要考虑三种。第一种是估算技巧：猜测递推关系的上下界，用归纳法证明这些界，并按需要收紧。第二种方法是展开递推，把它转化成求和，然后使用求和技巧。第三种方法是在递推具有合适形式时，利用已被证明的定理。特别是，像归并排序这样典型的分治算法产生的递推符合一种模式，对这种模式我们有现成的解。
2.8.1.1. 估算上下界
求解递推的第一种方法是猜测答案，然后尝试证明它正确。如果给出了正确的上下界估算，一个简单的归纳证明就会验证这个事实。如果证明成功，那么尝试收紧界。如果归纳证明失败，那么放宽界再试一次。一旦上下界相符，你就完成了。当你只寻求渐近复杂度时，这是一种有用的技巧。当你寻求精确的闭式解（也就是说，你寻求表达式中的常数）时，这种方法可能工作量太大。
2.8.1.2. 展开递推
如果你只需要答案的近似值，估算界是有效的。
要找到精确解则需要更精确的技巧。
一种方法被称为 展开递推。
在这种方法中，方程右边较小的项
依次被它们的定义替换。
这就是展开步骤。
这些项再次被展开，依此类推，直到得到一个
不再含递推的完整级数。
这产生一个
求和
，然后就可以使用求解求和的方法。
2.8.1.3. 分治递推
求解递推的第三种方法是利用已知定理，这些定理为一类递推提供解。特别有实际用途的是一个给出 分治递推 类答案的定理。它们的形式为
\[{\bf T}(n) = a{\bf T}(n/b) + cn^k; \quad {\bf T}(1) = c\]
其中 \(a\)、\(b\)、\(c\) 和 \(k\) 是常数。一般来说，这个递推描述一个规模为 \(n\) 的问题被划分成 \(a\) 个规模为 \(n/b\) 的子问题，而 \(cn^k\) 是组合部分解所需的工作量。归并排序是分治算法的一个例子，其递推符合这种形式。二分查找也是。我们用展开递推的方法，假设 \(n = b^m\)，为任何分治递推推导出一般解。
\[\begin{split}\begin{eqnarray*}
{\bf T}(n) & = & a{\bf T}(n/b) + cn^k\\
& = & a(a{\bf T}(n/b^2) + c(n/b)^k) + cn^k\\
& = & a(a[a{\bf T}(n/b^3) + c(n/b^2)^k] + c(n/b)^k) + cn^k\\
& = & a^m{\bf T}(1) + a^{m-1}c(n/b^{m-1})^k + \cdots + ac(n/b)^k + cn^k\\
& = & a^mc + a^{m-1}c(n/b^{m-1})^k + \cdots + ac(n/b)^k + cn^k\\
& = & c\sum_{i=0}^{m} a^{m-i} b^{ik}\\
& = &ca^m\sum_{i=0}^{m} (b^k/a)^i.
\end{eqnarray*}\end{split}\]
下面是此同一推导的更直观的呈现。
所以，我们得到这样的结果：
\[{\bf T}(n) = ca^m\sum_{i=0}^{m} (b^k/a)^i.\]
在这一点上，注意到这一点是有用的：
\[\begin{eqnarray}
\label{ThmEquiv}
a^m = a^{\log_bn} = n^{\log_ba}.
\end{eqnarray}\]
这给出
\[{\bf T}(n) = c n^{\log_ba} \sum_{i=0}^{m} (b^k/a)^i.\]
这个方程的求和部分是一个等比数列，其和取决于比值 \(r = b^k/a\)。有三种情形。
\(r<1\)。
由模块
求和
的方程 (4) 有
\[\sum_{i=0}^{m} r^i < 1/(1-r),\ {\rm a~constant.}\]
因此，
\[{\bf T}(n) = \Theta(a^m) = \Theta(n^{log_ba}).\]
\(r=1\)。因为 \(r = b^k/a\)，我们知道 \(a = b^k\)。由对数的定义立刻可以推出 \(k = \log_b a\)。还要注意，既然我们定义了 \(n = b^m\)，那么 \(m = \log_b n\)。因此，
\[\sum_{i=0}^{m} r^i = m + 1 = \log_bn + 1.\]
因为 \(a^m = n^{\log_b a} = n^k\)，我们有
\[{\bf T}(n) = \Theta(n^{\log_ba}\log_b n) = \Theta(n^k\log_b n).\]
\(r>1\)。
由模块
求和
的方程 (5) 有
\[\sum_{i=0}^{m} r^i = \frac{r^{m+1} - 1}{r - 1} = \Theta(r^m).\]
因此，
\[{\bf T}(n) = \Theta(a^mr^m)
= \Theta(a^m(b^k/a)^m)
= \Theta(b^{km})
= \Theta(n^k).\]
我们可以把上述推导总结为下面的定理，有时被称为 主定理。
只要适用，就可以直接应用这个定理，而不必重新推导递推的解。
2.8.1.4. 快速排序的平均情况分析
在模块
快速排序
中，我们确定快速排序的平均情况分析具有下面的递推：
\[{\bf T}(n) = cn + \frac{1}{n}\sum_{k=0}^{n-1} [{\bf T}(k) +
{\bf T}(n -1 - k)], \qquad {\bf T}(0) = {\bf T}(1) = c.\]
\(cn\) 项是 findpivot 和 partition 步骤的一个上界。这个方程源于假设分区元素出现在任何位置 \(k\) 的可能性相等。通过观察两个递推项 \({\bf T}(k)\) 和 \({\bf T}(n - 1 - k)\) 是等价的，可以简化它，因为一个只是从 \(T(0)\) 往上数到 \(T(n-1)\)，另一个从 \(T(n-1)\) 往下数到 \(T(0)\)。这给出
\[{\bf T}(n) = cn + \frac{2}{n}\sum_{k=0}^{n-1} {\bf T}(k).\]
这种形式被称为 全历史递推。求解这种递推的关键是消去求和项。求和的平移法提供了一种办法。两边乘以 \(n\)，并从 \(n{\bf T}(n+1)\) 的公式中减去结果：
\[\begin{split}\begin{eqnarray*}
n{\bf T}(n) & = & cn^2 + 2 \sum_{k=1}^{n-1} {\bf T}(k)\\
(n+1){\bf T}(n+1) & = & c(n+1)^2 + 2 \sum_{k=1}^{n} {\bf T}(k).
\end{eqnarray*}\end{split}\]
两边减去 \(n{\bf T}(n)\) 得到：
\[\begin{split}\begin{eqnarray*}
(n+1){\bf T}(n+1) - n{\bf T}(n) & = & c(n+1)^2 - cn^2 + 2{\bf T}(n)\\
(n+1){\bf T}(n+1) - n{\bf T}(n) & = & c(2n+1) + 2{\bf T}(n)\\
(n+1){\bf T}(n+1) & = & c(2n+1) + (n+2){\bf T}(n)\\
{\bf T}(n+1) & = & \frac{c(2n+1)}{n+1} + \frac{n+2}{n+1}{\bf T}(n).
\end{eqnarray*}\end{split}\]
在这一点上，我们已经消除了求和，现在可以用我们求解递推的常规方法得到闭式解。注意 \(\frac{c(2n+1)}{n+1} < 2c\)，所以我们可以简化结果。展开递推，我们得到
\[\begin{split}\begin{eqnarray*}
{\bf T}(n+1) & \leq & 2c + \frac{n+2}{n+1} {\bf T}(n)\\
& = & 2c + \frac{n+2}{n+1}\left (2c +
\frac{n+1}{n}{\bf T}(n-1)\right )\\
& = & 2c + \frac{n+2}{n+1}\left (2c + \frac{n+1}{n}\left
(2c + \frac{n}{n-1}{\bf T}(n-2)\right )\right )\\
& = & 2c + \frac{n+2}{n+1}\left (2c + \cdots +
\frac{4}{3}(2c + \frac{3}{2}{\bf T}(1))\right )\\
& = & 2c\left (1 + \frac{n+2}{n+1}
+ \frac{n+2}{n+1}\frac{n+1}{n} + \cdots
+ \frac{n+2}{n+1}\frac{n+1}{n}\cdots\frac{3}{2}\right )\\
& = & 2c\left (1 + (n+2)\left (\frac{1}{n+1}
+ \frac{1}{n} + \cdots + \frac{1}{2}\right )\right )\\
& = & 2c + 2c(n+2)\left ({\cal H}_{n+1} - 1\right )\\
\end{eqnarray*}\end{split}\]
其中 \({\cal H}_{n+1}\) 是调和级数。
由模块
求和
的方程 (10)，
\({\cal H}_{n+1} = \Theta(\log n)\)，
所以最终解是 \(\Theta(n \log n)\)。
