证明组合数(二项式系数)是整数

先给出组合数(二项式系数)性质

\(\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}\)

即二项式系数是另两个二项式系数之和。

Mathematica也知道此性质:

In[]:=FullSimplify[Binomial[n + 1, k] == Binomial[n, k] + Binomial[n, k – 1]]Out[]:=True

这样就可以直接用数学归纳法证明。但是不知道上述性质时也可以证明。

兹证明如下:

令\(n \geqslant 0\),设命题P(n)为\(\forall m \in \mathbb{N}, m\leqslant n \),\(\binom{n}{m}\)为整数。

提示:\(\binom{n}{m}=\frac{n!}{m!(n-m)!}\)。

证明:

当n=1时,m可取0或1。

  • 当m=0,\(\binom{1}{0}=\frac{1!}{1!(1-0)!}=1\)。命题成立。
  • 当m=1,\(\binom{1}{1}=\frac{1!}{1!(1-1)!}=1\)。命题成立。

假设n=k时,P(k)成立,则\(\binom{k}{0},\binom{k}{1},\cdots, \binom{k}{k}\)均为整数。

当n=k+1,\(\binom{k+1}{m}=\frac{(k+1)!}{m!(k+1-m)!}\)(公式1)。

  • 如果限制\(1\leqslant m\leqslant k\),则公式1可进一步分解。第一行红色部分为限制m的原因。
    \(\begin{align*}
    =&\frac{k!}{(\color{red}{m-1})!(k-m)!}\cdot \frac{k+1}{m\cdot (\color{Red}{k+1-m})} \\
    =&\frac{k!}{(m-1)!(k-m)!}\cdot \frac{k+1-m+m}{m\cdot (k+1-m)} \\
    =&\frac{k!}{(m-1)!(k-m)!}\cdot \left (\frac{1}{m}+\frac{1}{k+1-m} \right ) \\
    =&\frac{k!}{m!(k-m)!}+ \frac{k!}{(m-1)!(k-m+1)!} \\
    =&\binom{k}{m}+\binom{k}{m-1}
    \end{align*}\)
    根据归纳假设,\(\binom{k}{m}\)和\(\binom{k}{m-1}\)为整数,所以\(\binom{k+1}{m}\)也是整数。
  • 另外,当m=0或k+1时,得\(\binom{k+1}{m}=1\),为整数。

所以当n=k+1,P(k+1)成立。

所以,依照数学归纳法,对于所有的n(\(n \leqslant 0\)),命题P(n)成立,\(\forall m \in \mathbb{N} \),\(\binom{n}{m}\)为整数。

参考资料

nelsonywm2000. 怎样证明组合数一定是正整数?. . 2009-10-31 [2015-01-24].

发表评论

电子邮件地址不会被公开。

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)