第二章我们把目光放在很常用但很少详细叙述其技巧的和式上，也就是形如
这两种都表示相同的内容，前一种在连加符号上部分写出上界，下部分写出下界，称其为有确定界限的形式；后一种在连加符号下部分给出角标的取值范围，使用两个小于或小于等于号，称其为关系形式。
在具体使用中，当陈述一个问题或者表述一个结论时，倾向于使用带有确定界限的形式；而当我们处理一个需要对角标变换的和式时，为避免出错，倾向于使用关系形式。

注意本章的计算技巧很多，虽然不需要深刻的数学基础，但反而更考察灵光一现的观察能力

为了能够在表述时方便，规定形如[条件判断的内容]有类似于
对，如果为假，则项等于零
比如对小于N的全部素数倒数和可以写作：

而上一章我们讲过的成套方法正适合处理这样的形式，我们已经知道了形如
的递推式如何通过成套方法求出的值，然后将对应的带入求出最终结果。

而这里如果的系数如果不为1，该如何处理呢？
也就是说形如的递归式，该怎么处理？

其实我们可以通过一个求和因子来乘以两边：

这个求和因子需要巧妙选择，使得

如果我们记，则上面式子可化为

所以问题的关键在于找到合适的，观察，则对于，有，我们将这个式子递归的计算下去，可以得到
当然这个值的常数倍显然也符合我们对的要求

通常情况下，我们选择将其等号两边除以，将其化作

而的通项公式是比较好求的，

但其实这种方法需要我们对不同情况灵活的构思出计算得思路，而使用上文介绍的方式，可以从更高层面上，作出解答。比如这个递归式中为{1,1,...,1}，为{2,2,...,2}，故可以计算出，与上面的方法相比只是常数系数的区别。

下面介绍一个复杂的例子

快速排序是计算机数据排序中极其重要的方法，其算法描述和复杂度分析详见算法导论第七章内容。这里我们把关注点放在n个随机排列的数组使用快速排序时，其平均比较次数的计算。其递推式如下

这个递推式显然很复杂，它包含一个对前面所有值求和的和式，同时还要除以n，即便我们尝试列出前面多项的值试图寻找规律，但还是会一头雾水。为解决这个问题，首要就得把连加符号给消去，观察一下两个变换，首先使得等号两边乘以
令式1的，然后式1减去式2，有

根据这个式子我们可以得到简洁的多的的递推式：
显然这跟上文具有相同的形式。此处的为，为，于是有

而对于，我们用调和级数符号表示，于是最终可以化为

和式有以下几个基本性质

通过分配率，可以将常数移入和移出；通过结合律，可以将一个中的内容分为多个部分，或者多个部分合并为一个；通过交换律，可以按照任意方式来重新将内的内容排序

比如一个等差数列的一般和
交换律使得我们可以用代替，有

最后使用分配率将系数提取出来（注意这里系数与无关）

对应于我们所知的等差数列求和公式，即首项加末项乘以项数，除以2。

理解了上述三个基本性质之后，在看一看以下几个性质。

在使用艾弗森约定的情况下，加入分配率，交换律，结合律时有如下性质：
如果是整数的任意集合，则有

而通过这项性质我们就可以改写

而类似这种和式间的变形是扰动法的基础

其思想就是对一个未知的和式记为
我们写出，然后通过将其第一项与最后一项分离出来的结果进行对照
只要我们对最后那个和式做一些处理，使其能够通过表示出来，则可以得到一个方程，方程的解就是我们要求的的值

例如我们通过扰动法求解几何级数

这个例子比较简单，再看一个难一些的

再把这种情况做个推广，我们把底数2用作替换，有，使用扰动法可得

有趣的是，使用与现在完全不同的方法——微积分的初等技巧来推导也能得出完全相同的结论：
如果从方程入手，在其两边对求导，可得
显然和式的导数等于其各项导数之和，可以发现离散数学和微积分间有着紧密的联系。

下面介绍令初学者头疼的多重和式
这样表示没什么问题，但如果分别在不同的取值范围内，这样书写过于臃肿，通过艾弗森约定我们改变其书写方式
是间要满足的关系，显然交换求和次序不改变其结果

下面是一个特殊但很有用的技巧

对于集合，我们选择合适的使得满足下式

这种两个和式上下限间有函数关系的式子我们称为复杂型和式，而没有函数关系的称为简易型和式

对这个技巧我们举个例子，例如由个乘积组成的阵列

如果我们想要求这个阵列的上三角部分的和（包括对角线），记作
由于阵列元素关于对角线对称，即
所以显然等于下三角部分的和记作，且有

也就是说和式的下界中交换的大小顺序，不改变结果，故有恒等式

显然后面的和式为0，将第一个和式展开为4个简易型和式

将以上我们求出的等式化简并整理得
跟有名的切比雪夫不等式联系起来
发现切比雪夫不等式仅仅是我们求出的等式的特例

注意到单个和式由交换律有：
如果是一个双射，则是一一对应的关系，后面和式值为1
如果是一个非单射，如下图所示，则显然中4,5映射到的值就需要计算两次了，此时并没有更好的化简方式，非满射同理

所以在是之间的双射这一特殊情况下，我们有：

下面是一个综合性的例子，计算

显然这是一个调和级数的和式形式，到这一步就很难继续化简了
同样的，如果我们对求和，也会遇到上面相同的问题

现在我们换一种思路，将替换为，原式可以化为

利用这两次运算的结果，也就是说

从这个例子中我们可以得到一个技巧，如果有一个包含的二重和式，用替换，并对求和更方便。上个例子中就是通过，将带入，这样和式就变成了关于的和式，对求和后，剩余一个关于的和式，而其实我们发现仅仅是代数替换，所以将剔除，沿用作为代数表示（显然此时其意义发生变化）

在上面介绍了众多示例与常见性质后，我们看一下通常情况下，和式计算有多少种通用方法。

以一个很常见的和式，代表前个正整数平方和为例

其实，当我们令，显然有

• 直观来说，积分可以认为是x轴与曲线围成的面积（显然我们讨论的情况不包含曲线在x轴下方）

  
  

由图中可得，我们需要计算的多个矩形的面积和，可以近似的认为是图中曲线与x轴围成的面积，即
利用这一事实，如果我们需要精准的计算出误差从而计算出准确的的值，设误差为
然后我们通过这个递推式求出，继而求出

从简单的和式过渡到二重的复杂和式，然后再寻求机会将其化简，看似是让问题更麻烦了，但就像登山一样，想要攀登到顶点，在过程中免不了要走几段下坡路。

• 方法6：有限微积分：本部分内容过多，在下一节讲解
• 方法7：生成函数：这是组合数学一种很重要的工具，后面的笔记会重点讲

这是导数的基本定义，也是微积分的基础
所定义的查分算子的性质，查分算子是微分的有限模拟，相当于限制了只能取正整数值，那么也就是我们能达到的极限，而也就是时，的值

微积分中，显然，但有限微积分中，比如
其结果并无特定规律可循

但有一类特殊的m次幂，可以在有限微积分中做出形式优美的变换，而这也是有限微积分的意义所在。这类函数如下表示
m下面有一条下划线表示m个因子是向下递减的，读作“x直降m次”，也称为下降阶乘幂；同样的如果m上方有一条上划线，就表示m个因子是向上递增的，读作“x直升m次”，也称为上升阶乘幂

事实上，我们刚才规定的两种形式都与阶乘有紧密联系
这是一个媲美微积分幂函数微分公式的结果。

我们知道通过微积分第二定理，下面两个式子可以相互转化，其中称为对的不定积分
在有限微积分中，参考微积分的定义，我们规定

是的不定和式，在微积分中C是一个任意常数，而在有限微积分中C是任意一个满足的函数，类似微积分中求导时常数被消去，其意义仅在于我们取查分时，对结果不产生任何影响。所以C可以是周期函数，形如形式

在微积分的定积分运算中，如果，则有
类似的在有限微积分中，我们也可以做出定义，如果，则有

观察以下几个式子的规律

推广开来，我们的可以得到当时，的确切含义为
与微积分类似的是显然有

在我们做出以上种种定义之后，我们给出一个最重要的性质，同时也是其定义的最终意义

下面给出几个对本性质的实际应用的例子：

1. 当时，显然有，则根据上面的性质

通过这一式子我们也发现了对范围的求和是比的求和更简单的，前者刚好是，而后者必须计算

显然这比我们之间计算的方法更加简单

注意：在第六章中的斯特林数会帮助我们顺利的在通常的幂和阶乘幂之间转换，而不是这里通过分解质因式的笨办法

这里提前说明一个第五章习题中会讲述的阶乘二项式定理：以下等式恒成立

有了这个定理，我们可以很轻松的把二项式的下降幂拆分为多个简单的下降幂的加和

在上文中，我们仅仅考虑了非负指数的下降幂，现在我们推广至负指数的情形，给出时的定义
从上至下依次除以得到新的值，因此接下来再除以也是合理的
如此我们可以得到负指数的下降幂为

有了如上定义之后，与幂法则类似的，我们有

回到我们总结出的重要性质，显然可以将其情况推广
而对于有限微积分，为了防止，我们需要一个使其满足
当我们限制为整数时，显然有
恰好是前文提过的调和数，这也正是对连续的的离散模拟（在后续章节我们还将看到对于足够大的x，的近似值为0.577）

由以上叙述，我们可以给出下降幂的和式以完整的描述：
通过这个例子我们也了解到了为什么快速排序这样的离散问题会冒出调和数，因为其实我们处理的是对数函数的离散情况的逼近

而我们关心的是等比数列的和，显然有

我们把常用的间的对照关系列出来

有限微积分与微积分不同的是，对于形如并没有链式法则，但在分部积分上却有类似的地方。微积分中有，积分后改变次序有
在有限微积分中，同样的
为了书写上的便利，我们规定移位算子为如下形式
因此我们就可得到上表中最后一项的内容
再将式3取不定和即可得到有限微积分的分部

当我们使用时，只需要对上面三项同时加上确定的界限即可。

我们使用这条性质的场景通常是在左边的和式比右边的和式更难以处理时。比如在微积分中，同样的在有限微积分中，我们处理

加上界限后，可得如下式
通过这种办法显然比扰动法变换来变换去方便得多。

同样的我们来计算一下之

首先我们看一下和式的两种情况：
另一方面，按照同样的逻辑
竟然得出，这明显是一个错误的答案，我们在数列的敛散性里知道，这样的计算技巧只适用于不发散的序列，更准确的说：
假设每一项都是非负的，对无限集合，如果存在一个常数，使得任意有限集有
则我们认为对最小的有 ，如果不存在这样的，则我们认为 ，也就是说对任意大的数，都有有限项使得其组成的和超过
通过上面的式子，我们自然可以计算出
综合上一节有限微积分的知识

现在我们考虑一下和式同时存在正负项的情形，例如
如果将这个无限序列分组，由于次序不同，会分别得到0和1两个不同的答案，而如果我们令并代入式5，会得出这样一个答案，尽管这是一个全部由整数构成的和

下面看一个复杂的例子，对双向无限序列，
当时，，当时，，也就是

如果我们从中心开始计算这个和式
显然其和为1，我们将起点向左移动一个数
我们计算n个大的括号的和，即
事实上，无论起点选择在哪里，两两加和的结果都将结果指向1

但当我们用以下方式计算时

在这里我们使用不同方式计算产生了不同的结果，这提醒我们需要对无限和式采用更严谨的定义。

设是任意一个集合，是对任意时的项，实数可以写作以下形式（正的部分减去负的部分）
我们设，当都是有限值时，我们称绝对收敛于，当是有限值时，我们称发散于，当是有限值时，我们称发散于，当时，结果不一定

对应到这个例子中，我们知道调和级数是发散的，即，这个双向无限和式的结果是无法确定的。