前言

由于本人過于菜雞，學多項式以及一些奇奇怪怪的東西的時候結識了這個有限微積分，故有了這篇文章。

有限微積分是在離散（通常是整數）意義下的積分，不再是平常我們所熟知的類似求面積的無限微積分。

字面意思就是說不能無限分很多小塊下去。

引入

常見數列

對于數列上的求和，我們有一些耳熟能詳的結論和定理：

如果你知識面比較廣，可能還知道：

但是如果我們現在得到一個全新的公式，我們該如何是好呢？

這里就提出了有限微積分這個好東西，用于求解非組合形式的數列求和問題。

裂項相消法

在小學奧數中有這么一個式子：

根據小學奧數學的裂項：

這啟示我們，若干個數的和可以將其拆分成小數再進行相加。

而對于高中生來說，我們還會知道求導：

這個東西相當于是減去一個極小的 \(\Delta x\) 的值。

發現這個其實跟裂項相消比較類似。

于是我們能得出一個結論：

既然存在相加和相減的對立，那么求導也存在著與之相對應的運算法則，即積分，二者分別對應的是差的極限與和的極限。

因此對于求和問題，我們可以用積分進行求解。

差分

在OI中，我們學習過差分這種算法，一般用于解決區間操作問題。

比如我們對于一個數列 \(a\),我們需要對 \([l, r]\) 進行區間加操作，一種比較人類智慧的方法就是先對 \(a\) 進行如下操作：

這樣我們修改的時候，只需要修改 \(a_l\) 以及 \(a_{r + 1}\) 的值，最后再進行前綴和操作即可實現區間加操作。

我們發現這個差分操作類似于離散意義下的求導？那前綴和就是積分？

我們提出這樣一個東西：

意思就是 \(\Delta f(x)\) 是一個新函數，存儲的值是原函數 \(+1\) 的函數值與當前函數值的差值。

探究一下運算的法則：

• 加法法則：\(\Delta (u + v) = \Delta u + \Delta v\)
  套用定義即可證明
• 減法法則：\(\Delta (u - v) = \Delta u - \Delta v\)
  同理
• \(\Delta(Cu) = C \Delta u\)
  其中 \(C\) 是一個無關常數。
  同樣套用證明
• 乘法法則：\(\Delta(uv) = u\Delta v + Ev\Delta u\)
  證明：\(\Delta (f(x)g(x)) = f(x + 1)g(x + 1) - f(x)g(x)\)
  考慮一個中間項 \(-f(x)g(x + 1) + f(x)g(x + 1)\)

需要注意的是，有限微積分相比于無限微積分，并沒有除法法則和鏈式法則。

定和式

即存在上下界的和式

有了差分之后，我們開始系統性的解決求和問題。定義定和式：

注意，\(\sum_a^b\) 表示的范圍不是 \([a, b]\)，而是左閉右開，即 \([a, b)\)

很顯然，這個就是我們之前說的差分的逆運算，相當于前綴和。

具體的，根據裂項相消法，有微積分基本定理：

這說明差分函數在 \([a, b)\) 積分值為 \(f(b) - f(a)\)。

這個差分函數就是離散意義下的導函數，積分后的函數即為原函數。這也體現出了導函數的積分為原函數加某一個常數的觀點。

類比一下，說明一個函數 \(f(x)\) 在 \([a, b)\) 的積分值為 \(F(b) - F(a)\)。

套用定義，能知道定和式滿足以下性質：

• \(\sum_a^a f(x) \delta x = 0,\sum_a^b f(x) \delta x = - \sum_b^a f(x) \delta x\)
• \(\sum_a^b f(x) \delta x + \sum_b^c f(x) \delta x = \sum_a^cf(x) \delta x\)
• \(\sum_a^b f(x) \delta x \pm \sum_a^b g(x) \delta x = \sum_a^b (f(x) \pm g(x)) \delta x\)
• \(\sum_a^b Cf(x) \delta x = C\sum_a^b f(x) \delta x\)

例題1

求解等比數列和 \(\sum\limits^{n - 1}_{k = 0} a^k \ (a \ne 1)\)

考慮指數函數的差分：

因此，原式變為：

這也是等比數列求和公式的另外一種求法。

下降冪

以上的指數函數能夠通過 \(\Delta f(x)\) 套用運算法則將原函數化成 \(\Delta f(x)\) 的形式，直接能夠算出和。

但可惜的是冪函數就不可以了，如果我們按照剛剛的辦法，在有限微積分有以下式子：

這個東西沒辦法套用公式得到原函數與差分函數的關系，故這里引入下降冪（不會的去組合數學里學）。

Ex：同樣的做法在無限微積分中卻有非常優美的形式：\((x^n)' = na^{n-1}\)，這里的求導與有限微積分的差分意義上等價。

下降冪的差分具有類似無限微積分中的冪函數一樣的很優美的性質：

同樣套用公式,得出一個很重要的式子：

因此可以考慮普通冪轉下降冪進行求和。

由于普通冪與下降冪之間存在關系：

故可以解決冪函數的有限積分問題了。

例題2

求解等差數列和 \(\sum\limits_{k=1}^{n}k\)

解：

例題3

求解 \(\sum\limits_{k = 1}^{n}{1 \over {k(k + 1)}}\)

解：

由于當 \(m < 0\) 時，\(n^{\underline m} = {1 \over (n+1)^{\overline m}}\)。故：

例題4 (P1625求和)

解：

例題5

證明上指標求和公式 \(\sum\limits_{k = 0}^{n}{k \choose m} = {n + 1 \choose m + 1}\)

證明：

例題6

求解 \(\sum\limits_{k=1}^{n}k^2\)

解：

由于普通冪與下降冪之間存在關系：

所以 \(x^2 = {2 \brace 0}x^{\underline 0} + {2 \brace 1}x^{\underline 1} + {2 \brace 2}x^{\underline 2} = (x^{\underline 2} + x)\)

例題7

求解 \(\sum\limits_{k = 1}^{n} k^3\)

解：

同例題6理將冪次化為下降冪

需要注意的是，由于第二類斯特林數有遞推公式 \({n \brace k} = {n - 1 \brace k - 1} + k{n - 1 \brace k}\)，可以手算出 \({3 \brace 2} = {2 \brace 1} + 2{2 \brace 2} = 3\)。

經過這幾道題的求解，可以總結出一些規律或者解題技巧，如遇到帶冪函數的和式可以考慮轉化為下降冪進行有限積分。

將例6和例7總結可以得到自然數冪和的公式：

此時進行有限微積分得：

加上很重要的式子：\(x^{\underline n} = \Delta ({x^{\underline {n+1}} \over n + 1})\)

不定和式

剛剛講了定和式，相應的也有不定和式（即不存在上下界的和式），這種和式求和后只能算得另一個新函數，而不是具體的值（相當于原函數與積分函數的關系）

其中 \(C\) 類比于積分中的常數 \(C\)，一般通過特值得到。

對于差分中的乘法法則 \(\Delta(uv) = u\Delta v + Ev\Delta u\)

移項后得到分布求和法則：

例題8

求解 \(\sum\limits_{i = 0}^{n - 1} i^{\underline k}a^i,a\ne 1,k\) 較小。

解：直接套用分布求和法則

由于

分布求和中 \(u = x^{\underline k},\Delta v =a^x = {\Delta ({ a^x \over a - 1})},E = (x+1)\)

所以 \(v = \left( {a^x \over a - 1} \right),\Delta u = kn^{\underline {k - 1}}\)

這一步是發現最后那個和式就是原式的 \(k\) 變為 \(k - 1\)，暴力拆開，會變成一大坨東西乘起來，最后歸納一下得出公式（其實是我不知道怎么歸納）

因此 \(\large{\sum\limits_{i = 0}^{n - 1} i^{\underline k}a^i = \sum_{0}^{n} x^{\underline k}a^x \delta x = {a^x \over a -1}\sum_{i=0}^{k}\left({-a \over a - 1}\right)^ik^{\underline i}(a^n n^{\underline {k - i}} - a^0 0^{\underline {k - i}})}\)

這個公式應用性較強。