数学里也有差分？
jiezecheng
·
·
算法·理论
part 1 ：一道填空题
同学们，咱们先来看这样一个填空题：
1,2,4,8,16,31,57,?,?
emm貌似看不出什么来，但可以发现第 2\sim 5 项每一项都是前一项的两倍。虽然这不太重要吧。
接下来把从第 2 项之后的所有项都减去前一项，并把差值写在两个数之间。
\begin{matrix}
\quad 1\quad2\quad4\quad8\quad16\quad31\quad57\dots \\
1\quad2\quad4\quad8\quad15\quad26\dots
\end{matrix}
发现什么了吗，没有吧，没有就对了，还没完，我们再把新的数列从第 2 项之后的所有项都减去前一项，并把差值写在两个数之间。
\begin{matrix}
\quad 1\quad2\quad4\quad8\quad16\quad31\quad57\dots \\
1\quad2\quad4\quad8\quad15\quad26\dots\\
1\quad2\quad4\quad7\quad11\dots\\
1\quad2\quad3\quad4\dots\\
1\quad1\quad1\dots\\
\end{matrix}
现在就好了，最后一行的所有数都是 1 ，这样我们就可以倒着推回去了。
\begin{matrix}
\quad 1\quad2\quad4\quad8\quad16\quad31\quad57\quad{\color{Yellow} 99} \quad{\color{Yellow} 163} \dots \\
1\quad2\quad4\quad8\quad15\quad26\quad{\color{Yellow} 42} \quad{\color{Yellow} 64} \dots\\
1\quad2\quad4\quad7\quad11\quad{\color{Yellow} 16} \quad{\color{Yellow} 22} \dots\\
1\quad2\quad3\quad4\quad{\color{Yellow} 5} \quad{\color{Yellow} 6} \dots\\
1\quad1\quad1\quad{\color{Yellow} 1} \quad{\color{Yellow} 1} \dots\\
\end{matrix}
所以这道题的最终答案就是 99 和 163 了。
part 2 ：牛顿的差分
哎，这道题很神金没错，但 300 多年前的一个数学巨人牛顿也研究了这个问题。他发现整个数列从上到下实际上在求导数，而从下到上在求积分。
先回顾一下初中就学了的函数的 3 种表示方法，分别为：
- 解析法；
- 图像法；
- 列表法。
比如对于一个函数：
- 解析法：f(x)=x+1（有时可写作 y=x+1）。
- 图像法：
- 列表法：
| x |
-2 |
-1 |
0 |
1 |
2 |
| f(x) |
-1 |
0 |
1 |
2 |
3 |
好，最开始的数列其实就是一个函数，只不过由于自变量 x 只能取正整数，所以只能称为一个离散函数。那我们就可以用列表法来表示这个函数：
| x |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
| f(x) |
1 |
2 |
4 |
8 |
16 |
31 |
57 |
那么我们怎么求一个离散函数的导数呢，首先我们知道连续的函数的导数公式：
f'(x)=\lim_{\Delta x\to0}\frac{f(x+\Delta x)-f(x)}{\Delta x}
这个公式怎么来的不重要，你只需要知道 \Delta x 是一个非常非常小的值。
最精妙的一步来了，再这个离散函数中 \Delta x 的最小量就是 1 （因为并没有 f(1.1) 或其他小数函数值），所以我们直接带入 \Delta x=1：
f'(x)=f(x+1)-f(x)
当然，为了和其他导数作区分，我们用 \Delta f(x) 代替 f'(x)。
\Delta f(x)=f(x+1)-f(x)
这个东西我们就叫它差分，对，就是你想的那个差分。再细看一眼，记 a_i=f(i),d_i=\Delta f(i) 那么 d 数组就正是 a 的差分数组！
part 3 ：牛顿对函数的整理
牛顿觉得这个函数还是太麻烦，于是将其整理成一个公式：
F_n=\begin{pmatrix}n\\0\end{pmatrix}\Delta^0F_0+
\begin{pmatrix}n\\1\end{pmatrix}\Delta^1F_0+
\begin{pmatrix}n\\2\end{pmatrix}\Delta^2F_0+\dots+
\begin{pmatrix}n\\m\end{pmatrix}\Delta^mF_0+\dots
这里的 \begin{pmatrix}n\\m\end{pmatrix} 是组合数，也可记作 C^m_n。计算公式为：
\begin{pmatrix}n\\m\end{pmatrix}=C^m_n=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}
其中 \Delta^m 为原函数的 m 阶差分。即：
\Delta^m f(x)=\left\{\begin{matrix}
\Delta({\Delta^{m-1}f(x)})&m\ge 1\\
f(x)&m=0
\end{matrix}\right.
而且这个公式的 F_n 的下标是从 0 开始记录的，即 F_n 代表原数列第 n+1 项的值。
part 4 :回到最开始的问题
咱们套入最开始的那个问题。
F_n=\begin{pmatrix}n\\0\end{pmatrix}{\color{Yellow} 1} +
\begin{pmatrix}n\\1\end{pmatrix}{\color{Yellow} 1}+
\begin{pmatrix}n\\2\end{pmatrix}{\color{Yellow} 1}+
\begin{pmatrix}n\\3\end{pmatrix}{\color{Yellow} 1}+
\begin{pmatrix}n\\4\end{pmatrix}{\color{Yellow} 1}
带入组合数计算公式：
F_n=1+
n+
\frac{n(n-1)}{2!}+
\frac{n(n-1)(n-2)}{3!}+
\frac{n(n-1)(n-2)(n-3)}{4!}
拆括号：
f\left(x\right)=1+x+\frac{x^{2}-x}{2}+\frac{x^{3}-3x^{2}+2x}{6}+\frac{x^{4}-6x^{3}+11x^{2}-6x}{24}
化简：
f\left(x\right)=1+\frac{7}{12}x+\frac{11}{24}x^{2}-\frac{1}{12}x^{3}+\frac{1}{24}x^{4}
这样分别带入 x 的值就可求出原数列 x+1 项的值。
part 5 :其它关于差分
在数学中，差分函数（Difference） 是离散微积分中的核心概念，用于描述离散序列中相邻项的变化。它是连续函数导数的离散对应物，广泛应用于数值分析、组合数学、时间序列分析等领域。
差分的分类
对于给定的离散序列 \{x_n\} 或函数 f 在离散点上的取值 \{f(x_k)\} 其差分分为三种：
- 前向差分（Forward Difference）
\Delta f(k)=f(k+1)-f(k)
- 后向差分（Backward Difference）
\nabla f(k)=f(k)-f(k-1)
- 中心差分（Central Difference）
$\forall k\in \mathbb{N}^+ ,f(x)$与$f(k+h)$ 都有意义的最小值。
$$
\delta f(k)=f(k+\frac{h}{2})-f(k-\frac{h}{2})
$$
#### 差分的逆运算
离散差分的逆运算当然就是**离散积分**。
即为：
$$
S_k=\int_{0}^{k} a_idi
$$
当步长 $h=1$ 时，离散积分退化为求和
$$
S_k=\sum_{i=0}^{k} a_i
$$
## part $6$: 最后的闲话
数学的差分和信息学的差分有关联但不多，这篇文章写来的目的是为了让同学们可以对差分有新的认识，也可以将各学科联合起来，这是信息学与数学的联合。
本文鸣谢对象：
1. 画图软件desmos；
2. 此 [b站视频](https://www.bilibili.com/video/BV1GvoaYbExs/?spm_id_from=333.1387.collection.video_card.click&vd_source=b8b78e1425050eafec6959e4b471ed9b) 给了我灵感。