1、第第2章章 和式（和式（SUMS）鞠成東鞠成東E-mail：M. P. ：1520467933622.4 多重和Multiple Sums3多重和的表示方法 一個和的項可能是由兩個或多個指標來確定，而不僅僅是由一個指標來確定。例如 對于一般的多指標求和情形，有兩種表達方法： (1)用“Iverson約定”表示所有整數對j和k求和。 (2)若想表達求和過程的次序和步驟，可采用多個。3323133222123121113,1babababababababababakjkjkjkjkjPkjkjPaa,),(,),( jkkjjkkjkjPakjPa),(),(,和式的和式：和式的和式：2021-1

2、2-274求和次序的交換 在在多指標求和多指標求和中，可使用中，可使用“交換求和次序交換求和次序”基本基本法，即：法，即：多個指標的求和式可從任一指標開始求多個指標的求和式可從任一指標開始求和和，這也是交換律和結合律的推廣形式。，這也是交換律和結合律的推廣形式。k kj jk kj jk kj jP Pk kj jj jk kk kj jk kj jP Pa aa ak kj jP Pa a), ,( ( ), ,( ( , ,) ), ,( (, , ,=從任一指標開始求和得到的結果是一致的。但是從任一指標開始求和得到的結果是一致的。但是一般來說，從不同的指標入手，計算難度是不一樣的一般來說

3、，從不同的指標入手，計算難度是不一樣的。實際計算中往往選擇從較簡單的指標入手。實際計算中往往選擇從較簡單的指標入手。5求和次序交換的例子3131,3,1 31 31 31 31 31 31 3131 3131 3,1 kjkkjjjkkjjkkjjkkjkjkjkjkjkjkjbakbjakbjakbjakjbakjbakjbaba)()()(332313322212312111bababababababababa)()()(321332123211bbbabbbabbba)(321321bbbaaa推廣：一般分配律6求和次序交換的例子推廣：一般分配律) ) )( ( (3 31 13 31

4、13 3, ,1 1k kj jk kj jk kj jb ba ab ba a=上例結論：) ) )( ( (KkJjK Kk kk kJ Jj jj jk kj jb ba ab ba a=7交換求和次序中的兩種情形 1：vanilla香草冰激凌綿軟 適用人群：被加項的下標之間獨立獨立 2：rocky-road石板街冰激凌層次 適用人群：內層下標范圍取決于外層 額外條件： K Kk kJ Jj jk kj jK Kk kJ Jj jk kj jJ Jj jK Kk kk kj ja aa aa a, , , ,= K Kk kj jJ Jj jk kj jJ Jj jj jK Kk kk

5、kj ja aa a=) )( (, ,) )( (, , )()(,kJjKkjKkJjkj2021-12-278“Rocky road冰激凌”的例子 對下面的兩重for循環，如果更換循環的順序，應該怎么寫？int s = 0;for (unsigned int j = 1; j n + 1; j +) for (unsigned int k = j; k 2021-12-2724方法2 方法2（攝動求和）： 回顧攝動求和方法，要將n + 1表示含有n的多個表達式，然后聯立方程求解得到n 。 先抽出n + 1的第一項，得到：n + 1 = 1 + (1 + 1)2 + + (n + 1)2=

6、 1 + (12 + + n2) + 2(1 + + n) + n= 1 + n + 2(1 + + n) + n 再抽出n + 1的最末項，得到：n + 1 = n + (n + 1)2 聯立兩個方程?!.n消失了！ 2021-12-2725方法2 方法2（攝動求和）： 但是前面的攝動法并非一無所獲，盡管方程聯立后平方和項消失了，但是容易得到2(1 + 2 + + n) = (n + 1)2 n 1 換言之，通過對平方求和的攝動，意外地得到了整數求和的封閉解（出現了次數的降低！）。那么要求平方和的封閉解，是否需要對立方求和進行攝動呢？2021-12-2726方法2 OK，抽出前n + 1個正

7、整數立方求和Cn+1的第1項：Cn+1 = 13 + 23 + + (n + 1)3 = 1 + (1 + 1)3 + + (n + 1)3 = 1 + (13 + 312 + 311 + 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 + +

8、 n) + n = Cn + n3 + 3n2 + 3n + 1 很容易解出n = n3 + 3n2 + 3n + 1 3(1 + n) + n + 12021-12-2727方法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)，即可求

9、得n 。2021-12-2728方法4 方法4（積分替換）： 注意到，積分在實質上是離散求和的連續注意到，積分在實質上是離散求和的連續化化（應該限定為黎曼積分，而不是勒貝格積分）。因此，嘗試用積分中的一些技巧來解決求和問題。 首先計算平方求和的積分版本： 因此可以認為平方求和的結果近似等于n3/3。3302ndxxn2021-12-2729方法4 方法4（積分替換）： 下面考察近似結果與精確結果間的誤差En ：En = n n3/3 = n-1 + n2 n3/3 = En-1 + (n-1)3/3 + n2 n3/3 = En-1 + n 1/3 同時可以得到E0 = 0。根據此遞歸方程，可

10、以解出En = (1 + + n) n/3，并進而得到n的精確解。2021-12-2730方法4 方法4（積分替換）： 對于En的計算，還可直接從積分的概念入手： 同樣可以得到En = (1 + + n) n/3，并進而得到n的精確解。nknknkkknkkkkdxxkE11232112313) 1(22021-12-2731方法5 方法5（擴展收縮）： 使用多重求和。使用形式上更復雜的多重求和來表達原求和問題。在多重求和下，對容易計算的和進行化簡，將其轉化成類似攝動法的方程求解問題。nnjnjnjnkjnkjnknnnnnnjjnnjnnjkkk21) 1(2121) 1(21) 1(21121211112 2