0.基本定义

• 数学符号:
  • $\forall$ : 所有
  • $\exists$ : 存在
  • $\in$：属于
• $R$: 实数集
• $N$: 自然数集，包括$0,1,2,3,4,\cdots$
• $Z^+$: 正整数集
• $\{a_n\}_{n=0}^{\infty} \in R$: $R$里的一个数列$a_0, a_1, a_2, a_3, \cdots, a_n, \cdots$。
  • 数列的项: $a_n$表示数列第 $n$ 项，数列从第 $0$ 项开始。
  • 数列的 $=$ ：数列 $a = b$ 当且仅当 $ \forall \ n \geqslant 0, a_n = b_n$。
• $n!$: 一个自然数的阶乘, $n! = n(n-1)\cdots2\cdot1$,定义 $0! = 1$

【本文所有未明确定义集合的变量都默认为整数】

1.序章

先说一个耳熟能详的故事，据说高斯上小学的时候，他的数学老师在一节课上提了个难题: $$1 + 2 + 3 + 4 + … + 100 = ?$$
在其他小朋友从第头开始算的时候，高斯几秒就说出了答案: $5050$。老师感到很诧异，因为他自己曾经真的从头到尾加过一次，答案就是$5050$。于是他就请教了高斯，高斯回复到，我们从第一个和最后一个数开始看，$1 + 100 = 101$, 然后以此列推，$2 + 99 = 101, 3 + 98 = 101$, 最后到$50 + 51 = 101$中间总共有$50$组$101$加在一起，所以答案就是$5050$。
高斯这套巧妙的解法可以用来推导出实数的等差数列的前n项求和公式。
对于一个等差数列$\{a_n\}_{n=0}^{\infty} \in R$，$\forall n \in N, a_{n+1} = a_n + d, d \in R$，所以这个数列前$n + 1$项之和为 $$\sum_{k=0}^{n} a_k = a_0 + (a_0 + d) + (a_0 + 2d) + \cdots+ (a_0 + (n-1)d) + (a_0 + nd) $$
调整下顺序 $$\sum_{k=0}^{n} a_k = (a_0 + nd) + (a_0 + (n-1)d) +\cdots+ (a_0 + 2d) + (a_0 + d) + a_0$$
将两式子相加，我们就能得到
$$
\begin{split}
2\sum_{k=0}^{n} a_k &= \underbrace{(2a_0 + nd) + (2a_0 + nd) + \cdots+ (2a_0 + nd) + (2a_0 + nd)}_{n+1}\\
&= (n+1) (2a_0 + nd) \\
&= 2(n + 1)a_0 + n(n+1)d
\end{split}
$$

所以我们能得到求和公式
$$
\sum_{k=0}^{n} a_k = (n+1)a_0 + \frac{n(n+1)d}{2} \qquad \qquad \left(1.1\right)
$$
现在再定义一个自然数数列$\{b_n\}_{n=0}^{\infty} = 0,1,2,3,4,…$，第一项$b_0 = 0$， 公差$d = 1$，根据$\left(1.1\right)$, 此数列前$n + 1$项之和为
$$
\sum_{k=0}^{n} b_k =\frac{n(n+1)}{2} \qquad \qquad \left(1.2\right)
$$
所以对于任何正整数$n\geqslant1$, $$
\begin{align}1 + 2 + 3 + \cdots+ n &= 0 + 1 +2 +3 + \cdots + n \\
&= \sum_{k=0}^{n} b_k = (n+1)0 + \frac{n(n+1)1}{2}\\
&= \frac{n(n+1)}{2} \qquad \qquad \left(1.3\right)
\end{align}$$
所以$1 + 2 +3 +4 +\cdots + 100$，根据 $\left(1.3\right)$等于$\frac{100(100 + 1)}{2} = 5050$。我们得到了和高斯一样的答案，$\left(1.3\right)$也就是从$1$到$n$之间连续自然数的求和公式。
现在提出新的问题，
我们知道了$1 + 2 + 3 + \cdots+ n = \frac{n(n+1)}{2}, n \in Z^+$, 那么
$$
\begin{align}
&1^2 + 2^2 + 3^2 + \cdots+ n^2 = \ ?\\
&1^3 + 2^3 + 3^3 + \cdots+ n^3 = \ ?\\
&1^4 + 2^4+ 3^4 + \cdots+ n^4 = \ ?\\
&\qquad \qquad \qquad\vdots\\
&1^p + 2^p+ 3^p + \cdots+ n^p = \ ? \qquad \qquad \left(\circledast \right)\\
\end{align}
$$
其中$p \in Z^+$,本文将给出一种组合数学方法解决以上问题。
$\\$

2.二项式系数

对于任意$n, k \in N$, 如果$n < k$, 定义$\binom{n}{k} = 0$。
如果$n\geqslant k$,定义$$\binom{n}{k} = \frac{n!}{k!(n-k)!} \qquad \qquad \left(2.1\right)$$
这里的$\tbinom{n}{k}$叫做二项式系数($\textit{binomial coefficient})$, 也就是组合数$C(n,k)$, 能表示从n个不同的物体里选出k个不同的物体总共有多少种选法。一般情况下当$1\leqslant k\leqslant n$, $\tbinom{n}{k}$才有这种组合意义，比如从$5$个同学里选两个去跑步，总共就有$\tbinom{5}{2} = 10$种选法。根据$\left(2.1\right)$的定义，$\binom{n}{0} = 1, \binom{n}{n} = 1$。
$\tbinom{n}{k}$被称为二项式系数来源于下面的二项式定理($\textit{binomial theorem})$

$\forall n \in Z^+, x,y \in R$,
$$(x+y)^n = \sum_{k = 0}^{n} \binom{n}{k}x^{n-k}y^k
\qquad \qquad \left(2.2\right)$$
举例：$
\begin{align}
(x + y)^2 &= x^2 + 2xy + y^2 \\
&= \binom{2}{0}x^2y^0 + \binom{2}{1}xy + \binom{2}{2}x^0y^2 \\
&= \sum_{k = 0}^{2} \binom{2}{k}x^{2-k}y^k
\end{align}$
可以发现$\tbinom{n}{k}$表示的就是对于$(x+y)$这个二项式的$n$次方结果里对于$x^{n-k}y^k$这一项的系数，所以叫二项式系数。此定理可以用归纳或组合的方法来证明。
同时，对于$n, k \in Z^+,$且$k\leqslant n$, 注意当$k < n$时，$$
\begin{align}
\binom{n – 1}{k} + \binom{n – 1}{k – 1} &= \frac{(n-1)!}{k!(n-k-1)!} + \frac{(n-1)!}{(k-1)!(n-k)!} \\
&= \frac{(n-1)!(n-k) + (n-1)!k}{k!(n-k)!} \\
&= \frac{n(n-1)! -(n-1)!k + (n-1)!k}{k!(n-k)!}\\
&= \frac{n!}{k!(n-k)!} = \binom{n}{k}
\end{align}
$$
此外当$k = n$时,
$$
\binom{n – 1}{k} + \binom{n – 1}{k – 1} = 0 + 1 = 1 = \binom{n}{k}
$$
所以我们得到了帕斯卡公式($\textit{Pascal's formula}$)
$$\binom{n – 1}{k} + \binom{n – 1}{k – 1} = \binom{n}{k} \qquad \qquad \left(2.3\right)$$
举例:
$$\binom{7}{3} + \binom{7}{2} = 35 + 21 = 56 = \binom{8}{3}$$
我们也可以同时多次使用帕斯卡公式
例如:
$$
\begin{align}
\binom{8}{3} &= \binom{7}{3}+ \binom{7}{2}\\
&= ( \binom{6}{3}+ \binom{6}{2}) + \binom{7}{2}\\
&= (\binom{5}{3} + \binom{5}{2}) + \binom{6}{2} + \binom{7}{2}\\
& \qquad \qquad \vdots\\
&= \underbrace{\binom{2}{3}}_{= 0} + \binom{2}{2} +\binom{3}{2} + \binom{4}{2} + \cdots + \binom{7}{2}\\
&= \underbrace{\binom{0}{2}+ \binom{1}{2}}_{= 0} + \binom{2}{2} +\binom{3}{2} + \binom{4}{2} + \cdots + \binom{7}{2}\\
&= \sum_{i = 0}^{7}{\binom{i}{2}}
\end{align}$$
从上面的例子我们可以用同样的方法得到一个推论:
$
\forall n, k \in N,k\leqslant n,
$
$$
\binom{n+1}{k+1} = \binom{0}{k} + \binom{1}{k} +\binom{2}{k} + \cdots + \binom{n-1}{k} + \binom{n}{k} = \sum_{i=0}^{n}{\binom{i}{k}} \qquad \left(2.4\right)
$$
这个推论提供了一种解决本文问题的思路，比如:
$$
\begin{align}
1 + 2 + 3 + 4 + \cdots + (n-1) + n &= 0 + 1 + 2 + 3 + 4 + \cdots + (n-1) + n\\
&= \binom{0}{1} + \binom{1}{1} + \binom{2}{1} + \binom{3}{1} + \cdots + \binom{n-1}{1} + \binom{n}{1}
= \sum_{i=0}^{n}{\binom{i}{1}}\\
&= \binom{n+1}{2} = \frac{(n+1)!}{2!(n-1)!} = \frac{n(n+1)}{2}
\end{align}
$$
同理，只要我们能把$n^2,n^3$都写成二项式系数的系数和，前$n+1$项自然数的平方和以及立方和公式就可以得到。
观察发现:
$\forall n \geqslant 0$, $n^2 = 2\cdot \frac{n(n-1)}{2} + n = 2\binom{n}{2} + \binom{n}{1} $
所以$$
\begin{align}
1^2 + 2^2 + 3^2 + \cdots + (n-1)^2 + n^2 &= 0^2 + 1^2 + 2^2 + 3^2 + \cdots + (n-1)^2 + n^2\\
&= (2\binom{0}{2} + \binom{0}{1}) + (2\binom{1}{2} + \binom{1}{1}) + (2\binom{2}{2} + \binom{2}{1}) \\
& + \cdots + (2\binom{n-1}{2} + \binom{n-1}{1}) + (2\binom{n}{2} + \binom{n}{1}) \\
&= 2\sum_{i = 0}^{n}{\binom{i}{2}} + \sum_{i = 0}^{n}{\binom{i}{1}} \\
&= 2\binom{n+1}{3} + \binom{n+1}{2}\\
&= 2\cdot \frac{(n+1)!}{3!\cdot (n-2)!} + \frac{(n+1)!}{2!\cdot (n-1)!}\\
&= 2\cdot \frac{n(n+1)(n-1)}{6} + \frac{n(n+1)}{2}\\
&= \frac{n(n+1)(2n+1)}{6} \qquad\qquad \left(2.5\right)
\end{align}
$$
也可以观察发现：
$
\begin{align}
\forall n \geqslant 0, n^3 &= 6\cdot \frac{n(n-1)(n-2)}{6} + 3n^2 -2n \\
&= 6\binom{n}{3} + 3(2\binom{n}{2} + \binom{n}{1}) -2 \binom{n}{1}\\
&= 6\binom{n}{3} + 6\binom{n}{2} + \binom{n}{1}
\end{align}$
使用同样的方法，
$$
\begin{align}
1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 + n^3 &= 0^3 + 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 + n^3\\
&= 6\binom{n+1}{4} + 6\binom{n+1}{3} + \binom{n+1}{2}\\
&= \frac{n^2(n+1)^2}{4} \qquad\qquad \left(2.6\right)
\end{align}
$$
$\left(2.5\right)$ 和 $\left(2.6\right)$给出了前$n+1$的自然数的平方和和立方和的用$n$表示的公式。我们离目标$\circledast$更进了一步。但是问题来了，如果使用同样的方法去计算$1^4 + 2^4 + 3^4 + \cdots + n^4$, 我们需要把$n^4$写成二项式系数的系数和，比如找到$a,b,c,d \in R, \forall n \in N,$ $$n^4 = a\binom{n}{4} + b\binom{n}{3} +c\binom{n}{2} + d\binom{n}{1}$$
但我们现在甚至不知道是否$a,b,c,d$存在，后续章节会探讨找出这些系数的方法。
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad $ To be continued