連続するn個の整数

テーマ:
ああああああああぁぁぁ、更新忘れてたァァァ。


ということで、お久しぶりです。笑



もっと更新します。頑張ります。はい。


というわけで、今回は連続するn個の整数についてです。

今回取り扱いたいものは、

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

です。

k,k+1,…,k+n-1のn個の整数の積をf(n,k)としましょう。


k,k+1,…,k+n-1に0が含まれる場合、つまり、k≦0≦k+n-1、つまりは、1-n≦k≦0のとき。
これらの積は0ですので、f(n,k)=0より、f(n,k)は確かにn!の倍数です。

次に、k,k+1,…,k+n-1が全て負の数、つまり、k+n-1≦-1、つまりは、k≦-nのとき。
先の数列を逆さまに並べ替えて-1をそれぞれ掛けた数列1-n-k,2-n-k,…,-1-k,-kは全て正の数で連続するn個の整数です。これらの積は、f(n,1-n-k)と表せますから、f(n,k)=(-1)^n×f(n,1-n-k)となります。従って、全て正の数で連続するn個の整数の積がn!の倍数であることが分かれば、全て負の数で連続するn個の整数の積もn!の倍数と分かります。


従って、以下では、全て正の数で連続するn個の整数の積がn!の倍数であることを示しましょう。

1)二項係数

これが、1番簡単です。全て正の数より、k≧1ですから、k+n-1≧nですので、二項係数つまりコンビネーションを考えましょう。




上の式より、最左辺がk+n-1人からn人選ぶ組み合わせの場合の数ですから、中辺より、k,k+1,…,k+n-1の積(連続するn個の自然数の積)はn!の倍数と分かります。


2)ルジャンドルの公式

なんか、1)の証明て、簡単なんですけど、ん…?って言う感が凄いんですよね。(組み合わせの数が中辺で表されるのを説明しなくていいのか…?っていう懸念がある。つまりは組み合わせの定義と式にした定義が同値であるのか…?っていう懸念。(これも近いうちに記事に起こしますかね…。))

そこで、中辺と最右辺を使いましょう。




つまり、最右辺が整数になることを示します。
任意の素数pについて、ord_p(分子)≧ord_p(分母)であることを言えれば、分子も分母も自然数ですので、分子は分母の倍数つまり、最右辺は整数と言えます。(ord_p(x)で整数pで割れる回数→ordの記事)

まず、階乗のオーダーはルジャンドルの公式を使えば調べられます。



ここで、[x+y]≧[x]+[y](xの小数部分+yの少数部分は0以上2未満ですが、これが、1以上のとき、x+yの整数部分=xの整数部分+yの整数部分+1で、1未満のとき、x+yの整数部分=xの整数部分+yの整数部分より示されます。)なので、各項は上の方が下より大きい(あるいは等しい)ことになります。ここで無限級数の形になってますが、iが十分に大きいと項は全てゼロになりますので、上下ともに収束するので、和をとっても上の方が下より大きい(あるいは等しい)ことが分かります。よって、ord_p(分子)≧ord_p(分母)より、最右辺は整数ですから、中辺より、連続するn個の自然数の積はn!の倍数と分かりました。

3)二重数学的帰納法

f(n,k)=k×(k+1)×…×(k+n-2)×(k+n-1)
=k×(k+1)×…×(k+n-2)×(k-1)+k×(k+1)×…×(k+n-2)×n
=f(n,k-1)+nf(n-1,k)
(これは、二項係数の漸化式を表しています。)

n≧2かつk≧2のとき、f(n,k-1)とf(n-1,k)で成り立つならば、f(n,k)でも成り立ちます。(なぜなら左の項=n!の倍数、右の項=n×(n-1)!の倍数=n!の倍数より、f(n,k)もn!の倍数)が成り立ちます。

ここで、f(1,k)=kより、1!の倍数、f(n,1)=n!よりn!の倍数です。よって、f(1,k)とf(n,1)で成り立ちますので、kとnを二重に動かすことで数学的帰納法より、f(n,k)はn!の倍数と分かります。
(たとえば、k=i以下でf(n,k)が全て命題をみたし、k=i+1では、n=j以下でf(n,k)が全て命題をみたすと仮定すると、まず、nの帰納法より、k=i+1で成立するので続いてkの帰納法より任意のk,nで成立すると分かる。)






どうでしたか??
個人的には二重帰納法のやり方が好きです。
ただ、無難にやるならルジャンドルの公式あたりが良いのではないでしょうか…。





↓twitterやってます!