具体数学 第2章 和式(2.1节-2.3节)

1、第第2章章 和式（和式（SUMS）鞠成东鞠成东E-mail：M. P. 书名：具体数学：计算机科学基础（第书名：具体数学：计算机科学基础（第2版）版）原书名：原书名：Concrete Mathematics: A Foundation for Computer Science (2nd Edition)作者：作者：(美美)Ronald L. Graham, Donald E. Knuth, Oren Patashnik译者：张明尧，张凡译者：张明尧，张凡出版社：人民邮电出版社出版社：人民邮电出版社 ISBN：978-7-115-30810-8 第第1章章 递归问题递归

2、问题 第第2章章 和式（选讲）和式（选讲） 第第3章章 整值函数整值函数 第第4章章 数论数论 第第5章章 二项式系数二项式系数 第第6章章 特殊的数特殊的数 第第7章章 生成函数（自学）生成函数（自学） 第第8章章 离散概率离散概率 第第9章章 渐进式渐进式 It introduces the mathematics that supports the analysis of algorithms, modeling probems in real world. See,Chap. 1 Recurrence 递归的计数递归的计数Chap. 2 Sum 各种求和，用于算法复杂度计算等各种求和，

3、用于算法复杂度计算等Chap. 6 Special Numbers 调和数列及有关求和问题调和数列及有关求和问题 Concrete mathematics is a blending of continuous and discrete mathematics. See,Chap. 3 Integer Functions 实数的整数部分运算实数的整数部分运算Chap. 9 Asymptotics 离散到连续的渐进离散到连续的渐进 The goal is for the student to have mathematical skills to solve complex problems,

4、and to discover subtle patterns in data. Chap. 7 Generating Functions 用于概率计算的母函数用于概率计算的母函数Chap. 8 Discrete Probability 离散问题概率离散问题概率(最有趣最有趣) 2.1 记号记号 2.2 和式和递归式和式和递归式 2.3 和式的处理和式的处理 2.4 多重和式多重和式 2.5 一般性的方法一般性的方法 2.6 有限微积分和无限微积分有限微积分和无限微积分* 2.7 无限和式无限和式*82.1 记号（记号（Notation） 各种求和问题是最基本的数学内容之一，在各种求和问题是最

5、基本的数学内容之一，在数学的各个分支中都无处不在。数学的各个分支中都无处不在。 离散求和：级数离散求和：级数 连续求和：积分连续求和：积分在计算机科学中，求和是算法设计和分析工在计算机科学中，求和是算法设计和分析工作中的重要运算。因此，需要一些基本而巧妙的作中的重要运算。因此，需要一些基本而巧妙的工具和方法来处理求和问题。工具和方法来处理求和问题。本章讲解与求和相关的符号、方法和技巧。本章讲解与求和相关的符号、方法和技巧。92.1.1 三点记号法三点记号法n个整数的和可表为个整数的和可表为1+2+3+(n1)+n。对一般形式的和，可表为：对一般形式的和，可表为：a1 + a2 + + an但应

6、能体现项的模式（规律）。但应能体现项的模式（规律）。 明确列出的项确定了各明确列出的项确定了各项的模式项的模式，而未明确列出的项，而未明确列出的项使用使用“”来表示。来表示。 优点：简单明晰、直观，写起来不费劲。优点：简单明晰、直观，写起来不费劲。 缺点：有些含糊、不太严谨，式子冗长。缺点：有些含糊、不太严谨，式子冗长。例如：例如：1+7+41.7，费解否？，费解否？再如：再如：1+2+2n-1是是n项之和还是项之和还是2n-1项之和？项之和？102.1.2 符号表示法符号表示法大体有两种表示法（以大体有两种表示法（以a1 + a2 + + an为例）：为例）：两种表示法各有特点，也各有适用场

7、景。两种表示法各有特点，也各有适用场景。小知识：法国数学家小知识：法国数学家J. Fourier引入引入符号。符号。 确定界限的形式：确定界限的形式： 推广的一般形式：推广的一般形式： n nk kk ka a1 1 n nk kk ka a1 1其中：其中：ak为项；为项；k为指标；为指标；指标集指标集K为为1,n。11（1）下标变换）下标变换（2）符号数量）符号数量确定界限形式使用确定界限形式使用7个，而一般形式为个，而一般形式为8个。个。表示法表示法特点特点示例示例确定界限形式确定界限形式下标变换过程不够直观、下标变换过程不够直观、不易理解不易理解一般形式一般形式可方便地对下标变量进行可

8、方便地对下标变量进行变换，且简明易懂变换，且简明易懂 n nk kk kn nk kk ka aa a1 11 11 11 1 1 10 01 11 1n nk kk kn nk kk ka aa a12（3）表示法的清晰性和灵活性）表示法的清晰性和灵活性确定界限的形式：确定界限的形式：推广的一般形式：推广的一般形式：示例：请描述示例：请描述“不超过不超过100的所有正奇数的平方和的所有正奇数的平方和”。 49490 02 2) )1 12 2( (k kk k 是奇数是奇数1001001 12 2k kk kk k示例：请描述示例：请描述“1到到N之间的所有素数的倒数之和之间的所有素数的倒数

9、之和”。请阅读教材。请阅读教材。13（4）适用场景）适用场景那么如何较准确理解一般形式的那么如何较准确理解一般形式的 ？ p(k)是一个性质，可以是任意的谓词；是一个性质，可以是任意的谓词； k是满足是满足p(k)的一个整数；的一个整数； 是所有满足是所有满足p(k)的下标的下标k对应的项对应的项ak的和。的和。表示法表示法适用场景适用场景确定界限形式确定界限形式 常用于表示最终结果常用于表示最终结果一般形式一般形式常用于计算和推导过程常用于计算和推导过程 ) )( (k kp pk ka a14在写法上，还可写成在写法上，还可写成 ，其中，其中p(k)成为成为的的“下标下标”。常用于正文排版

10、，以减少行高。常用于正文排版，以减少行高。有一种更奇妙的表示方法，称为艾弗森约定：有一种更奇妙的表示方法，称为艾弗森约定：例如：例如： ) )( (k kp pk ka aKenneth Iverson在程序设计语言在程序设计语言APL中提出，将真或假中提出，将真或假的命题的命题p(k)放在方括号中，当命题放在方括号中，当命题p(k)为真时，命题的结果为为真时，命题的结果为1；为假时，结果为为假时，结果为0。 不是素数不是素数p p，0 0是素数是素数p p，1 1 是素数是素数 ) )( (p pk kP P15这样，就可将谓词这样，就可将谓词p(k)放到被加项中，而不是用放到被加项中，而不

11、是用来限制下标变量。此时，和式可写成：来限制下标变量。此时，和式可写成：特点：可规避为特点：可规避为p(k)假的情形，以及假的情形，以及ak无定义的无定义的情形。该表示法更具灵活性、能力更强。情形。该表示法更具灵活性、能力更强。 p pk kp pk kk kp pk kp pa aa ak kk kk kp pk k不满足不满足, ,0 0满足满足, ,1 1)( ( 其中其中, ,)( ( ) )( (示例：使用艾弗森约定描述示例：使用艾弗森约定描述N的素数倒数之和。的素数倒数之和。 p pp pN Np pp p/ / 是素数是素数 16另外还需注意界限的简单性：另外还需注意界限的简单性

12、：人们常常想要使用人们常常想要使用而不是而不是 1 12 2) )()(1 1( (n nk kk kn nk kk k n nk kk kn nk kk k0 0) )()(1 1( (前者：可能会有含糊不清的风险；前者：可能会有含糊不清的风险；后者：界限简单，更便于处理。后者：界限简单，更便于处理。17。 2.1 记号记号 2.2 和式和递归式和式和递归式 2.3 和式的处理和式的处理 2.4 多重和式多重和式 2.5 一般性的方法一般性的方法 2.6 有限微积分和无限微积分有限微积分和无限微积分* 2.7 无限和式无限和式*192.2 和式和递归式和式和递归式 联想到上一章所学内容，能把

13、和式化为递归联想到上一章所学内容，能把和式化为递归问题吗？这样就可施展问题吗？这样就可施展“Guess-Prove”方法。方法。首先考察和式首先考察和式 ，以观察和式与递，以观察和式与递归式之间的密切关系。归式之间的密切关系。递归出现了递归出现了 n nk kk kn na aS S0 0n nn nn na aS SS Sa aS S 1 10 00 020。2022-1-1321将求和转化为递归问题后，就可以用将求和转化为递归问题后，就可以用“Guess-Prove”方法求出封闭形式解，当然，也可使用方法求出封闭形式解，当然，也可使用“清清单法单法”。可得：可得：示例：求解如下和式。示例：

14、求解如下和式。k ka aa aa aR Rk kn nk kk kn n 0 00 0其中：其中：, ,n n1 1- - n nn nR RR R2022-1-1322求解递归式求解递归式 的方法：的方法：（1）由）由 ，猜测解的形式为：，猜测解的形式为：（2）采用）采用Josephus推广问题中的推广问题中的“清单法清单法”，在，在若干简单的若干简单的 组合上直接算出组合上直接算出Rn，构造出关，构造出关于于A, B, C的方程组，求出的方程组，求出A、B、C即可得到即可得到Rn的的一般解。一般解。32,21RR)()()(nCnBnARn),(n n1 1- - n nn nR RR

15、R令令Rn=1，可得，可得=1，=0，=0，从而，从而A(n)=1；令令Rn=n，可得可得=0，=1，=0，从而从而B(n)=n；令令Rn=n2，可得可得=0，=-1，=2，从而，从而2C(n)-B(n)=n2，即：，即：C(n)=(B(n)+n2)/2最终可得：最终可得：2 2/ /) )( () )( () )( () )( (2 2n nn nn nn nC Cn nB Bn nA AR Rn n 示例：计算示例：计算解：此时解：此时=a，=b。 n nk kn nbkbka aR R0 0) )( (2022-1-1324现在我们知道可以用递归来求和，相反，很多递归现在我们知道可以用递

16、归来求和，相反，很多递归问题也可以简化为求和，后面要学到的各种求和方问题也可以简化为求和，后面要学到的各种求和方法都可以用来计算较难的递归问题。例如，对于法都可以用来计算较难的递归问题。例如，对于Hanoi Tower问题：问题：T0 = 0Tn = 2Tn-1 + 1下面我们尝试用求和方法来计算下面我们尝试用求和方法来计算Tn首先，两端除以首先，两端除以2n，得到，得到T0 / 20 = 0Tn / 2n = Tn-1 / 2n-1 + 1 / 2n2022-1-1325设设Sn= Tn/ 2n，于是得到，于是得到S0 = 0Sn = Sn-1 + 2-n容易看出，计算容易看出，计算Sn是一

17、个求和问题：是一个求和问题：假如假如可以很容易地解决求和问题可以很容易地解决求和问题，就可以得到递归，就可以得到递归方程的封闭解方程的封闭解Tn = Sn * 2n 。事实上，上面的。事实上，上面的Sn是常是常见的等比级数，因此见的等比级数，因此Tn = (1 2-n) 2n = 2n - 1nkknS12对于一般形式的递归方程对于一般形式的递归方程 ，可采用类似方法，将，可采用类似方法，将其化成等比级数求和问题：其化成等比级数求和问题：两边乘两边乘以以求和因子求和因子sn可可得得巧妙地选择此因子巧妙地选择此因子sn使得使得接下来，记接下来，记Sn = snanTn，则可得到递归式则可得到递归

18、式因此因此原原递归式的解即为：递归式的解即为：nnnnncTbTa1n nn nn nn nn nn nn nn nc cs sT Tb bs sT Ta as s 1 11 11 1 n nn nn nn na as sb bs sn nn nn nn nc cs sS SS S+=1 1nkkknkkknkkkncsTbscsTascsSS1011100010 n nk kk kk kn nn nn nc cs sT Tb bs sa as sT T1 10 01 11 11 1尚有未决问题：尚有未决问题：sn 到底是怎样的，才能使下式成立？到底是怎样的，才能使下式成立？sn bn = s

19、n-1 an-1sn-1 bn-1 = sn-2 an-2s2 b2 = s1a1将以上等式连续相乘，可得将以上等式连续相乘，可得s1、s0的值仅受到的值仅受到s1b1=s0a0的约束，可为任意非零值。的约束，可为任意非零值。因此可略去因此可略去s1，因而，因而sn可取如下值或其任意倍数可取如下值或其任意倍数避免被零避免被零除。当除。当所有所有a和和b非非零时，求和因子法零时，求和因子法才能用才能用。1 12 21 11 12 21 1s sb bb bb ba aa aa as sn nn nn nn nn n-=2 21 11 12 21 1b bb bb ba aa aa as sn n

20、n nn nn nn n=作业：请使用求和因子法求解三个桩柱的Hanoi Tower问题。快速排序方法是快速排序方法是Hoare在在1962年发明的。在实际应用中，快年发明的。在实际应用中，快排是效率最高的简单排序算法。排是效率最高的简单排序算法。假定待假定待排序的排序的n项项记录的初始次序随机排列的，则快速记录的初始次序随机排列的，则快速排序排序所需所需的平均比较次数的平均比较次数Cn满足满足递归递归式式消掉除法：两边消掉除法：两边同同乘乘n。消消掉掉：用：用(n-1)代替代替n 。1 10 00 02 21 10 0n nk kk kn nC Cn nn nC CC C=+=1022nkk

21、nCnnnC20212) 1() 1() 1(nkknCnnCn思考题：快速排序的平均比较次数的递归式怎么得到的？上下两个方程相减，上下两个方程相减，可得可得因此，递归式可化简为：因此，递归式可化简为：令令an=n，bn=n +1和和cn=2n，则求和因子，则求和因子sn为为1122) 1(nnnCnCnnC2 2, ,2 2) )1 1( (; ;3 3; ;0 01 12 21 10 0+=n nn nC Cn nnCnCC CC CC Cn nn n-nnnnnnbbbaaasnnnnn) 1(23) 1(1)2() 1(21121可得解为可得解为我们我们记调和数记调和数Hn为为此时得到

22、了此时得到了Cn的封闭形式解。也就是说，这里将的封闭形式解。也就是说，这里将“调和数调和数”Hn视为视为“常见常见”的运算。的运算。字母字母H代表代表“调和调和”(Harmonic)。Hn被称为被称为调和数，其调和数，其来历是：小提琴的琴弦来历是：小提琴的琴弦产生的第产生的第k个泛音是由其个泛音是由其1/k长长（手指搭在弦上）的（手指搭在弦上）的弦产生的弦产生的基音。基音。nknknH111211) )1 1( (3 32 21 11 1) )1 1( (2 21 1+=n nk kn nC Cn nk kn n-在定义完在定义完Hn之后，对之后，对Cn中的求和部分做些变换，以中的求和部分做些

23、变换，以便使用便使用Hn来表达来表达Cn ：因此因此Cn可以写成可以写成对小数值对小数值n = 0, 1, 2，可检查其正确性。，可检查其正确性。1111111111111121111nnHnkkkkknnknknknknknHnnnHnCnnn2) 1(21) 1(2 2.1 记号记号 2.2 和式和递归式和式和递归式 2.3 和式的处理和式的处理 2.4 多重和式多重和式 2.5 一般性的方法一般性的方法 2.6 有限微积分和无限微积分有限微积分和无限微积分* 2.7 无限和式无限和式*332.3 和式的处理和式的处理“和式运算法则和式运算法则”的重要作用：将某个形式的重要作用：将某个形式

24、的的变成另一个更简单或更接近某个目标的变成另一个更简单或更接近某个目标的。设设K为有限整数集合。可用三个简单的规则为有限整数集合。可用三个简单的规则来变换基集合来变换基集合K中的元素的和：中的元素的和：分配律分配律distributive law：结合律结合律associative law：交换律交换律commutative law：p(k)应满足什么条件？应满足什么条件？KkkKkkaccaKkkKkkKkkkbabaKkpkpKkkaa)()(34。 示例：对算术级数 求和 运用交换律，用n k替代k，可得 运用结合律，将两个等式相加，得到 运用分配率，提取常数(2a + bn)，可得 最

25、终得到nkbkaS0)(nknknbkbnaknbaS00)()(nknkbnabkbnabkaS00)2()()(2) 1()2(1)2(20nbnabnaSnk) 1()21(nbnaS回顾成套方法2022-1-1336有关Iverson约定形式的运算 回顾一下，“Iverson约定”将下标的限制放到被加项的公式里面。此方法可以与分配律、结合律和交换律一起使用，并且产生一些有趣的性质。 假设K和K是任意整数集合，则： 推导过程：KKkkKKkkKkkKkkaaaaKKkkKKkkkkkkkkkkkkkkKkkKkkaaKKkaKKkaKKkKKkaKkKkaKkaKkaaa2022-1-1

26、337Iverson约定形式在求和中的应用 1、合并两个几乎不相交的指标集合 2、从一个求和式中分离出某个单独的项。这是“摄动法”(perturbation method)的基本形式。nkkmnmkkmkkaaaa11nkknkkaaa000nnkknkkaaa1002022-1-1338摄动法的应用 Perturbation Method，摄动法，该名词来自于天体力学中的常用数学方法。摄动法用于计算小天体对大天体运行的影响，后广泛用于数学、物理学的各个领域。主要思想是将复杂系统看做是简单系统被某个未知参数扰动的结果，因此可以先计算简单系统，再以未知参数的级数来渐进地近似复杂系统，大大简化了计算过程。 CM借用了摄动法的术语和主要思想，在求和计算中，根据“和上的运算”(Iverson约定)规则，将求和式表达成两种形式，并且分别化为待求值的（线性）多项