【前文链接：《关于前n项自然数多次方求和公式的组合数学推导方法(一)》https://blog.yidaz.net/blog/2020/05/12/%e5%85%b3%e4%ba%8e%e8%87%aa%e7%84%b6%e6%95%b0%e5%89%8dn%e9%a1%b9%e7%9a%84p%e6%ac%a1%e6%96%b9%e6%b1%82%e5%92%8c%e5%85%ac%e5%bc%8f%e6%8e%a8%e5%af%bc/ 】

3. 差分表

【本节内容含有部分线性代数概念】
定义一个集合$V$包含所有的数列$\{a_n\}_{n=0}^{\infty} \in R$
再定义数列的两种运算：加法和乘法
$\forall \{a_n\}_{n=0}^{\infty}, \{b_n\}_{n=0}^{\infty} \in V, \alpha \in R$,
$$
\begin{align}
&\{a_n\}_{n=0}^{\infty} + \{b_n\}_{n=0}^{\infty} = \{a_n + b_n\}_{n=0}^{\infty}\\\\
&\{a_n\}_{n=0}^{\infty} \cdot \{b_n\}_{n=0}^{\infty} = \{a_n \cdot b_n\}_{n=0}^{\infty}\\\\
&\alpha \cdot \{a_n\}_{n=0}^{\infty} = \{\alpha a_n\}_{n=0}^{\infty}
\end{align}
$$
再定义 数列$0_V$ = $\{0\}_{n=0}^{\infty} = 0,0,0…$, 数列$1_V$ = $\{1\}_{n=0}^{\infty} = 1,1,1…$
注意$0_V + \{a_n\}_{n=0}^{\infty} = \{a_n\}_{n=0}^{\infty}$, $0_V \cdot \{a_n\}_{n=0}^{\infty} = 0_V$, $1_V \cdot \{a_n\}_{n=0}^{\infty} = \{a_n\}_{n=0}^{\infty}$

举例: 定义 $a = \{n+1\}_{n=0}^{\infty}, b = \{n – 1\}_{n=0}^{\infty}$
$$
\begin{align}
&a + b = \{2n\}_{n=0}^{\infty} = 0,2,4,…,2n,…\\
&a \cdot b = \{n^2 – 1\}_{n=0}^{\infty} = -1, 0, 3, 8,…,n^2 -1,…\\
&2a = \{2n + 2\}_{n=0}^{\infty} = 2,4,6,8,…,2n+2,…
\end{align}
$$
拓展：【根据我们定义的$+, \cdot, 0_V$和$1_V$, 可以验证$V$是定义在实数域$R$上的一个向量空间($\textit{vector space}$)】

让$h = \{h_n\}_{n=0}^{\infty} \in V$,
现在定义一个函数 $\Delta : V \rightarrow V,\Delta (h) = \Delta h$，
其中 $$
\begin{align}
&\Delta h = \{\Delta h_n\}_{n=0}^{\infty} = \{h_{n+1} – h_n\}_{n=0}^{\infty},\\
& \Delta h_n = h_{n+1} – h_n, n \geqslant 0
\end{align}$$
数列$\Delta h = \Delta h_0, \Delta h_1, \Delta h_2,…$被称为差分数列($\textit{difference sequence}$)。
差分数列的第$n$项可以看作是原数列的第$n+1$项与第$n$项之差。

根据以上定义可易证，差分数列具有以下性质：
$\forall h,h’ \in V, \alpha \in R,$
$$
\begin{align}
\Delta 0_V &= 0_V \\\\
\Delta(h + h’) &= \Delta h + \Delta h’ \\\\
\alpha \Delta h &= \Delta(\alpha h)
\end{align}
$$
拓展：【满足以上性质说明$\Delta$是向量空间$V$的一个线性变换 $(linear \ transformation)$。】

运用以上性质可得出下列等式：
$\forall h_i \in V, \alpha_i \in R, 0 \leqslant i \leqslant k, k\in N,$
$$
\Delta( \sum_{i = 0}^{k} \alpha_i h_i) = \sum_{i = 0}^{k} \Delta (\alpha_i h_i) = \sum_{i = 0}^{k} \alpha_i \Delta h_i \qquad (3.1)
$$

差分数列可以继续产出差分数列。定义$\Delta (\Delta h) = \Delta^2 h$, $\Delta^2 h$叫做$h$ 的第二阶差分数列。同理，$h$的第$p$阶差分数列$\Delta^p h= \Delta (\Delta^{p-1} h)$。
并且，定义$\Delta^0 h = h$。
至此，我们可以通过一个数列$h$的$p$阶差分数列($p = 0,1,2,3,…$)得出$h$的差分表($\textit{difference table}$):
$$\begin{align}
&h_0 \quad h_1 \quad h_2 \quad h_3 \quad h_4 \quad \cdots\\\\
&\ \ \Delta h_0 \ \ \Delta h_1 \ \Delta h_2 \ \Delta h_3 \ \ \cdots\\\\
& \quad \ \ \Delta^2 h_0 \, \Delta^2 h_1 \, \Delta^2 h_2 \ \cdots\\\\
& \qquad \quad \Delta^3 h_0 \ \Delta^3 h_1 \ \cdots\\\\
& \qquad \qquad \quad \cdots
\end{align}
$$
举例: 对于数列$ h = \{h_n\}_{n=0}^{\infty}, h_n = 2n^2 + 3n + 1 \quad (n \geqslant 0)$,此数列的差分表为:
$$\begin{align}
h: \ &1 \quad 6 \quad 15 \quad 28 \quad 45 \quad 66 \quad 91 \ \cdots\\\\
\Delta h: \ &\ \ \ 5 \ \ \ \ \ 9 \ \quad 13 \ \ \ \ 17 \ \ \ \ 21 \ \ \ 25 \ \cdots\\\\
\Delta^2 h: \ & \quad \ \ \ 4 \quad \ 4 \quad \ \ 4 \quad \ \ 4 \quad \ \ 4 \ \cdots\\\\
\Delta^3 h: \ & \qquad \quad 0 \ \quad 0 \quad \ \ 0 \quad \ \, 0 \ \cdots\\\\
& \qquad \qquad \quad \cdots
\end{align}
$$
再定义一个数列$p = \{p_n\}_{n=0}^{\infty}, p_n = n^4 \quad (n \geqslant 0)$,此数列的差分表为:
$$\begin{align}
p: \ &0 \quad 1 \quad 16 \quad 81 \quad 256 \quad 625 \quad 1296 \ \cdots\\\\
\Delta p: \ &\ \ \ 1 \ \ \ \ 15 \ \ \ 65 \ \ \ \ 175 \ \ \ \, 369 \ \ \ \ 671\ \cdots\\\\
\Delta^2 p: \ & \quad \ \ 14 \ \ \ 50 \ \ \ 110 \ \ \ 194 \ \ \ \ 302 \ \cdots\\\\
\Delta^3 p: \ & \qquad \ \ 36 \ \ \ \ 60 \ \ \ \ 84 \quad \, 108 \ \cdots\\\\
\Delta^4 p: \ & \qquad \quad \ \ 24 \ \ \ \ 24 \ \ \ \ 24 \ \cdots\\\\
\Delta^5 p: \ & \qquad \qquad \ \ \ \ 0 \quad \ \,0 \ \cdots\\\\
& \qquad \qquad \quad \cdots
\end{align}
$$
观察发现，对于数列$h$，$h_n = 2n^2 + 3n + 1$, $(2n^2 + 3n + 1)$作为$n$的一个多项式的次数($\textit{degree}$)定义为其中所有单项式的最高次数，这里$2n^2$的次数为$2$并高于其他项的次数，所以$(2n^2 + 3n + 1)$的次数为$2$, 写作$deg(2n^2 + 3n + 1) = 2$。根据差分表可以合理猜测第三阶差分数列$\Delta^3 h = 0,0,0… = 0_V$。
同样观察可得，对于数列$p$, $n^4$的次数为$4$，并且观察猜测此数列的第五阶差分数列$\Delta^5 h = 0,0,… = 0_V$。
这里推出以下猜测：

命题$3.2$: 对于任何数列$h \in V$和一个自然数$p$,
如果$h_n = n^p, n \geqslant 0$, 则$\Delta^{p+1} h = 0_V$

命题$3.3$: 对于任何数列$h \in V$和一个自然数$p$,
如果$h_n = f(n), n \geqslant 0$, $f(n)$为$n$的实数系数的多项式，且$ deg(f(n)) = p$,
则$\Delta^{p+1} h = 0_V$
如果后者是正确的，从命题$3.3$就可以推出命题$3.2$，这里我们直接证明$3.3$。

$(3.3)$证明：
让$p \in N$，定义$P(p)$: 如果$h \in V, h_n = f(n), n\geqslant 0$, $deg(f(n)) = p$,则$\Delta^{p+1} h = 0_V$

利用(强)归纳法证明$\forall p \in N, P(p)$成立:

$\cdot$基本情况：
当$p = 0$, 假设$h\in V, h_n = f(n), n \geqslant 0, deg(f(n)) = 0$,
注意$deg(f(n)) = 0$当且仅当$f(n) = c \in R$, 所以$h_n = c,c,c…,$ $\Delta^1 h = 0,0,0,… = 0_V$, $P(0)$成立。

$\cdot$归纳步骤:
$\quad$ $\cdot$归纳假设：对于整数$k \geqslant 0,$对于所有整数$k’,$ $0\leqslant k’\leqslant k,$ $P(k’)$成立。
$\quad $ $\cdot$证明如果所有$P(k’)$成立(归纳假设成立)，$P(k+1)$成立:
$\quad \ \ \ $假设$h \in V, h_n = f(n), n\geqslant 0$, $deg(f(n)) = k + 1$,
$\quad \ \ \ $(需要证明$\Delta^{k+2} h = 0_V$)
$\quad \ \ \ $则$\exists a_i \in R, 0 \leqslant i \leqslant k+1$,
$$
f(n) = \sum_{i = 0}^{k+1} a_i n^i
$$
$\quad \ \ \ $所以
$$
h = \{f(n)\}_{n=0}^{\infty} = \{ \sum_{i = 0}^{k+1} a_i n^i\}_{n=0}^{\infty}
$$
$\qquad$使用等式$(3.1)$, 可得
$$
\begin{align}
\Delta^{k+2} h &= \Delta^{k+2}\{ \sum_{i = 0}^{k+1} a_i n^i\}_{n=0}^{\infty} = \Delta^{k+2} (\sum_{i = 0}^{k+1} \{a_i n^i\}_{n=0}^{\infty})\\
&= \Delta^{k+2} (\sum_{i = 0}^{k+1} a_i\{ n^i\}_{n=0}^{\infty}) = \sum_{i = 0}^{k+1} a_i\Delta^{k+2} \{ n^i\}_{n=0}^{\infty}\\
&= \underbrace{\sum_{i = 0}^{k} a_i\Delta^{k+2} \{ n^i\}_{n=0}^{\infty}}_{= \ ?} + a_{k+1}\Delta^{k+2} \{ n^{k+1}\}_{n=0}^{\infty} \quad (3.4)
\end{align}
$$
$\quad$ 对于$(\sum_{i = 0}^{k} a_i\Delta^{k+2} \{ n^i\}_{n=0}^{\infty})$的每一项$a_i\Delta^{k+2} \{ n^i\}_{n=0}^{\infty}, 0 \leqslant i \leqslant k$。
$\quad$ 注意数列$\{ n^i\}_{n=0}^{\infty}, deg(n^i) = i, $根据归纳假设，$\Delta^{i+1} \{ n^i\}_{n=0}^{\infty} = 0_V$
$\quad$ 又因为$i+1 \leqslant {k+1} < {k+2}, $ $i +1$是一个小于$k+2$的整数，所以$$
\begin{align}
a_i\Delta^{k+2} \{ n^i\}_{n=0}^{\infty} &= a_i(\Delta^{k-i+1} \Delta^{i+1} \{ n^i\}_{n=0}^{\infty}) \\\\
&= a_i(\Delta^{k-i+1} (\Delta^{i+1} \{ n^i\}_{n=0}^{\infty}))\\\\
&= a_i(\Delta^{k-i+1}0_V)\\\\
&= a_i\cdot 0_V\\\\
&= 0_V
\end{align}
$$
$\quad$由此可得$$
? = \sum_{i = 0}^{k} a_i\Delta^{k+2} \{ n^i\}_{n=0}^{\infty} = \underbrace{0_V + 0_V + … +0_V}_{k+1} = 0_V
$$
$\quad$根据等式$(3.4)$,
$$
\begin{align}
\Delta^{k+2}h &= \underbrace{\sum_{i = 0}^{k} a_i\Delta^{k+2} \{ n^i\}_{n=0}^{\infty}}_{= \ ? \ = \ 0_V} + a_{k+1}\Delta^{k+2} \{ n^{k+1}\}_{n=0}^{\infty}\\
&= 0_V + a_{k+1}\Delta^{k+2} \{ n^{k+1}\}_{n=0}^{\infty}\\\\
&= a_{k+1}\Delta^{k+2} \{ n^{k+1}\}_{n=0}^{\infty}\\\\
&= a_{k+1}\Delta^{k+1} (\Delta \{ n^{k+1}\}_{n=0}^{\infty}) \qquad (3.5)
\end{align}
$$
$\quad$假设$\Delta \{ n^{k+1}\}_{n=0}^{\infty} = \{ g_n\}_{n=0}^{\infty},$根据差分数列的定义，
$$
\begin{align}
\forall n \geqslant 0, g_n &= (n+1)^{k+1} – n^{k+1} \\
& \qquad \downarrow (2.2)\\
&= \sum_{i = 0}^{k+1} \binom{k+1}{i} n^{i} – n^{k+1} \\\\
&= (\sum_{i = 0}^{k} \binom{k+1}{i} n^{i} + \binom{k+1}{k+1} n^{k+1}) – n^{k+1} \\\\
&= \sum_{i = 0}^{k} \binom{k+1}{i} n^{i}
\end{align}
$$
$\quad$ 注意$\sum_{i = 0}^{k} \binom{k+1}{i} n^{i}$是关于$n$的一个多项式，且次数为$k$。
$\quad$ 因为$k \leqslant k,$根据归纳假设，$$\Delta^{k+1}(\{ g_n\}_{n=0}^{\infty} )= \Delta^{k+1} (\Delta \{ n^{k+1}\}_{n=0}^{\infty}) = 0_V$$
$\quad$把它代入回等式$(3.5)$
$$
\begin{align}
\Delta^{k+2} h &= a_{k+1}\Delta^{k+1} (\Delta \{ n^{k+1}\}_{n=0}^{\infty}) \\\\
&= a_{k+1}\cdot 0_V \\\\
&= 0_V
\end{align}
$$
$\quad$因此，$P(k+1)$成立，归纳完毕，证明结束。

经过以上证明我们得到了定理$(3.6)$:

对于任何数列$h \in V$和一个自然数$p$,
如果$h_n = f(n), n \geqslant 0$, $f(n)$为$n$的实数系数的多项式，且$ deg(f(n)) = p$,
则$\Delta^{p+1} h = 0_V$

举例: 取$\{ a_n\}_{n=0}^{\infty} = \{ n^{99} + n^{66} + 33\}_{n=0}^{\infty} \in V$, 则$\Delta^{100} \{ a_n\}_{n=0}^{\infty}= 0_V$

【后续章节将会讨论定理$(3.6)$对解决本文问题的重要性。】

备注：本文未对一些定义做明确解释，如有任何问题请在评论区留言或者私信我，谢谢。

$\textit{To be continued}$