证明组合数（二项式系数）是整数
2015年1月24日先给出组合数（二项式系数）性质
[latex]\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}[/latex]
即二项式系数是另两个二项式系数之和。
Mathematica也知道此性质：
[MathematicaIn/]FullSimplify[Binomial[
这样就可以直接用数学归纳法证明。但是不知道上述性质时也可以证明。
兹证明如下：
令[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]为整数。