先给出组合数（二项式系数）性质

[latex]\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}[/latex]

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

Mathematica也知道此性质：

[MathematicaIn/]FullSimplify[Binomial[n + 1, k] == Binomial[n, k] + Binomial[n, k – 1]][MathematicaOut n=””]True

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

兹证明如下：

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

提示：[latex]\binom{n}{m}=\frac{n!}{m!(n-m)!}[/latex]。

证明：

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

• 当m=0，[latex]\binom{1}{0}=\frac{1!}{1!(1-0)!}=1[/latex]。命题成立。
• 当m=1，[latex]\binom{1}{1}=\frac{1!}{1!(1-1)!}=1[/latex]。命题成立。

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

当n=k+1，[latex]\binom{k+1}{m}=\frac{(k+1)!}{m!(k+1-m)!}[/latex]（公式1）。

• 如果限制[latex]1\leqslant m\leqslant k[/latex]，则公式1可进一步分解。第一行红色部分为限制m的原因。
  [latex]\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*}[/latex]
  根据归纳假设，[latex]\binom{k}{m}[/latex]和[latex]\binom{k}{m-1}[/latex]为整数，所以[latex]\binom{k+1}{m}[/latex]也是整数。
• 另外，当m=0或k+1时，得[latex]\binom{k+1}{m}=1[/latex]，为整数。

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

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

参考资料

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