2.6. 求和技巧
考虑下面这个简单的求和。
\[\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}.\]
在这一点上，我们仍必须完成猜测与验证方法的"验证"部分。我们可以使用归纳证明来验证我们的候选闭式解是否正确。本例中它确实是正确的，如示例 2.2.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)\) 中寻找模式。
这是另一个例子。
