离散微积分学习笔记

· · 个人记录

后向差分

对于函数 f(x) 定义等距节点 x_k = x_0 + k \Delta x。

有：

\Delta f(x_k) = f(x_{k}) - f(x_{k-1})

下文简称差分。

高阶差分

一般来说，k 阶差分的定义如下：

\Delta^k a_n = \Delta (\Delta ^{k-1} a_n)

易得 k 阶差分公式：

\Delta^k a_n = \sum_{i=0}^{k} C_i^{k} (-1)^{k-i}a_{n+i}

差分公式

四则运算的公式和微分一致，可惜的是并不存在所谓的复合函数差分公式。

求和

我们称：

\sum f(n) \Delta n

为 f 的不定求和。

求和公式

\sum a_n \Delta f(n) = a_n +C

这里 C 是一个差分为 0 的函数。

差分表

\Delta C = 0 \Delta n = 1 \Delta n^k = \sum_{i=0}^{k-1} C_{i}^{k} n^i \Delta \ln n = \ln (1 + \frac{1}{n}) \Delta a^n = (a-1)a^{n-1}

不定求和表

这里我们探讨一个有意思的问题：

求 \sum k^n

事实上，因为：

\Delta k^n = (k-1)k^{n-1}

所以：

k^n = (k-1) \sum k^{n-1} + C

自然：

\sum k^n = \frac{k^{n+1}}{k-1} + C

分部积分（阿贝尔恒等式）

\sum_{i=1}^{n} a_{i}b_{i} = b_n \sum_{i=1}^{n} a_{i} + \sum_{i=1}^{n-1} \Delta {b_{i+1}} \sum_{i=1}^{n} a_i

下降幂

\Delta C_{n}^{k} = k \times C_{n}^{k-1}

组合数拆解原数列

a_{n} = \sum_{k=0} \Delta^{k}a_{0} \times C_{n}^{k+1}