(m+n-1)!がm!n!で割り切れることの証明（2021年奈良県立医科大学後期第3問）

解答例

 

（１）

$(m+n,n)=d_1$、$(m,n)=d_2$ と置く。

 

このとき、整数$k_1$、$l_1$を用いて $m+n=k_1{d}_1$、$n=l_1{d}_1$ と書けて、$$m=(k_1-l_1)d_1,n=l_1{d}_1$$と表せる。これより$d_1$は正整数$m$と$n$の公約数であるから、$$d_1\leqq (m,n)=d_2\cdots \mathrm{①}$$を得る。

 

また、整数$k_2$、$l_2$を用いて $m=k_2{d}_2$、$n=l_2{d}_2$ と書けて、$$m+n=(k_2+l_2)d_2,n=l_2{d}_2$$と表せる。これより$d_2$は正整数 $m+n$ と$n$の公約数であるから、$$d_2\leqq (m+n,n)=d_1\cdots \mathrm{②}$$を得る。

 

以上、$\mathrm{①}$と$\mathrm{②}$より $d_1\leqq d_2$ かつ $d_2\leqq d_1$ となるから、$d_1=d_2$ である。よって示された。

□

 

（２）

$$\begin{array}{rl}{}_{m+n}{\mathrm{C}}_n& ={\displaystyle \frac{(m+n)!}{m!n!}}\\ & ={\displaystyle \frac{m+n}{n}}\cdot {\displaystyle \frac{(m+n-1)!}{m!(n-1)!}}\\ & ={\displaystyle \frac{m+n}{n}}\cdot {}_{m+n-1}{\mathrm{C}}_{n-1}\end{array}$$より、$$n\cdot {}_{m+n}{\mathrm{C}}_n=(m+n)\cdot {}_{m+n-1}{\mathrm{C}}_{m-1}$$を得る。ここで（１）より $(m+n,n)=(m,n)$ が成り立つから、${}_{m+n}{\mathrm{C}}_n$ が $m+n$ の倍数であることが従う。

よって ${\displaystyle \frac{{}_{m+n}{\mathrm{C}}_n}{m+n}}$、つまり ${\displaystyle \frac{(m+n-1)!}{m!n!}}$ は整数であるから、$(m+n-1)!$ は $m!n!$ によって割り切れることが示された。

□