数学II / 式と証明

二項係数が n+1 で割り切れること

最難関編二項係数整数性

問題

$n$ を自然数とする。

(1) 等式 $_{2 n} C_{n} -_{2 n} C_{n + 1} = \frac{_{2 n} C _{n}}{n + 1}$ が成り立つことを示せ。

(2) $_{2 n} C_{n}$ は $n + 1$ の倍数であることを示せ。

ヒントを見る

割り切れることを素因数で調べようとすると沼にはまる。商そのものが「整数であることが明らかな量(二項係数の組合せ)」で書けてしまえば終わり — 隣どうしの二項係数の比を階乗で計算してみると。

解答・解説

方針

「割り切れる」を直接示す代わりに、商 $\frac{_{2 n} C _{n}}{n + 1}$ が2つの二項係数の差に等しいことを示す。二項係数は整数、整数の差は整数 — それだけで割り切れることが出る。比 $\frac{_{2 n} C _{n + 1}}{_{2 n} C _{n}}$ を階乗で計算するのが早い。

解答

⓪ 発想 — どう考え始めるか。 「 $n + 1$ で割り切れる」を素因数分解で示すのは難しい。発想を裏返す。商 $\frac{_{2 n} C _{n}}{n + 1}$ が、整数であることが見えている量 — 二項係数の差 — に一致することを示せばよい。

整数の差は整数だから、それで割り切れることが確定する。鍵は、隣どうしの二項係数の比を階乗表示で出すことだ。

重要整数性の証明の定石: その数を「個数を数えている量(二項係数)たちの和・差」で表す

① 比を計算する((1)の証明)。 階乗表示で

$\frac{_{2 n} C _{n + 1}}{_{2 n} C _{n}} = \frac{\frac{( 2 n )!}{( n + 1 )! ( n - 1 )!}}{\frac{( 2 n )!}{n ! n !}} = \frac{n ! n !}{( n + 1 )! ( n - 1 )!} = \frac{n}{n + 1}$

よって $_{2 n} C_{n + 1} = \frac{n}{n + 1}_{2 n} C_{n}$ であり、

$_{2 n} C_{n} -_{2 n} C_{n + 1} =_{2 n} C_{n} (1 - \frac{n}{n + 1}) = \frac{_{2 n} C _{n}}{n + 1}$

② 整数性((2)の証明)。 左辺 $_{2 n} C_{n} -_{2 n} C_{n + 1}$ は二項係数(整数)の差だから整数。よって右辺 $\frac{_{2 n} C _{n}}{n + 1}$ も整数であり、 $_{2 n} C_{n}$ は $n + 1$ の倍数である。

③ 確かめ。 $n = 3$ : $_{6} C_{3} = 20$ 、 $_{6} C_{4} = 15$ 、差は $5 = \frac{20}{4}$ ✓ たしかに $20$ は $4$ の倍数。

まとめ: 「整数であること」は、その数を数え上げの量の組合せで書くのがいちばん強い証明になる。この商 $\frac{_{2 n} C _{n}}{n + 1}$ はカタラン数と呼ばれる有名な数( $1, 2, 5, 14, 42, \dots$ )で、本問の差の表示がその整数性のいちばん短い証明だ。

発展 — 一歩先へ。 カタラン数は「正しい括弧の並べ方」「対角線を越えない最短経路」など、驚くほど多くのものを数えている(本サイトの場合の数の実戦編に、反射原理による勘定がある)。1つの数に代数(本問)と数え上げの2つの顔があるのは、良い数の証だ。

答

(1) 階乗表示の比較で証明 (2) (1)の左辺が整数だから $\frac{_{2 n} C _{n}}{n + 1}$ も整数

別解

互いに素を経由する(得意な人向け)。 差の表示の代わりに、もう1つの階乗の恒等式から攻める道もある。

$_{2 n + 1} C_{n} = \frac{( 2 n + 1 )!}{n ! ( n + 1 )!} = \frac{2 n + 1}{n + 1}_{2 n} C_{n}$

分母を払うと

$(n + 1)_{2 n + 1} C_{n} = (2 n + 1)_{2 n} C_{n}$

左辺は $n + 1$ の倍数。だから右辺 $(2 n + 1)_{2 n} C_{n}$ も $n + 1$ の倍数だ。ここで $n + 1$ と $2 n + 1$ の最大公約数を互除法で調べると

$g cd (n + 1, 2 n + 1) = g cd (n + 1, 2 n + 1 - 2 (n + 1)) = g cd (n + 1, - 1) = 1$

互いに素。よって $n + 1$ は $_{2 n} C_{n}$ の側を割り切るしかない。

「積が割り切れて、片方の因子と互いに素なら、もう片方を割り切る」— 整数論の基本原理を二項係数に適用した形だ。差の表示(本解)が数え上げ寄りの証明なら、こちらは整数論寄りの証明である。

ポイント

比 $\frac{_{2 n} C _{n + 1}}{_{2 n} C _{n}} = \frac{n}{n + 1}$ (階乗表示)。
差 = $\frac{_{2 n} C _{n}}{n + 1}$ で、左辺は整数。
よって $_{2 n} C_{n}$ は $n + 1$ の倍数。

よくある間違い

比の計算で $(n + 1)!$ と $n!$ 、 $(n - 1)!$ と $n!$ の消し合いを混乱する。分子分母を階乗のまま並べてから約分する。
「二項係数の差は整数、だから商も整数」という論理の核を書き落とす。等式だけでは証明にならない。
$n = 1, 2, 3$ の検算( $\frac{2}{2} = 1, \frac{6}{3} = 2, \frac{20}{4} = 5$ )を省く。カタラン数の並びが見えると安心して進める。