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