具體數(shù)學(xué)-2-2第二章多重和

具體數(shù)學(xué)

ConcreteMathematics

13十月20242024/10/1322.4多重和

MultipleSums2024/10/133多重和的表示方法一個和的項可能是由兩個或多個指標(biāo)來確定，例如兩種（數(shù)量）表達一般多指標(biāo)求和的方法：利用“Iverson約定”對所有整數(shù)對j和k求和按特定次序求和，表示為多重∑

2024/10/134求和次序的交換交換求和次序的基本法則：具有多個指標(biāo)的求和式可從任一指標(biāo)開始求和（交換律和結(jié)合律在多指標(biāo)求和中的應(yīng)用，推廣了結(jié)合律）從任一指標(biāo)開始求和得到的結(jié)果是一致的。但是一般來說，從不同的指標(biāo)入手，計算難度是不一樣的。實際計算中往往選擇從較簡單的指標(biāo)入手。

2024/10/135求和次序交換的例子

推廣：一般分配律2024/10/136兩種特定P(j,k)下的求和次序及交換（1）P(j,k)可表示為P(j)andP(k)

下標(biāo)之間是獨立的（2）p(j,k)不能表示為p(j)andp(k)

要求

2024/10/137第一種形式的例子（1）（2）

2024/10/138第二種形式的例子對下面的兩重for循環(huán)，如果更換循環(huán)的順序，應(yīng)該怎么寫？ints=0;for(unsignedintj=1;j<n+1;j++){ for(unsignedintk=j;k<n+1;k++){ s+=a[j][k]; }}2024/10/139第二種形式的例子前面的代碼相當(dāng)于計算在Iverson約定下考察如何變換循環(huán)的順序：因此有一般來說，從j或k開始求和的難度是不同的。往往選擇從容易的下標(biāo)開始。

2024/10/1310第二種形式的例子考慮具有n2個乘積ajak的陣列目標(biāo)是計算所有上三角元素之和，即

2024/10/1311第二種形式的例子容易看出，該矩陣是對稱的。因此應(yīng)該大約等于矩陣所有元素之和的一半：由于因此

2024/10/1312另外一個例子目標(biāo)是計算注意到j(luò)和k的對稱性，可以寫成而且，在Iverson約定下有

2024/10/1313另外一個例子因此將S的兩個表達式相加，得到顯然第2項為0。對于第1項，可以展成4項：

?2024/10/1314Chebyshev單調(diào)不等式因此得到如果有，則有如果有，則有

切比雪夫不等式彼得堡學(xué)派創(chuàng)始人1821—18942024/10/1315多重和中的交換律

2024/10/1316一個多重和的concreteexample目標(biāo)是計算先嘗試從j開始：

先對j求和用k-j替換j簡化j的上下界使用調(diào)和數(shù)記號用k+1替換k簡化k的上下界這里記H0=02024/10/1317一個多重和的concreteexample再嘗試從k開始：

先對k求和用k+j替換k簡化k的上下界使用調(diào)和數(shù)記號用n-j替換j簡化j的上下界這里記H0=0結(jié)果和方法1一致2024/10/1318一個多重和的concreteexample第三種方法：在將Sn表達成多重和之前，用k+j替換k。

計算目標(biāo)用k+j替換k先在j上求和算出j上的和使用結(jié)合律很容易采用調(diào)和數(shù)記號2024/10/1319一個多重和的concreteexample綜合前面的三種不同方法，可以得到從代數(shù)、幾何兩種角度總結(jié)三種方法中的經(jīng)驗：代數(shù)：如果在被加項中有k+f(j)之類的表達式，可以將k替換成k-f(j)，然后在j上求和；幾何：

2024/10/13202.5GeneralMethods

一般方法總結(jié)2024/10/13212.5一般方法總結(jié)在掌握了求和的記號、求和與遞歸的關(guān)系，以及多重求和的有關(guān)技巧之后，對常見的求和方法做一個簡明的列舉和介紹。通過具體問題展開介紹：計算目標(biāo)：求前n個平方和的封閉形式解。在解未知之前，將其記做□n

2024/10/1322方法0~1方法0（查找書籍）：

去書里面查找到答案為。注：(1)知道去找什么書往往并不容易，需要積累；(2)計算機科學(xué)或者數(shù)學(xué)自身內(nèi)部也有很多方向，而且基本上是“隔行如隔山”，我們很難成為全能選手，所以快速、準確地找到需要的工具和結(jié)論是非常重要的，也是研究和開發(fā)工作中的關(guān)鍵本領(lǐng)。方法1（猜測證明）： Guess—Prove。首先猜出再用數(shù)學(xué)歸納法證明。

2024/10/1323方法0~1盡管方法0和方法1是常用的基本數(shù)學(xué)工具，但并不是CM的主旨和主推方法。我們的目標(biāo)是，在下面的條件下，計算出正確的結(jié)果：1、沒有現(xiàn)成結(jié)論或參考資料；2、沒有靈光一現(xiàn)地猜出結(jié)論。所以繼續(xù)看后面的方法>>>>>>>>>>>>>2024/10/1324方法2（擾動求和）回顧擾動求和方法，要將□n+1表示成含有□n的多個表達式，然后聯(liá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聯(lián)立兩個方程……???!!!......□n消失了！

2024/10/1325方法2（擾動求和）但是前面的擾動法并非一無所獲，盡管方程聯(lián)立后平方和項消失了，但是容易得到2(1+2+…+n)=(n+1)2–n–1換言之，通過對平方求和的擾動，意外地得到了整數(shù)求和的封閉解（出現(xiàn)了次數(shù)的降低?。Ｄ敲匆笃椒胶偷姆忾]解，是否需要對立方求和進行擾動呢？2024/10/1326方法2（擾動求和）OK，抽出前n+1個正整數(shù)立方求和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+3□n+3(1+…+n)+n然后，抽出前n+1個正整數(shù)立方求和Cn+1的第末項：

Cn+1=Cn+(n+1)3

=Cn+n3+3n2+3n+1聯(lián)立方程，得到1+Cn

+3□n+3(1+…+n)+n=Cn+n3+3n2+3n+1易解出3□n=n3+3n2+3n+1–[3(1+…+n)+n+1]2024/10/1327方法3（成套法求和）對遞歸方程R0=α;Rn=Rn-1+β+γn+δn2封閉解的一般形式為Rn=A(n)α+B(n)β+C(n)γ+D(n)δ令δ=0，可以很容易地解出A、B和C的表達式（參見2.2）。然后在(α,β,γ,δ)=(0,1,-3,3)上求得Rn=n3，因此有D(n)=(n3+3C(n)-B(n))/3。最后在(α,β,γ,δ)=(0,0,0,1)上即可求得□n。2024/10/1328方法4（積分替換）注意到，積分實質(zhì)上是離散求和的連續(xù)化，探索積分會給我們一些啟發(fā)，乃至解決問題。首先計算平方求和的積分版本：可以認為平方求和的結(jié)果近似等于n3/3。

2024/10/1329方法4（積分替換）下面考察近似結(jié)果與精確結(jié)果間的誤差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。根據(jù)此遞歸方程，可以解出En=(1+…+n)–n/3，并進而得到□n的精確解。2024/10/1330方法4（積分替換）對于En的計算，還可直接從積分的概念入手：

同樣可以得到En=(1+…+n)–n/3，并進而得到□n的精確解。

2024/10/1331方法5（展開和收縮）使用多重求和。使用形式上更復(fù)雜的多重求和來表達原求和問題。在多重求和下，對容易計算的和進行化簡，將其轉(zhuǎn)化成類似擾動法的方程求解問題。

2024/10/1332方法6~7方法6（有限“積分”）：2.6節(jié)講解的主要內(nèi)容。與前面的幾種求和方法不同，方法6是以前很少接觸到、比較陌生的一種方法，該方法具有較為系統(tǒng)的演算法則和規(guī)律，是解求和問題的新工具，值得掌握和熟悉。方法7（母函數(shù)法）：留作課外學(xué)習(xí)。作業(yè)P52：2,11,19,20,21,22證明：Pleasefindtheclosedformforthesumofthefirstnpositiveinte