2014/02/23

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

分野: 整数問題  レベル: 最難関大学

整数論の有名な公式(定理):
連続する $n$ 個の整数の積は $n!$ の倍数である

について素直な証明とエレガントな証明を紹介します。

上記の公式は美しく,この事実を背景とした問題がたまに出題されます。
特に $n=3$ の場合をよく見かける気がします:
「任意の整数 $n$ に対して $n(n-1)(n-2)$ は $6$ の倍数である」

連続する $n$ 個の整数が自然数だとしても一般性を失わないので,以下では上記の公式が自然数の場合に成り立つことを3つの方法で証明します。
1,整数論のルジャンドルの定理を用いる素直な方法
2,二項係数の意味を考えるエレガントな方法
3,二項係数と数学的帰納法を用いる方法

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

証明

連続するn個の数の積:$m(m-1)\cdots(m-n+1)=\dfrac{m!}{(m-n)!}$ が $n!$ で割り切れることは,$\dfrac{m!}{n!(m-n)!}$ が整数であることと同値である。
任意の素数 $p$ に対して,上式の分母と分子がそれぞれ素因数 $p$ を何個持つか数え,分子の方が多く持っていることを示せばよい。
ルジャンドルの定理より,$m!$ が持つ素因数 $p$ の数は,
${\displaystyle\sum_{i=1}^{\infty}\bigl\lfloor \dfrac{m}{p^i} \bigr\rfloor}$ 個。
同様に,$n!(m-n)!$ が持つ素因数 $p$ の数は,
${\displaystyle\sum_{i=1}^{\infty}\left(\bigl\lfloor \dfrac{n}{p^i} \bigr\rfloor+\bigl\lfloor \dfrac{m-n}{p^i} \bigr\rfloor\right)}$ 個。
これと,フロアー関数の性質:$\lfloor x+y \rfloor\geq\lfloor x \rfloor+\lfloor y \rfloor$(和を取って切り捨てるより切り捨ててから和を取ったほうが小さい)より,題意は示された。

2,二項係数の意味を考えたエレガントな方法

証明2

$m$ 個から $n$ 個選ぶ組み合わせの数は${}_m\mathrm{C}_n=\dfrac{m!}{n!(m-n)!}$ 通りであり,これは紛れもない整数なので題意は示された。

コンビネーションの定義式と意味を考えれば上記のように一瞬で導けます。
これも正しい証明にはなっているのですが,狐につままれたような感じがするので,${}_m\mathrm{C}_n$ が整数であることを組み合わせに頼らず帰納法で証明しておきます。

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

証明3

${}_m\mathrm{C}_n$ が整数であることを $m$ に関する帰納法で示す。
$m=1$ のときは自明。また,$n=m$ の場合も自明(${}_m\mathrm{C}_m=1$)である。
$m=k$ のとき${}_k\mathrm{C}_n (n=0, 1, 2,\cdots, k)$ が整数だと仮定すると,二項係数の有名公式より,${}_{k+1}\mathrm{C}_{n}={}_k\mathrm{C}_n+{}_k\mathrm{C}_{n-1}$ も整数。(整数+整数=整数)
よって,$m=k+1$ のときも主張は成立する。


Tag: 数学的帰納法のパターンまとめ

分野: 整数問題  レベル: 最難関大学