前文链接：
关于前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/
关于前n项自然数多次方求和公式的组合数学推导方法（二）：
https://blog.yidaz.net/blog/2020/05/31/%e5%85%b3%e4%ba%8e%e8%87%aa%e7%84%b6%e6%95%b0%e5%89%8dn1%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%e4%ba%8c%ef%bc%89/

4.对角数列

对于一个数列$h \in V$, 回顾第三章，我们定义了它的差分表:
$$
\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}
$$
这里标记下每一行的第一个数：
$$
\begin{align}
&\overline{h_0} \quad h_1 \quad h_2 \quad h_3 \quad h_4 \quad \cdots\\\\
&\ \ \overline{\Delta h_0} \ \ \Delta h_1 \ \Delta h_2 \ \Delta h_3 \ \ \cdots\\\\
& \quad \ \ \overline{\Delta^2 h_0} \, \Delta^2 h_1 \, \Delta^2 h_2 \ \cdots\\\\
& \qquad \quad \overline{\Delta^3 h_0} \ \Delta^3 h_1 \ \cdots\\\\
& \qquad \qquad \quad \cdots
\end{align}
$$

我们定义一个$h$的对角数列($\textit{diagonal sequence}$) $\{ \Delta^n h_0 \}_{n = 0} ^ \infty$
$$
\{ \Delta^n h_0 \}_{n = 0} ^ \infty = h_0, \Delta h_0, \Delta^2 h_0,…,\Delta^n h_0,…
$$
$\{ \Delta^n h_0 \}_{n = 0} ^ \infty$ 由$h$的差分表每一行的第一项组成，这些项可以像对角线一样连在一起，所以取名为对角数列。【注意$\Delta^n h_0$ 指的是数列$\Delta^n h$的第$0$项】

举例：

​ 对于数列$ 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}
$$
​ 如图可知，$h$的对角数列为
$$
\{ \Delta^n h_0 \}_{n = 0} ^ \infty = 1,5,4,0,0,0…
$$
​

​ 根据定理(3.6), $\Delta^3 h = 0_V$, 所以$\Delta ^p h = 0_V, p \geqslant 3$, 且$\Delta^p h_0 = 0$， 所以对角数列$\{ \Delta^n h_0 \}_{n = 0} ^ \infty$从第$4$个 数开始全为0。

从对角数列的定义我们可以推导出以下结论：

• 定理(4.1)

  对于数列$h \in V$, 如果对角数列$\{ \Delta^n h_0 \}_{n = 0} ^ \infty = 0_V$, 则 $h = 0_V$。

(4.1)证明：

假设存在数列$h \in V$, 且它的对角数列为$0_V$, 那么对于所有$n \geqslant 0$, $\Delta^n h_0 = 0$, 所以$h$的差分表的每一行的一个数为0，如图所示：
$$
\begin{align}
&0\quad h_1 \quad h_2 \quad h_3 \quad h_4 \quad \cdots\\\\
&\ \ 0 \ \ \ \Delta h_1 \ \Delta h_2 \ \Delta h_3 \ \ \cdots\\\\
& \quad \ \ 0 \ \ \, \Delta^2 h_1 \, \Delta^2 h_2 \ \cdots\\\\
& \qquad \ \ 0 \ \ \ \Delta^3 h_1 \ \cdots\\\\
& \qquad \qquad \cdots
\end{align}
$$
这里 $h_0 = \Delta^0 h_0 = 0$，同时注意 $\Delta h_0 = h_1 – h_0$，所以 $h_1 = h_0 + \Delta h_0 = 0 + 0 = 0$。

同理，$\Delta^2 h_0 = \Delta h_1 – \Delta h_0 = h_2 – h_1$，所以 $h_2 = h_1 + \Delta^2 h_0 = 0 + 0 = 0$。

我们现在得出$h_0 = h_1 = h_2 = 0$，按照相同思路可以得出$h$所有的项都为0。

但是当$n$足够大的时候，$h_n$的计算会变得非常繁琐，所以这里提供一个逻辑比较清晰的归纳法思路去证明此定理。

归纳法证明：引理(4.1.1)：对于$h \in V$, $\forall \ m \geqslant 0$, $0 \leqslant k \leqslant m$, 如果$h = \underbrace{0,0,…, 0}_{m \ 个0}, h_m,…$, ,则$\Delta^k h = \underbrace{0,0,…, 0}_{(m-k)个0}, h_m,…$。

​ $\cdot$基本情况：

​ 当$k = 0$, $\Delta^k h =\Delta^0 h = h = \underbrace{0,0,…, 0}_{(m-k)个0}, h_m,…$, 基本情况成立。

​ $\cdot$ 归纳步骤：

​ $\cdot$归纳假设：对于一个 $k$, $0 \leqslant k \leqslant m-1$, $\Delta^{k} h = \underbrace{0,0,…, 0}_{(m-k)个0}, h_m…$

​ $\cdot$在归纳假设的前提下证明 $\Delta^{k+1} h = \underbrace{0,0,…, 0}_{(m-(k+1))个0}, h_m…$ :

​ 因为$\Delta^{k} h = \underbrace{0,0,…, 0}_{(m-k)个0}, h_m…$, 可以得到
$$
\begin{align}
&\Delta^k h_{m-k} = h_m\\ \\
&\Delta^k h_{i} = 0, i < m-k
\end{align}
$$
​ 所以
$$
\Delta^{k+1}h_{m-(k+1)} = \Delta^k h_{m-k} – \Delta^k h_{m-(k+1)} = h_m – 0 = h_m
$$
​ 所以数列$\Delta^{k+1} h$的第$m-(k+1)$项为$h_m$。如果存在任何$h_m$之前的项，

​ 比如$\Delta^{k+1}h_i, i < m -(k+1)$ $\Rightarrow i+1 < m-k$
$$
\Delta^{k+1}h_i = \Delta^k h_{i+1} – \Delta^k h_i = 0 – 0 = 0
$$
​ 所以 $\Delta^{k+1} h = \underbrace{0,0,…, 0}_{(m-(k+1))个0}, h_m…$ 。归纳完毕，证明结束。引理(4.1.1) 成立。

回到原证明，我们已经证明了对角数列为$0_V$的数列 $h$ 前几项$h_0, h_1, h_2$都为0，这里再次利用归纳法证明所有$h_n = 0$。

强归纳法证明：对于$h \in V$, 如果$\{ \Delta^n h_0 \}_{n = 0} ^ \infty = 0_V$, 则$h_n = 0, n \geqslant 0$。

​ $\cdot$基本情况：已证明当$n = 0$，$h_0 = 0$。

$\cdot$ 归纳步骤：

​ $\cdot$归纳假设：对于$n \geqslant 1$, $\forall \ k, 0 \leqslant k \leqslant n$, $h_k = 0$。

​ $\cdot$在归纳假设的前提下证明 $h_{n+1} = 0$ :

​ 根据归纳假设，$h = \underbrace{0,0,…, 0}_{(n+1)个0}, h_{n+1},…$。

​ 根据引理(4.1.1)，$\Delta^{n+1} h = h_{n+1}, \Delta^{n+1} h_1,…$ ，

​ 所以
$$
h_{n+1} = \Delta^{n+1} h_0 = 0
$$
​ 归纳完毕，定理(4.1)证明结束。

利用定理(4.1)可以推导出下个推论。

• 推论(4.2)

  对于数列$h, h' \in V$, 如果$\{ \Delta^n h_0 \}_{n = 0} ^ \infty = \{ \Delta^n h'_0 \}_{n = 0} ^ \infty$($h$和$h'$的对角数列相等)，则$h = h'$。

(4.2)证明：

想要证明 $h = h'$ ，需要证明$\forall \ n \geqslant 0$, $h_n = h'_n$。

定义一个数列$\{a_n\}_{n=0}^{\infty} \in V$, $a_n = h_n – h'_n, n \geqslant 0$。

数列$\{a_n\}_{n=0}^{\infty}$可以看成是$h$与$h'$两个数列之差得到的数列，此数列的对角数列为$\{\Delta ^n a_0\}_{n=0}^{\infty}$。

$\forall \ n \geqslant 0$,
$$
\Delta^n a_0 = \Delta^n(h – h')_0 = \Delta^nh_0 – \Delta^n h'_0
$$
又因为 $\{ \Delta^n h_0 \}_{n = 0} ^ \infty = \{ \Delta^n h'_0 \}_{n = 0} ^ \infty$，$\Delta^n h_0 = \Delta^n h'_0$。

所以
$$
\Delta^n a_0 = \Delta^nh_0 – \Delta^n h'_0 = 0 \\
$$
我们得到了$\{\Delta ^n a_0\}_{n=0}^{\infty} = 0_V$, 根据定理(4.1), $\{a_n\}_{n=0}^{\infty} = 0_V$

$\forall \ n \geqslant 0,$
$$
\begin{align}
&a_n = h_n – h'_n = 0 \\\\
& \qquad h_n = h'_n\\\\
& \qquad \ \ h = h'
\end{align}
$$
推论(4.2)证明完毕。

推论(4.2) 说明只要俩个$V$里的数列拥有同样的对角数列，那这俩个数列相等。所以对于一个未知数列 $a$，如果我们知道了它的对角数列，以及另一个已知数列 $b$ 拥有同样的对角数列，那么推论可以得出 $a = b$。

如果能通过 $a$ 的对角数列来构造出 $b$，我们就能得到数列 $a$。

事实上对于特殊的对角数列是可以做到这一步的，比如对于数列$h \in V$,

如果
$$
\{ \Delta^n h_0 \}_{n = 0} ^ \infty = c_0, c_1,…, c_p,0,0,0,… \quad, c_i \in R, \ 0\leqslant i \leqslant p
$$

使用二项次系数可以构造出数列 $h'$ 拥有同样的对角数列，$h = h'$。

在这之前先推导一个引理：

• 引理(4.3)

  取整数$p \geqslant 0$, 对于数列$\{ \binom{n}{p} \}_{n = 0} ^ \infty$, 它的对角数列为
  $$
  0,0,…,0,\underbrace{1}_{第 p 项},0,0,…
  $$
  (4.3)证明：

对于 $p \geqslant 0$,
$$
\{ \tbinom{n}{p} \}_{n = 0} ^ \infty = \tbinom{0}{p}, \tbinom{1}{p}, \tbinom{2}{p}, … ,\tbinom{p}{p}, \tbinom{p+1}{p},… = 0,0,…,0,\underbrace{1}_{第p项},p,…
$$
注意数列$\{ \tbinom{n}{p} \}_{n = 0} ^ \infty$的前 $(p-1)$ 项都为0，且第 $p$ 项为1。

根据引理(4.1.1)，对于整数 $k$ ,$0 \leqslant k \leqslant p$,
$$
\Delta^k(\{ \tbinom{n}{p} \}_{n = 0}^\infty) = \underbrace{0,…,0}_{(p-k)个0},1,…
$$
当 $0 \leqslant k

0$, 所以 $\Delta^k(\{ \tbinom{n}{p} \}_{n = 0}^\infty)_0 = 0$，

当 $k = p$，$p – k = 0$, 所以$\Delta^k(\{ \tbinom{n}{p} \}_{n = 0}^\infty)_0 = 1$。

我们已经知道了对角数列 $\{\Delta^m(\{ \tbinom{n}{p} \}_{n = 0}^\infty)_0\}_{m = 0}^{\infty}$ 的前 $p$ 项的值。

注意
$$
\binom{n}{p} = \frac{\overbrace{n(n-1)(n-2)\cdots(n-p+1)}^{p个多项式相乘}}{p(p-1)(p-2)\cdots2\cdot1} = f(n)
$$

$f(n)$ 代表一个关于 $n$ 的多项式且最高次数为 $p$，

所以
$$
\{ \tbinom{n}{p} \}_{n = 0} ^ \infty = \{ f(n)\}_{n = 0} ^ \infty
$$
根据定理(3.6),
$$
\Delta^{p+1} \{ f(n) \}_{n = 0}^{\infty} = 0_V
$$

所以对于 $\forall m > p$，
$$
\Delta^{m} \{ f(n) \}_{n = 0}^{\infty} = \Delta^{m-(p+1)}(\Delta^{p+1}\{ f(n) \}_{n = 0}^{\infty}) = \Delta^{m-(p+1)}0_V = 0_V
$$
因此，
$$
\Delta^{m} (\{\tbinom{n}{p} \}_{n = 0}^\infty)_0 = \Delta^{m} (\{ f(n) \}_{n = 0}^{\infty})_0 = (0_V)_0 = 0
$$
对角数列中所有在第 $p$ 项 ($1$) 以后的值都为 $0$，所以此数列为：
$$
\{\Delta^m(\{ \tbinom{n}{p} \}_{n = 0}^\infty)_0\}_{m = 0}^{\infty} = 0,0,…,0,\underbrace{1}_{第p项},0,…
$$
引理(4.3) 证明完毕。

(4.3) 举例：数列 $\{\tbinom{n}{3} \}_{n = 0}^\infty$ 的对角数列为 $0,0,0,1,0,…$。

利用此引理可以得到下列重要定理。

• 定理(4.4)

​ 取整数$p \geqslant 0$, $c_0, c_1,…, c_p \in R$,
​ 如果$\exists \ h \in V$,
$$
\{ \Delta^n h_0 \}_{n = 0} ^ \infty = c_0, c_1,…, c_p,0,0,0,…
$$
​ 则
$$
h_n = c_0 \binom{n}{0} + c_1 \binom{n}{1} + c_2 \binom{n}{2} + \cdots + c_p \binom{n}{p}, \ n \geqslant 0
$$

(4.4)证明：

定义数列 $a = \{ a_n \}_{n = 0} ^ \infty = \{c_0 \binom{n}{0} + c_1 \binom{n}{1} + c_2 \binom{n}{2} + \cdots + c_p \binom{n}{p} \}_{n = 0} ^ \infty$，

需要证明
$$
\{ \Delta^n a_0 \}_{n = 0} ^ \infty = \{ \Delta^n h_0 \}_{n = 0} ^ \infty = c_0, c_1,…, c_p,0,0,0,…
$$
为了方便显示，这里定义另一种数列表示方法：$\{ a_n \}_{n = 0} ^ \infty = \{a_n\}$。

使用定义的数列运算：
$$
\begin{align}
\{ \Delta^n h_0 \}_{n = 0} ^ \infty &= c_0, c_1,…, c_p,0,0,0,… \\\\
& = (c_0,0,0,…) + (0,c_1,0,…) + \cdots + (\underbrace{0,…,0}_{p个0},c_p,0,…) \\
& = c_0 \cdot(1,0,0,…) + c_1 \cdot(0,1,0,…) + \cdots + c_p \cdot(\underbrace{0,…,0}_{p个0},1,0,…)\\
(4.3) \Rightarrow \quad \ & = c_0 \{\Delta^m (\{\tbinom{n}{0}\})_{0}\} + c_1 \{\Delta^m (\{\tbinom{n}{1}\})_{0}\} +
\cdots + c_p \{\Delta^m (\{\tbinom{n}{p}\})_{0}\}\\\\
& = \{c_0 \cdot \Delta^m (\{\tbinom{n}{0}\})_{0} + c_1 \cdot \Delta^m (\{\tbinom{n}{1}\})_{0} + \cdots+
c_p \cdot \Delta^m (\{\tbinom{n}{p}\})_{0}\}\\\\
& = \{\Delta^m (\{c_0\tbinom{n}{0}\})_{0} + \Delta^m (\{c_1\tbinom{n}{1}\})_{0} + \cdots+
\Delta^m (\{c_p\tbinom{n}{p}\})_{0}\}\\\\
& = \{\Delta^m (\{c_0\tbinom{n}{0}\}_{0} + \{c_1\tbinom{n}{1}\}_{0} + \cdots + \{c_p\tbinom{n}{p}\}_{0}\}\\\\
& = \{\Delta^m \{c_0 \tbinom{n}{0} + c_1 \tbinom{n}{1} + \cdots + c_p \tbinom{n}{p} \}_0 \}\\\\
& = \{ \Delta^n a_0 \}_{n = 0}^{\infty}
\end{align}
$$

因为数列 $a$ 与 $h$ 的对角数列相同，根据推论(4.2) $a = h$。

$\forall \ n \geqslant 0$,
$$
h_n = a_n = c_0 \binom{n}{0} + c_1 \binom{n}{1} + c_2 \binom{n}{2} + \cdots + c_p \binom{n}{p}
$$

定理(4.4) 证明完毕。

此定理提供了一种通过对角数列还原原数列的方法，也直接帮助我们解决了第二章遗留的问题：

是否存在 $a,b,c,d \in R, \forall \ n \geqslant 0,$
$$
n^4 = a\binom{n}{4} + b\binom{n}{3} +c\binom{n}{2} + d\binom{n}{1}
$$

这里利用定理(4.4)找出这些值：

定义数列 $ p = \{ n^4\}_{n = 0} ^{\infty} \in V$, 给出它的差分表：
$$
\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 \quad \cdots
\end{align}
$$
如图所示，$p$ 的对角数列前 $5$ 项($0 \rightarrow 4$) 为 $0,1,14,36,24$,

由定理(3.6)可得，$\Delta^5 p = 0_V$, 易证对角数列从第 $5$ 项开始都为 $0$。

所以
$$
\{\Delta^n p_0\}_{n = 0}^{\infty} = 0,1,14,36,24,0,0,…
$$
根据定理(4.4)，

$\forall \ n \geqslant 0$,
$$
p_n = n^4= 0 \cdot \binom{n}{0} + 1 \cdot \binom{n}{1} + 14 \cdot \binom{n}{2} + 36 \cdot \binom{n}{3} + 24 \cdot \binom{n}{4}
$$
所以 $n^4$ 被成功写成了二项式系数的系数和，回顾第二章使用的方法，可以得到前 $n$ 项 ($n \geqslant 1$)自然数的四次方求和公式：
$$
\begin{align}
&1^4 + 2^4 + 3^4 + \cdots + n^4\\\\ =& \sum_{k = 0}^{n} k^4 \\\\
=& \sum_{k = 0}^{n} (\binom{k}{1} + 14\binom{k}{2} + 36\binom{k}{3} + 24\binom{k}{4})\\\\
=& \sum_{k = 0}^{n} \binom{k}{1} + 14\sum_{k = 0}^{n} \binom{k}{2} + 36\sum_{k = 0}^{n} \binom{k}{3} + 24\sum_{k = 0}^{n} \binom{k}{4}\\\\
=& \binom{n+1}{2} + 14\binom{n+1}{3} + 36\binom{n+1}{4} + 24\binom{n+1}{5}
\end{align}
$$

同理，对于任何 $p \in Z^+$, 定义数列 $\{ n^p\}_{n = 0} ^{\infty} \in V$,

通过差分表可以找到其对角数列的前 $p$ 项 $c_0, c_1, c_2, …, c_p \in R$,

此对角数列为 $c_0, c_1, c_2,…, c_p, 0,0,…$

根据定理(4.4), $\forall \ n \geqslant 0$,
$$
n^p= c_0 \cdot \binom{n}{0} + c_1 \cdot \binom{n}{1} + c_2 \cdot \binom{n}{2} + \cdots + c_p \cdot \binom{n}{p}
$$
我们可以得出前 $n$ 项自然数的任意 $P$ 次方求和公式：
$$
1^p + 2^p + 3^p + \cdots + n^p = c_0 \cdot \binom{n+1}{1} + c_1 \cdot \binom{n+1}{2} + c_2 \cdot \binom{n+1}{3} + \cdots + c_p \cdot \binom{n+1}{p+1} \qquad (4.5)
$$

虽然 $c_0, c_1, c_2,…, c_p$ 这些系数可以通过构造差分表来计算得出，但当 $p$ 足够大时，差分表每一行的计算量会很大，这些系数的获取难度陡增。

所以我们能否不用差分表的方法，而是通过一个特殊的公式算出来这些系数，答案会在最终章第五章揭晓。

5. 第二类斯特林数

To be continued