证明任意$n$个连续的正整数的乘积都能被$n!$整除

2020-03-14

Formulation

试证明

$$ \forall{k \geq 0, k \in \mathbb{Z}}, \exists{p \in \mathbb{Z}}, \Pi_{i=1}^{n} (k+i) = p n! $$

恒成立.

Instances

为了理解这个命题所表达的意思,我们不妨分别给$n$取固定的值,看当$n$给定的时候,命题陈述的内容是什么,现当$n=1$,那么就是要证明任意$1$个正整数都能被$1!$(1的阶乘)整除,这是显然的.

当$n=2$,等于要证明:任意两个整数$k,k+1,k \geq 1$的乘积$k(k+1)$都能被$2!$,$2$的阶乘,也就是2,整除,这同样也是显然的,因为$k,k+1$如果其中一个是奇数,那么另外一个必然是偶数,而偶数,按照定义,是能被$2$整除的.

当$n=3$及$n \geq 3$时,原命题就变得不那么显然了,诚然我们知道

$$ 1 \times 2 \times 3 = 3! $$

以及

$$ 2 \times 3 \times 4 = 3! \times 4 $$

以及

$$ 3 \times 4 \times 5 = 3! \times 10 $$

但是对于任意的$k \in \mathbb{N}^{\star}$,判断是否有整数$q \in \mathbb{Z}$,使得

$$ (k+1)(k+2)(k+3) = 3! \times q $$

成立,并不显然(如果不亲自去算一遍的话.同样的,给定$n=4$,对任意$k \in \mathbb{N}^{\star}$,判断是否有整数$q \in \mathbb{Z}$使得

$$ (k+1)(k+2)(k+3)(k+4) = 4! \times q $$

成立,也不是显然.但是到现在,我们至少明白了原命题

$$ \forall{k \geq 0, k \in \mathbb{Z}}, \exists{p \in \mathbb{Z}}, \Pi_{i=1}^{n} (k+i) = p n! $$

的基本含义,即它想让我们证明的是什么,从直观意义上.

证法之一:利用二项式系数的表达式

我们记得二项式系数$\binom{n}{k}$的定义是$n$个元素的集合的互不相同的含有$k$个元素的非空子集的个数,举例来说,$\binom{5}{3}$可以设想为从编号为$1,2,3,4,5$的五个小球中挑取$3$个球,得到的所有不同编号组成的个数,更加具体一点,从$1,2,3,4,5$中,要挑取$3$个数字,我们可以挑取下列组合$ (1,2,3), (1,2,4), (1,2,5),(1,3,4), (1,3,5),$$(1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5) $

即从$1,2,3,4,5$这$5$个数字中总共能挑选出$10$个互不相同的组合,所以$\binom{5}{3}=10$,这里我们所说两个组合「互不相同」实际上是指着两个组合中的元素不是完全相同的,正如您可以简单地验证上列$10$个组合中没有两个组合有完全相同的数字.

然而,为了证明

$$ \forall{k \geq 0, k \in \mathbb{Z}}, \exists{p \in \mathbb{Z}}, \Pi_{i=1}^{n} (k+i) = p n! $$

我们为什么还要提到组合数$\binom{n}{k}$呢?数学家们经过思考、猜想和证明得到了$\binom{n}{k}$的一般公式,即,根据这个公式,我们能够解决这样的一般性的问题:给定正整数$n$,给定非负整数$k \leq n$,从$n$个元素中总共能选取出多少种含有$k$个元素的不完全相同的组合?答案是

$$ \binom{n}{k} = \frac{n!}{m!(n-m)!} $$

这么多个.正如我们可以带进去算,令$n=5,k=3$,我们得到

$$ \binom{5}{3} = \frac{5!}{3! \times 2!} = \frac{2 \times 3 \times 4 \times 5}{2 \times 3 \times 2} = 10 $$

这就验证了上面列出的$\binom{n}{k}$的一般公式在$n=5,k=3$的情形是正确的.我们暂且不去怀疑上面列出的$\binom{n}{k}$的一般公式是否是正确的,我们首先应当注意的是,对原命题,如果成立的话,那么就有

$$ \frac{(k+1)\times \cdots \times (k+n)}{n!} = q $$

右边的$q$是个整数,因为左边分子是整除分母的,怎么证明这一点呢?我们注意到

$$ k! (k+1) \times \cdots \times (k+n) = (k+n)! $$

于是就有

$$ \frac{(k+n)!}{k! \times n!} = q $$

其中等式的左端刚好就是

$$ \binom{n+k}{n} = \frac{(k+n)!}{k! \times n!} $$

或者,还等价的是

$$ \binom{n+k}{k} = \frac{(k+n)!}{k! \times n!} $$

即,我们得到

$$ \binom{n+k}{n} = \binom{n+k}{k} = q = \frac{(k+1) \times \cdots \times (k+n)}{n!} $$

这告诉我们$n$个连续的正整数的乘积除以$n$的阶乘刚好等于组合数$\binom{n+k}{n}$和组合数$\binom{n+k}{k}$! 而组合数肯定是整数,因此原命题

$$ \forall{k \geq 0, k \in \mathbb{Z}}, \exists{p \in \mathbb{Z}}, \Pi_{i=1}^{n} (k+i) = p n! $$

是成立的!

回顾与补充

在前面一节中,我们通过将$n$个连续的正整数的乘积和$n!$的分式

$$ \frac{(k+1) \times \cdots \times (k+n)}{n!} $$

做等价变换得到

$$ \frac{(k+1) \times \cdots \times (k+n)}{n!} = \frac{(k+n)!}{k! \times n!} $$

然后又由组合数公式

$$ \binom{k+n}{n} = \binom{k+k}{k} = \frac{(k+n)!}{k! \times n!} $$

得到

$$ \frac{(k+1) \times \cdots \times (k+n)}{n!} = \binom{k+n}{n} = \binom{k+k}{k} $$

最后由组合数是整数这一「显然」的性质得出了

$$ \frac{(k+1) \times \cdots \times (k+n)}{n!} $$

也是整数的这一推论,从而最后证明$(k+1) \times \cdots \times (k+n)$是整除$n!$的,从而证明了原命题.

但现在这里有几个问题:

  1. 凭什么说$\binom{n+k}{n} = \binom{n+k}{k}$?
  2. 凭什么说,对一般的$n,k \geq 0, n, k \in \mathbb{Z}$会有$\binom{n+k}{n} = \binom{n+k}{k} = \frac{(n+k)!}{n! \times k!}$成立?

对第一个问题,我们要解释$\forall{k,n \geq 0, k, n \in \mathbb{Z}}, \binom{n+k}{n} = \binom{n+k}{k}$成立,由于$\binom{n+k}{n}$代表的是从$n+k$个(互不相同的)数字里面取出$n$个互不相同的数字的互不完全相同的组合的个数,$\binom{n+k}{n}$代表的是从$n+k$个(互不相同的)数字里面取出$k$个互不相同的数字的互不完全相同的组合的个数,所以我们要解释为什么从$n+k$个元素里面取$n$个元素得到的组合的个数和从$n+k$个元素里面取$k$个元素得到的组合的个数是一样的.

意识到这样一个事实之后,就会立刻觉得上述关系是显然的:设想我们是这么计算$\binom{n+k}{n}$的,我们一次从$n+k$个元素中取$n$个元素,每一次都取不同的组合,每取一次就更新一次统计结果,给计数器$s(n+k,n)$加$1$,然而注意到这样一个容易被忽视的事实,当我们确定了$n+k$个元素中的$n$个元素,是不是也就同样确定看剩下的$k$个元素呢?这是肯定的!因为当我们从$n+k$个元素中取走了$n$个之后,就只剩下$k$个元素了,所以相当于,通过从$n+k$个元素中确定一个$n$个元素的组合,我们同时还确定了$n+k$个元素中的一个$k$个元素的组合,因此计数器$s(n+k,k)$也要加$1$,这样,待我们遍历完了所有$n+k$个元素中$n$个元素的组合,我们也遍历完了$n+k$个元素中$k$个元素的组合,这毫无疑问,因为每一个$n$个元素的组合在$n+k$个元素中比如唯一对应着剩下的$k$个元素的组合,而反过来,不难理解,也是同样的道理.

所以,到最后,计数器$s(n+k,n)$必然会等于计数器$s(n+k,k)$,简单来说就是因为在$n+k$个元素中,每得到一个$n$个元素的组合,也相当于得到了一个$k$个元素的组合,而反过来也是一样的,所以最终$\binom{n+k}{n}=\binom{n+k}{k}$.

这就完成了对第一个问题的解释.

要解释第二点,需要我们证明,在一般情况下:

$$ \forall{n,k \geq 0, n,k \in \mathbb{Z}}, \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

成.该怎么证呢?首先,作为一个引理,我们引入「排列数」(Arrangements)的概念,什么叫做排列数呢?就是$n$个元素中,共有多少个$k$个不同元素的排列?再具体一个,一个$k$元排列其实就是$k$个元素在空间上的一种放置方式,两个排列相同,当且仅当这两个排列包含的元素且每个元素对应的位置还相同,还是不好理解?我举个例子$(1,2,3)$是一个排列,而$(1,3,2)$虽然也包含了相同的元素但是位置不一样,在第二个排列中,数字$3$是处在排列的第二个位置,数字$2$是处在排列的第$3$个位置,而这在第一个排列中是刚好相反的,所以说它们是两个排列.

先设想一个特殊情况,我们要从$5$个元素中找出所有$3$个元素的排列,有多少个这样的排列呢?我们把这些排列的个数记做$\mathsf{A}(5,3)$,其中的$\mathsf{A}$即排列数(Arrangements)的意思.

这回,我们可不会像求组合数那样,一个一个地去数了.

反正,每一次,我们都要从$5$个元素组成的集合中取出$3$个不同的元素,那么在每一次,我们先从$5$个元素中取这$3$个元素的第一个,很显然,有$5$中取法,即$5$中选择,然后,我们取第二个元素,由于我们刚才已经取了一个,$5$个元素中还剩下$4$个,所以,这一次我们有$4$中选择,那么当我们要取第$3$个元素的时候,$5$个元素中也只剩下$3$个了,所以第三次我们有$3$中选择,并且,注意到,第一次不关我们选$5$个元素中的哪一个,第二次选的时候都是只剩下$4$个供我们选,而第二次不管我们选$4$个元素中的哪一个,第三次都只剩下$3$个元素供我们选,因为每一次做出选择不可用不选,必须要选一个,这样选三次,每次选一个,我们就能得到一个$3$个元素的排列,并且我们知道,这样的决策空间必定和所有的排列组成的空间是等价的,这是因为,对任何一个这样的$3$元排列,它的第一个元素必然是从$5$个元素当中选出,而第二个元素必然是从$4$个元素当中选出,而第$3$个元素必然是从剩下的$3$个元素中选出,现在来计算这个决策空间所包含的决策的数量的个数(其实也正是排列的个数):

$$ \mathsf{A}(5, 3) = r_1 \times r_2 \times r_3 = 5 \times 4 \times 3 $$

其中$r_i, i=1,2,3$表示做出第$i$次决定之前所面临的选项的个数,显然$r_i$在这里等于$r_i = 5 - i + 1$.

那么更一般地,我们就知道了,从$n$个元素中找出一个$k$个元素的排列等于说是做一个决策,所有可能的决策的个数正是$n$个元素中$k$个元素的排列的个数,那么就有$\mathsf{A}(n,k)$个可能的决策,由于在第$i$次做决策的时候我们有$r_i = n - i + 1$个选项,所以

$$ \mathsf{A}(n, k) = \Pi_{i=1}^{k} r_i = n \times (n-1) \times \cdots \times (n - k + 1) $$

特殊的,当$k=n$的时候,我们把得到的每一个排列称为「全排列」,因为$n$元集中的所有元素全部都拿来排列了,所以顾名思义,叫做全排列.并且

$$ \mathsf{A}(n, n) = n \times \cdots \times 1 = n! $$

接下来为了证明组合数的一般公式

$$ \forall{n,k \geq 0, n,k \in \mathbb{Z}}, \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

我们试着从这样一个另外的角度求出排列数:为了从$n$元集中得到所有的$k$元排列,我们先求出$n$元集的所有$k$元组合,于是我们首先得到$\binom{n}{k}$个这样的$k$元组合,而再由每一个这样的$k$元组合做全排列,就正好得到了所有$n$元集的$k$元排列!并且由于$k$个元素的全排列个数是$\mathsf{A}(k,k)=k!$,所以我们事实上得到了

$$ \binom{n}{k} \times (k!) = A(n, k) = n \times (n-1) \times \cdots \times (n-k+1) $$

于是

$$ \binom{n}{k} = \frac{n \times (n-1) \times \cdots \times (n-k+1)}{k!} = \frac{n!}{k!(n-k)!} $$

这就完成了对组合数一般公式的证明.

给我们的启示

这样的一次证明,给我们揭示了排列和组合的内在联系,同时还让我们得以有机会利用计数原理这个领域的知识和武器来解决数论领域的问题,可见计数原理的应用是非常广泛的,简单的道理,却蕴含着奇妙的联系,数学的世界真精彩!

证法二:利用「鸽笼原理」

待续

参考文献

[1] Divisibility of Product of Consecutive Integers - ProofWiki

[2] Pigeonhole principle - Wikipedia

数学讨论mathematicspermutations

使用Hugo Shortcode和svg标签构建自定义图形!

RFC 7234:阅读与思考