7. 求和技巧
考虑下面这个简单的求和。
\[\sum_{i=1}^n i.\]
一个简单的 归纳证明
表明这个求和具有众所周知的闭式解
\(n(n+1)/2\)。
但是，虽然归纳法是证明某个提出的闭式表达式正确的好技巧，
我们一开始又如何找到要检验的候选闭式表达式呢？
让我们尝试从基本原理出发来思考这个问题，
就像我们以前从未见过它一样。
开始分析一个求和时，一个好的起点是：对于给定的 \(n\)，
估算它的值。
观察这个求和的最大项是 \(n\)，
而被累加的项数共有 \(n\) 个。
所以总和必须小于 \(n^2\)。
实际上，大多数项都远小于 \(n\)，
而且各项的大小线性增长。
如果我们用条形图来描绘各项的大小，
那么它们的高度会形成一条直线，我们可以把它们框在一个宽 \(n\)
单位、高 \(n\) 单位的盒子里。
由此容易看出，对这个求和更精确的估计约为 \((n^2)/2\)。
有这样一个估计在手边，会有助于我们确定精确的闭式解，
因为如果我们的候选解大错特错，我们希望可以识别出来。
现在让我们考虑一些方法，看看我们可能怎样想到这个求和的
闭式解的精确方程。
一个特别巧妙的方法是指出：我们可以把第一项和最后一项"配对"，
第二项与第 \(n-1\) 项配对，依此类推。
每一对的和都是 \(n+1\)。
对数是 \(n/2\)。
因此，解是 \(n(n+1)/2\)。
这很漂亮，而且毫无疑问是正确的。
问题在于它并不是对许多其他求和都有用的技巧。
现在让我们试着提出更通用一些的方法。
我们已经认识到，因为最大项是 \(n\) 并且
共有 \(n\) 项，所以这个求和小于 \(n^2\)。
如果我们幸运的话，闭式解是个多项式。
以此为工作假设，
我们可以调用一项称为 猜测与验证 的技巧。
我们猜测这个求和的闭式解是一个多项式。
这意味着我们猜测它具有
\(c_1 n^2 + c_2 n + c_3\) 的形式，其中 \(c_1\)、\(c_2\)
和 \(c_3\) 是常数。
如果这是真的，那么我们可以代入这个小求和小例子的答案
来解出这些系数。
对本例而言，把 0、1 和 2 代入 \(n\) 会导出
三个联立方程。
因为当 \(n=0\) 时求和只是 0，所以 \(c_3\) 必定
为 0。
对于 \(n=1\) 和 \(n=2\)，我们得到两个方程
\[\begin{split}\begin{eqnarray*}
c_1 + c_2 & = & 1 \\
4 c_1 + 2 c_2 & = & 3,
\end{eqnarray*}\end{split}\]
这依次给出 \(c_1 = 1/2\) 和 \(c_2 = 1/2\)。
因此，如果这个求和的闭式解 是 一个多项式，
那么它只能是
\[1/2 n^2 + 1/2 n + 0\]
通常写成
\[\frac{n(n+1)}{2}.\]
在这一点上，我们仍必须完成猜测与验证方法的"验证"部分。
我们可以使用归纳证明来验证我们的候选闭式解是否正确。
本例中它确实是正确的，如
示例 6.7.3 所示。
归纳证明是必要的，因为我们最初假设解是一个简单多项式
可能出错。
例如，真实解可能包含一个对数项，比如
\(c_1n^2 + c_2 n \log n\)。
这里展示的过程本质上是对固定数量的点拟合一条曲线。
因为总是存在一个 \(n\) 次多项式能拟合
\(n+1\) 个点，所以如果没有归纳证明，我们所做的工作
还不足以确信我们认识到了真正的方程。
只要解是多项式表达式，猜测与验证就是有用的。
特别是，类似的推理可以用来求解
\(\sum_{i=1}^n i^2\)，或更一般地对任意正整数 \(c\)
求解 \(\sum_{i=1}^n i^c\)。
为什么这不是求解求和的通用方法？
因为很多求和的闭式解并不是多项式。
一种更通用的方法建立在
减法猜测 或 除法猜测
策略之上。
减法猜测的一种形式被称为
平移法。
平移法把原求和减去该求和的一种变体。
被选来进行相减的变体应当能让大多数项相互抵消。
为求解和 \(f\)，我们选取一个已知函数 \(g\)，并在
\(f(n) - g(n)\) 或 \(f(n)/g(n)\) 中寻找模式。
这是另一个例子。
