具体数学-第2章-和式(2.4节-2.5节)

第2章和式（SUMS）鞠成东E-mail：[e-mail].P.：1520467933622.4多重和MultipleSums3多重和的表示方法•一个和的项可能是由两个或多个指标来确定，而不仅仅是由一个指标来确定。例如•对于一般的多指标求和情形，有两种表达方法：•(1)用“Iverson约定”表示所有整数对j和k求和。•(2)若想表达求和过程的次序和步骤，可采用多个∑。3323133222123121113,1babababababababababakjkjkjkjkjPkjkjPaa,,),(,)],([jkkjjkkjkjPakjPa)],([)],([,,和式的和式：2020/11/164求和次序的交换•在多指标求和中，可使用“交换求和次序”基本法，即：多个指标的求和式可从任一指标开始求和，这也是交换律和结合律的推广形式。∑∑∑∑∑kjkjkjPkjjkkjkjPaakjPa)],([)],([,),(,,==从任一指标开始求和得到的结果是一致的。但是一般来说，从不同的指标入手，计算难度是不一样的。实际计算中往往选择从较简单的指标入手。5求和次序交换的例子3131,,3,1]31[]31[]31[]31[]31[]31[]31][31[]31][31[]3,1[kjkkjjjkkjjkkjjkkjkjkjkjkjkjkjbakbjakbjakbjakjbakjbakjbaba)()()(332313322212312111bababababababababa)()()(321332123211bbbabbbabbba))((321321bbbaaa推广：一般分配律①②③④⑤⑥⑦6求和次序交换的例子推广：一般分配律))((31313,1∑∑∑≤≤kjkjkjbaba=上例结论：))((∑∑∑∈∈K∈kJ∈jKkkJjjkjbaba=7交换求和次序中的两种情形•1：vanilla—香草冰激凌—绵软•适用人群：被加项的下标之间独立•2：rocky-road—石板街冰激凌—层次•适用人群：内层下标范围取决于外层•额外条件：∑∑∑∑∑∈∈∈∈∈∈KkJjkjKkJjkjJjKkkjaaa,,,==∑∑∑∑∈∈∈∈KkjJjkjJjjKkkjaa′′=)(,)(,)()(,,kJjKkjKkJjkj2020/11/168“Rockyroad冰激凌”的例子•对下面的两重for循环，如果更换循环的顺序，应该怎么写？ints=0;for(unsignedintj=1;jn+1;j++){for(unsignedintk=j;kn+1;k++){s+=a[j][k];}}2020/11/169“Rockyroad冰激凌”的例子•前面的代码相当于计算•在Iverson约定下考察如何变换循环的顺序：•因此有•一般来说，从j或k开始求和的难度是不同的。往往选择从容易的下标开始。njnjkkja1,kjnknkjnkjnj1111∑∑∑∑∑≤≤≤nkkjkjnkjkjnjnjkkjaaa11,1,1,======2020/11/1610“Rockyroad冰激凌”的例子•考虑具有n2个乘积ajak的阵列•目标是计算所有上三角元素之和，即nnnnnnnnaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa321333231323222121312111nkjkjaaS12020/11/1611“Rockyroad冰激凌”的例子•容易看出，该矩阵是对称的。因此应该大约等于矩阵所有元素之和的一半：•由于•因此SSaaaaaaSnjkkjnjkjknkjkj111nkjnkjnjknkj1,111nkjkjnkjkjaaaaSSS1,122111njjnkknjjaaanjja12nkknkknkjkjaaaaS12211212020/11/1612另外一个例子•目标是计算•注意到j和k的对称性，可以写成•而且，在Iverson约定下有nkjjkjkbbaaS1njkjkjknjkkjkjbbaabbaaS11nkjnkjnjknkj1,1112020/11/1613另外一个例子•因此将S的两个表达式相加，得到•显然第2项为0。对于第1项，可以展成4项：nkjkjkjnkjkjkjbbaabbaaS1,12nkknkknkkknkjkjnkjkknkjkknkjjknkjkjnkjjjbabanbabababababa111,1,1,1,1,1,12222?消去一个下标，就要增加一个因子2020/11/1614Chebyshev单调不等式•因此得到•如果有，则有•如果有，则有nkjjkjknkkknkknkkbbaabanba1111nnbbaa11,nkkknkknkkbanba111nnbbaa11,nkkknkknkkbanba111Chebyshev不等式彼得堡学派创始人1821—18942020/11/1615多重和与单一和的联系•对于单一求和中改变求和指标的一般操作，可以用多重求和来证明其正确性：•简略推导过程：}.)({)(,)(#11)(kjfjkfkfaaKkkJjjf这里KkkKkJjkKkJjkJjjfkfakjfakjfaa)(#])([])([1)(2020/11/1616一个多重和的concreteexample•目标是计算•先尝试从j开始：nkjnjkS11nkknkknkknkkjnkkjknkkjnHHHjjjkS011111111111111先对j求和用k-j替换j简化j的上下界使用调和数记号用k+1替换k简化k的上下界这里记H0=02020/11/1617一个多重和的concreteexample•再尝试从k开始：njjnjnjnjjnnjjnknjnjkjnjnkjnHHHkkjkS0111011111先对k求和用k+j替换k简化k的上下界使用调和数记号用n-j替换j简化j的上下界这里记H0=0结果和方法1一致2020/11/1618一个多重和的concreteexample•第三种方法：•在将Sn表达成多重和之前，用k+j替换k。nHnnknknkknkkjkSnnknknknknkknjnjkjnkjn1111111111111计算目标用k+j替换k先在j上求和算出j上的和使用结合律很容易采用调和数记号2020/11/1619一个多重和的concreteexample•综合前面的三种不同方法，可以得到•从代数、几何两种角度总结三种方法中的经验：•代数：如果在被加项中有k+f(j)之类的表达式，可以将k替换成k-f(j)，然后在j上求和；•几何：nHnHnnkn041132111231211114321jjjjkkkk2020/11/16202.5GeneralMethods常用求和方法列举2020/11/16212.5常用求和方法•在掌握了求和的记号、求和与递归的关系，以及多重求和的有关技巧之后，对常见的求和方法做一个简明的列举和介绍。通过具体问题展开介绍：•计算目标：求前n个平方和的封闭形式解。在解未知之前，将其记做□nnkk022020/11/1622方法0~1•方法0（查找书籍）：去书里面查找到答案为。注：(1)知道去找什么书往往并不容易，也需要积累；(2)计算机科学或者数学自身内部也有很多方向，而且基本上是“隔行如隔山”，我们很难成为全能选手，所以快速、准确地找到需要的工具和结论是非常重要的，也是研究和开发工作中的关键本领。•方法1（猜测证明）：Guess—Prove。首先猜出再用数学归纳法证明。6)12)(1(nnn3)2)(21(nnn2020/11/1623方法0~1•尽管方法0和方法1是常用的基本数学工具，但并不是CM的主旨和主推方法。•我们的目标是，在下面的条件下，计算出正确的结果：•1、没有现成结论或参考资料；•2、没有灵光一现地猜出结论。•所以继续看后面的方法2020/11/1624方法2•方法2（摄动求和）：•回顾摄动求和方法，要将□n+1表示含有□n的多个表达式，然后联立方程求解得到□n。•先抽出□n+1的第一项，得到：□n+1=1+(1+1)2+…+(n+1)2=1+(12+…+n2)+2(1+…+n)+n=1+□n+2(1+…+n)+n•再抽出□n+1的最末项，得到：□n+1=□n+(n+1)2•联立两个方程……???!!!......□n消失了！2020/11/1625方法2•方法2（摄动求和）：•但是前面的摄动法并非一无所获，尽管方程联立后平方和项消失了，但是容易得到2(1+2+…+n)=(n+1)2–n–1•换言之，通过对平方求和的摄动，意外地得到了整数求和的封闭解（出现了次数的降低！）。那么要求平方和的封闭解，是否需要对立方求和进行摄动呢？2020/11/1626方法2•OK，抽出前n+1个正整数立方求和Cn+1的第1项：Cn+1=13+23+…+(n+1)3=1+(1+1)3+…+(n+1)3=1+(13+3·12+3·11+1)+…+[n3+3n2+3n+1]=1+(13+…+n3)+3(12+…+n2)+3(1+…+n)+n=1+Cn+□n+3(1+…+n)+n•然后，抽出前n+1个正整数立方求和Cn+1的第末项：Cn+1=Cn+(n+1)3=Cn+n3+3n2+3n+1•联立方程，得到1+Cn+□n+3(1+…+n)+n=Cn+n3+3n2+3n+1•很容易解出□n=n3+3n2+3n+1–[3(1+…+n)+n+1]2020/11/1627方法3•方法3（清单求和）：•对递归方程R0=α;Rn=Rn-1+β+γn+δn2•猜想封闭形式解为Rn=A(n)α+B(n)β+C(n)γ+D(n)δ•令δ=0，可以很容易地解出A、B和C的表达式。然后在(α,β,γ,δ)=(0,1,-3,3)上求得Rn=n3，因此有D(n)=(n3+3C(n)-B(n))/3。•最后令(α,β,γ,δ)=(0,0,0,1)，即可求得□n。2020/11/1628方法4•方法4（积分替换）：•注意到，积分在实质上是离散求和的连续化（应该限定为黎曼积分，而不是勒贝格积分）。因此，尝试用积分中的一些技巧来解决求和问题。•首先计算平方求和的积分版本：•因此可以认为平方求和的结果近似等于n3/3。3302ndxxn2020/11/1629方法4•方法4（积分替换）：