連続するn個の整数の積と二項係数

整数論の有名な定理

連続する nn 個の整数の積は n!n! の倍数である。

上記の定理について,3通りの証明を紹介します。

連続n整数の積はn!の倍数

大学入試でも,上記の定理に関連した問題がたまに出題されます。

特に n=3n=3 の場合をよく見かける気がします。

任意の整数 nn に対して n(n1)(n2)n(n-1)(n-2)66 の倍数になります。

例えば,5×4×3=605\times 4\times 3=60 は確かに 66 の倍数になっています。

以下では,上記の定理を3つの方法で証明します。

  • 整数論のルジャンドルの定理を用いる素直な方法
  • 二項係数の意味を考える方法
  • 二項係数と数学的帰納法を用いる方法

※ただし,連続する nn 個の整数がすべて自然数の場合のみ証明します。 00 を含む場合は明らかですし,全て負の場合も,全て正の場合から従います。

1.整数論のルジャンドルの定理を用いた素直な方法

証明

連続するn個の数の積: m(m1)(mn+1)=m!(mn)!m(m-1)\cdots(m-n+1)=\dfrac{m!}{(m-n)!}n!n! で割り切れることは,m!n!(mn)!\dfrac{m!}{n!(m-n)!} が整数であることと同値である。

任意の素数 pp に対して,上式の分母と分子がそれぞれ素因数 pp を何個持つか数え,分子の方が多く持っていることを示せばよい。 ルジャンドルの定理より,m!m! が持つ素因数 pp の数は,

i=1mpi{\displaystyle\sum_{i=1}^{\infty}\left\lfloor \dfrac{m}{p^i} \right\rfloor} 個。

同様に,n!(mn)!n!(m-n)! が持つ素因数 pp の数は,

i=1(npi+mnpi){\displaystyle\sum_{i=1}^{\infty}\left(\left\lfloor \dfrac{n}{p^i} \right\rfloor+\left\lfloor \dfrac{m-n}{p^i} \right\rfloor\right)} 個。

これと,フロアー関数の性質: x+yx+y\lfloor x+y \rfloor\geq\lfloor x \rfloor+\lfloor y \rfloor (和を取って切り捨てるよりも,切り捨ててから和を取ったほうが小さい)より,目標の定理が示された。

フロアー関数(ガウス記号)の性質については,ガウス記号の定義と3つの性質で解説しています。

2.二項係数の意味を考えた方法

証明2

mm 個から nn 個選ぶ組み合わせの数は mCn=m!n!(mn)!{}_m\mathrm{C}_n=\dfrac{m!}{n!(m-n)!} 通りであり,これは紛れもない整数なので目標の定理が示された。

コンビネーションの定義式と意味を考えれば,上記のように一瞬で導けます。

これも正しい証明なのですが,狐につままれたような感じがする人もいるでしょう。

3.二項係数と数学的帰納法を用いる方法

証明3

mCn{}_m\mathrm{C}_n が整数であることを mm に関する帰納法で示す。

m=1m=1 のときは自明。

m=km=k のとき kCn(n=0,1,,k){}_k\mathrm{C}_n\:(n=0, 1,\cdots, k) が整数だと仮定すると,二項係数の有名公式より,k+1Cn=kCn+kCn1{}_{k+1}\mathrm{C}_{n}={}_k\mathrm{C}_n+{}_k\mathrm{C}_{n-1} も整数 (n=1,,k)(n=1,\cdots, k) 。また,k+1C0{}_{k+1}\mathrm{C}_{0}k+1Ck+1{}_{k+1}\mathrm{C}_{k+1}11 なので整数。

よって,m=k+1m=k+1 のときも主張は成立する。

証明1は,ルジャンドルの定理という難しい道具を使いますが,非常に美しいです。

Tag:数学的帰納法をわかりやすく【例題3問、応用5パターン】