已知 $m、n$ 是任意非负整数．求证：$\dfrac{(2m)!(2n)!}{m!n!(m+n)!}$ 是整数（规定 $0!=1$）．（英国）
【难度】
【出处】
1972年第14届IMO试题
【标注】
【答案】
略
【解析】
证法一
设 $f(m,n)=\dfrac{(2m)!(2n)!}{m!n!(m+n)!}$．
若 $n=0$，则 $f(m,0)=C_{2m}^m$ 对所有非负整数 $m$ 是一整数，又易证 $f(m,n+1)=4f(m,n)-f(m+1,n)$ ①
设对一切非负整数 $m,f(m,n)$ 为整数，则由 ① 式知 $f(m,n+1)$ 是整数，因此，对一切非负整数 $m,n,f(m,n)$ 是整数．
证法二
我们证明分母 $D=m!n!(m+n)!$ 整除它的分子 $N=(2m)!(2n)!$．
设素数 $p$ 能整除 $D$ 的最高次幂为 $p^a$，$p$ 能整除 $N$ 的最高次幂为 $p^b$，则
$\begin{aligned}
a&=\sum_{i=1}^{\infty}\left[\dfrac{m}{p^i}\right]+\sum_{i=1}^{\infty}\left[\dfrac{m}{p^i}\right]+\sum_{i=1}^{\infty}\left[\dfrac{m+n}{p^i}\right]\\
&=\sum_{i=1}^{\infty}\left(\left[\dfrac{m}{p^i}\right]+\left[\dfrac{n}{p^i}\right]+\left[\dfrac{m+n}{p^i}\right]\right)\\
b&=\sum_{i=1}^{\infty}\left[\dfrac{2m}{p^i}\right]+\sum_{i=1}^{\infty}\left[\dfrac{2n}{p^i}\right]
\\
&=\sum_{i=1}^{\infty}\left(\left[\dfrac{2m}{p^i}\right]+\left[\dfrac{2n}{p^i}\right]\right)
\end{aligned}$
先证明一个结论：设 $r,s$ 是非负实数，则 $[r]+[s]+[r+s]\leqslant [2r]+[2s]$．
由于当 $l$ 是整数时，$[l+x]=l+[x]$，所以不妨设 $0\leqslant r< 1,0\leqslant s<1$，于是 $[r]=[s]=0$．
当 $r+s<1$ 时，$[r]+[s]+[r+s]=0\leqslant [2r]+[2s]$；
当 $1\leqslant r+s<2$ 时，则 $r,s$ 中必有一个 $\geqslant\dfrac{1}{2}$，从而 $[2r]+[2s]\geqslant 1$，也有 $[r]+[s]+[r+s]=1\leqslant [2r]+[2s]$．
由上面结论知 $\left[\dfrac{m}{p^i}\right]+\left[\dfrac{n}{p^i}\right]+\left[\dfrac{m+n}{p^i}\right]\leqslant \left[\dfrac{2m}{p^i}\right]+\left[\dfrac{2n}{p^i}\right]$，从而 $a\leqslant b$．
所以，对每一个素数 $p$，都有 $a\leqslant b$，故 $D$ 整除 $N$，从而命题得证．
设 $f(m,n)=\dfrac{(2m)!(2n)!}{m!n!(m+n)!}$．
若 $n=0$，则 $f(m,0)=C_{2m}^m$ 对所有非负整数 $m$ 是一整数，又易证 $f(m,n+1)=4f(m,n)-f(m+1,n)$ ①
设对一切非负整数 $m,f(m,n)$ 为整数，则由 ① 式知 $f(m,n+1)$ 是整数，因此，对一切非负整数 $m,n,f(m,n)$ 是整数．
证法二
我们证明分母 $D=m!n!(m+n)!$ 整除它的分子 $N=(2m)!(2n)!$．
设素数 $p$ 能整除 $D$ 的最高次幂为 $p^a$，$p$ 能整除 $N$ 的最高次幂为 $p^b$，则
$\begin{aligned}
a&=\sum_{i=1}^{\infty}\left[\dfrac{m}{p^i}\right]+\sum_{i=1}^{\infty}\left[\dfrac{m}{p^i}\right]+\sum_{i=1}^{\infty}\left[\dfrac{m+n}{p^i}\right]\\
&=\sum_{i=1}^{\infty}\left(\left[\dfrac{m}{p^i}\right]+\left[\dfrac{n}{p^i}\right]+\left[\dfrac{m+n}{p^i}\right]\right)\\
b&=\sum_{i=1}^{\infty}\left[\dfrac{2m}{p^i}\right]+\sum_{i=1}^{\infty}\left[\dfrac{2n}{p^i}\right]
\\
&=\sum_{i=1}^{\infty}\left(\left[\dfrac{2m}{p^i}\right]+\left[\dfrac{2n}{p^i}\right]\right)
\end{aligned}$
先证明一个结论：设 $r,s$ 是非负实数，则 $[r]+[s]+[r+s]\leqslant [2r]+[2s]$．
由于当 $l$ 是整数时，$[l+x]=l+[x]$，所以不妨设 $0\leqslant r< 1,0\leqslant s<1$，于是 $[r]=[s]=0$．
当 $r+s<1$ 时，$[r]+[s]+[r+s]=0\leqslant [2r]+[2s]$；
当 $1\leqslant r+s<2$ 时，则 $r,s$ 中必有一个 $\geqslant\dfrac{1}{2}$，从而 $[2r]+[2s]\geqslant 1$，也有 $[r]+[s]+[r+s]=1\leqslant [2r]+[2s]$．
由上面结论知 $\left[\dfrac{m}{p^i}\right]+\left[\dfrac{n}{p^i}\right]+\left[\dfrac{m+n}{p^i}\right]\leqslant \left[\dfrac{2m}{p^i}\right]+\left[\dfrac{2n}{p^i}\right]$，从而 $a\leqslant b$．
所以，对每一个素数 $p$，都有 $a\leqslant b$，故 $D$ 整除 $N$，从而命题得证．
答案
解析
备注
