連続するｋ個の自然数の積

　　ｎ（ｎ−１）・・・（ｎ−ｋ＋１）

がｋ！で割り切れることは

　　ｎ（ｎ−１）・・・（ｎ−ｋ＋１）／ｋ！

が整数であることがいえればよいのであるが，

　　ｎ（ｎ−１）・・・（ｎ−ｋ＋１）／ｋ！＝nＣk

すなわち，二項係数はその定義から組み合わせの総数＝整数であるから明らかであろう．しかしながら，このことを証明しようとするとかなり厄介である．

　ｎの倍数は連続するｎ個の自然数ごとに１個存在するから，連続するｋ個の自然数ｎ〜ｎ−ｋ＋１までの間に２の倍数は少なくとも［ｋ／２］個，３の倍数は少なくとも［ｋ／３］個，・・・

　しかし，

　　ｎ（ｎ−１）・・・（ｎ−ｋ＋１）

がｋ！で割り切れることは，加法・乗法・除法に関わる定理としてみると決して自明ではない．実際，ガウスやディリクレは純粋に算術的な証明を与えようとして悪戦苦闘したと伝えられている．算術の難しい定理も，組み合わせ論の視点からみれば易しい定理であることはあり得るのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ｑ］ｎ^5−ｎは１０の倍数であることを示せ．

［A］ｎ^5−ｎ＝ｎ（ｎ^4−１）＝ｎ（ｎ^2−１）（ｎ^2＋１）

＝（ｎ−１）ｎ（ｎ＋１）（ｎ^2＋１）

　（ｎ−１）ｎ（ｎ＋１）は３個の連続する整数の積であるから３！＝６で割り切れることはわかるが，（ｎ^2＋１）は

　　２，５，１０，１７，２６，・・・

となって，ｎ^5−ｎが１０の倍数であるかどうかはよくわからない．

　そこで，数学的帰納法を使ってみよう．

Ｐ（１）＝１^5−１＝０・・・１０の倍数である

Ｐ（ｋ）＝ｋ5−ｋが１０の倍数であると仮定する．このとき，

Ｐ（ｋ＋１）＝（ｋ＋１）^5−（ｋ＋１）

＝（ｋ^5−ｋ）＋５ｋ（ｋ＋１）（ｋ^2＋ｋ＋１）

　ｋ（ｋ＋１）は２の倍数であるから，（ｋ^5−ｋ）も５ｋ（ｋ＋１）（ｋ^2＋ｋ＋１）も１０の倍数である．→Ｐ（ｋ＋１）は１０の倍数である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝