◆京都府 大空風成 さんからの解答。
|
||||||||||||
nC0+nC1+nC2+・・・
+nCn=2n この左辺のnCrを、r を3で割ったときの余りで分類して、 rが3で割り切れる数の項の和 (nC0+nC3+nC6+・・・)、 rが3で割ると1余る数の項の和 (nC1+nC4+nC7+・・・)、 rが3で割ると2余る数の項の和 (nC2+nC5+nC8+・・・)に分ける。 このうち2つが等しく、残りの1つが他の2つより1大きいか、または1小さくなる。・・・(A) このことを示せば、rが3で割り切れる数の項の和が、 2nを3で割った数にとても近い数であることがわかる。 rが3で割り切れる数の項の和を nC3k、 rが3で割ると1余る数の項の和を nC3k+1、 rが3で割ると2余る数の項の和を nC3k+2 と表して、 (A)のことを数学帰納法によって示す。 n=2のとき、 2C3k=2C0=1、 2C3k+1=2C1=2、 2C3k+2=2C2=1、 よって、(A)が成り立つ。 n=m-1のとき、(A)が成り立つとすると、 m-1C3k、m-1C3k+1、m- 1C3k+2のうち、 2つが等しく、残りの1つが他の2つより1大きいか、または1小さくなる。・・・(B) n=mのとき、nCr=n-1Cr-1+n-1Cr を利用する。 mC3k=(m-1C3k-1+m-1C3k)= m-1C3k-1+m-1C3k=m-1C3k+2+ m-1C3k mC3k+1=(m-1C3k+m-1C3k+1) =m-1C3k+m-1C3k+1 mC3k+2=(m-1C3k+1+m- 1C3k+2)=m-1C3k+1+m-1C3k+2
だから、(B)より、m-1C3kが他より1大きい(または1小さい)場合は、 |
||||||||||||
|
||||||||||||
この式の左辺の3つの項のうち、1つが1大きい、または1小さいので、 nC3k+ nC3k+1+nC3k+2- 1=2n-1、 または、nC3k+ nC3k+1+ nC3k+2+1=2n+1 の両辺が3で割り切れる。 |
||||||||||||
|
||||||||||||
|
||||||||||||
|
||||||||||||
|
||||||||||||
以上より、 |
||||||||||||
|
||||||||||||
|
||||||||||||
|
||||||||||||
|
||||||||||||
|
◆愛知県 Y.M.Ojisan さんからの解答。
【証明】
2項係数を計算するパスカルの三角形を周長3のパスカルの葉巻に巻き上げれば一目瞭然です。
周期2で偏差010と110が繰り返します。
【PS】
パスカルの葉巻はここだけの造語です。
◆出題者のコメント。
パスカルの葉巻、というのは面白い解き方ですね。
先の問題のつづき、のような物を考えてみました。
面白く思えてもらえると光栄です。
【追加問題】
n が3 以上の場合、次を証明してください。
k=5の倍数 | nCk は、 |
2n 5 | - fn よりは大きく、 | 2n 5 | + fn よりは小さい。 |
但し、fn は、フィボナッチ数列の n項目の事で、項は、
f0=0, f1=1, f2=1, f3=2, f4=3, f5=5, ... という数え方だとします。
例えば、n=5 の場合、
5C0 + 5C5 = 2 は、
32/5 - f5 = 1.4 よりは、大きくなっています。
【余談】
学生時代に、こういう物の一般項を出そうとしたのですが、
k=7の倍数 | nCk より先は、簡単には書けそうにないと、諦めてしまっています。 |
それにしても、フィボナッチ数列は、どこにでも出て来るんだなぁと、ちょっと不思議です。
◆京都府 大空風成 さんからの解答。
|
|||||||||||||||||||||
nC0+nC1+nC2+・・・
+nCn=2n この左辺のnCrを、r を5で割ったときの余りで分類して、 rが5で割り切れる数の項の和 (nC0+nC5+nC10+・・・)、 rが5で割ると1余る数の項の和 (nC1+nC6+nC11+・・・)、 rが5で割ると2余る数の項の和 (nC2+nC7+nC12+・・・)、 rが5で割ると3余る数の項の和 (nC3+nC8+nC13+・・・)、 rが5で割ると4余る数の項の和 (nC4+nC9+nC14+・・・)に分ける。 これら5つの和の数の中には、2つずつ等しい数があるから、3種類の数、小、中、大となり、 中の数をanとすると、5つの和は、 an-fn、an、an+fn-1、an、 an-fn または、 an+fn、an、an-fn-1、 an、an+fn の順(先頭がどの数で始まるかは問わない)に並んでいる。・・・(C) このことを示せば、この5つの和の数は、 どれも an-fn以上 an+fn以下の数であることがわかる。 rが5で割り切れる数の項の和を nC5k、 rが5で割ると1余る数の項の和を nC5k+1、 rが5で割ると2余る数の項の和を nC5k+2、 rが5で割ると3余る数の項の和を nC5k+3、 rが5で割ると4余る数の項の和を nC5k+4、と表して、 (C)のことを数学帰納法によって示す。 n=4のとき、 4C5k=4C0=1=4-3=4-f4 4C5k+1=4C1=4 4C5k+2=4C2=6=4+2=4+f3 4C5k+3=4C3=4 4C5k+4=4C4=1=4-3=4-f4 よって、5つの和は、4-f4、4、4+f3、4、4-f4の順に並んでいるので、 (C)の前者と一致して、(C)が成り立つ。 n=m-1のとき、(C)が成り立つとすると、 m-1C5k、m-1C5k+1、m- 1C5k+2、m-1C5k+3、m-1C5k+4は、 どれかが先頭になり、この順で、 am-1-fm-1、am-1、am-1+fm-2、am- 1、am-1-fm-1・・・(D) または、 am-1+fm-1、am-1、am-1-fm-2、 am-1、am-1+fm-1・・・(E) の順に並んでいる。 n=mのとき、nCr=n-1Cr-1+n-1Cr を利用する。 mC5k=(m-1C5k-1+m-1C5k)= m-1C5k-1+m-1C5k=m-1C5k+4+ m-1C5k mC5k+1=(m-1C5k+m-1C5k+1) =m-1C5k+m-1C5k+1 mC5k+2=(m-1C5k+1+m- 1C5k+2)=m-1C5k+1+m-1C5k+2 mC5k+3=(m-1C5k+2+m- 1C5k+3)=m-1C5k+2+m-1C5k+3 mC5k+4=(m-1C5k+3+m- 1C5k+4)=m-1C5k+3+m-1C5k+4 これらの右辺はいずれも、(D)または(E)の隣どうしの項の和だから、 (D)の場合、隣どうし加えて、 2am-1-fm-1、 2am-1+fm-2、 2am- 1+fm-2、2am-1-fm-1、2am-1-2fm-1 となり、am=2am-1-fm-1とおくと、これらは、 am、am+fm-1+fm-2、am+fm- 1+fm-2、am、am-fm-1 である。フィボナッチ数列の性質より、fm-1+fm-2=fmだから、 これらは、am、am+fm、am+fm、 am、am-fm-1 となり、(C)の後者であることがわかる。 (E)の場合も隣どうし加えて、 2am-1+fm-1、 2am-1-fm-2、 2am-1- fm-2、2am-1+fm-1、2am-1+2fm-1 となり、am=2am-1+fm-1とおくと、これらは、 am、am-(fm-1+fm-2)、am-(fm- 1+fm-2)、am、am+fm-1 である。同様にして、 これらは、am、am-fm、am-fm、 am、am+fm-1 となり、(C)の前者であることがわかる。 いずれも場合においても、n=mのとき、(C)が成り立つ。 したがって、(C)はnが4以上のすべての自然数について成り立つ。 |
|||||||||||||||||||||
|
|||||||||||||||||||||
ここで、(C)の前者の場合、nC5kを小、中、大のうち、小の数とする
と、 an-fn、an、an+fn-1、an、 an-fnの5つの数は、 nC5k、 nC5k+fn、nC5k+fn+fn- 1、nC5k+fn、nC5k と書き表せて、この5つの数の和は、 5nC5k+3fn+fn-1<5( nC5k+fn) この式の左辺は2nと等しいから、 2n<5(nC5k+fn) |
|||||||||||||||||||||
|
|||||||||||||||||||||
次に、小、中、大のうち、大の数とすると、 an-fn、an、an+fn-1、an、 an-fnの5つの数は、 nC5k-fn-fn- 1、nC5k-fn-1、nC5k、 nC5k-fn-1、nC5k-fn-fn- 1 と書き表せて、この5つの数の和は、 5nC5k-2fn-4fn-1 |
|||||||||||||||||||||
|
|||||||||||||||||||||
5nC5k-2fn-4fn-1>5
nC5k-2fn-3fn=5(nC5k-
fn) この式の左辺は2nと等しいから、 2n>5(nC5k-fn) |
|||||||||||||||||||||
|
|||||||||||||||||||||
また、(c)の後者の場合も同様である。 |
|||||||||||||||||||||
|
|||||||||||||||||||||
n=3のとき、 3C5k=3C0=1 |
|||||||||||||||||||||
|
|||||||||||||||||||||
|
|||||||||||||||||||||
|
|||||||||||||||||||||
ゆえに、nが3以上のすべての自然数について、 |
|||||||||||||||||||||
|
|||||||||||||||||||||
【コメント】 n=1、2 のときも成り立ちますね。 |
◆愛知県 Y.M.Ojisan さんからの解答。
【一般論】
パスカルの葉巻を数式で表すと下記です。
(下図Bはn=5の場合です。)
Am+1=B・Am
A0=(1,0,0,…0)t
Bの特性式は(λ―1)n=1です。
従ってBは p番目の固有値 | p | λ=1+exp( | 2πpj n | )に対して |
固有ベクトル pEk= | exp( | 2πpkj n | )をもつような行列です。 |
A0を固有ベクトル成分に分解すると下記です。
A0= | n-1 k=0 | pEk n |
特に最大の固有値はλ0=2で、
0E=(1,1,1,…1)tですからAmのp=0対応成分は
Amk= | 2m n | (k=0〜n−1)であることが分かります。 |
次に大きな固有値は
λ | 1 | 、λ | n-1 | =1± | exp( | 2πj n | )で、その大きさ(絶対値)は |
すなわちAmのp=1、n−1の対応合成成分は
A | mk | =2cos( | πk n | )(2cos( | π n | )) | m | /n (k=0〜n−1) |
であることが分かります。
従って、一般にAm0はおおよそ下記であると言えます。
Am0≒ | 2m n | −2*(2cos( | π n | )) | m | /n〜 | 2m n | +2*(2cos( | π n | )) | m | /n |
【n=5の場合】
cos( | π 5 | )= | 1+ 4 | です。よって |
Am0≒ | 2m 5 | −2*( | 1+ 2 | ) | m | /5〜 | 2m 5 | +2*( | 1+ 2 | ) | m | /5 |
一方フィボナッチ数列f(m)は mが大きくなれば
f(m)={( | 1+ 2 | ) | m | +( | 1− 2 | ) | m | }/ | ≒( | 1+ 2 | ) | m | / |
です。
また、 | 2 5 | < | 1 | = | 5 | です。 |
|A | m0 | − | 2m 5 | |<f(m)になります。 |
【n=7の場合】
2*cos( | π 7 | )=1.801938 です。よって |
Am0≒ | 2m 7 | − | 2*(1.801938)m 7 | 〜 | 2m 7 | + | 2*(1.801938)m 7 |
となります。
これに対するフィボナッチ数列(三項)は最大の固有値の絶対値を合わせた下記の特性式から得られるものが適当でしょう。即ち、
0=(x−2 cos( | π 7 | )) (x+2 cos( | 2π 7 | )) (x−2 cos( | 3π 7 | ))=x3−x2−2x+1 |
であり、 f(n+3)=f(n+2)+2f(n+1)−f(n) で得られるものです。
ちなにみ n=5の場合のフィボナッチ数列はその最大の特性値と
Bの最大の固有値の絶対値(=2 cos( | π 5 | ))を合わせた |
0=(x−2 cos( | π 5 | )) (x+2 cos( | 2π 5 | ))=x2−x−1 |
から得ることができ、通常のフィボナッチ数列になっています。
【一般のフィボナッチの導出】
一般にnが奇数の場合のフィボナッチ数列は下記特性式から得られる漸化式によるものが整数係数になるので適当でしょう。(詳細略)
nが偶数の場合は、2飛びの漸化式になりますが、下記から得るのが妥当でしょう。
【P.S.】
フィボナッチとの関係はありそうですが、実際はBの2番目に大きい固有値の絶対値とフィボナッチの特性値がたまたま一致しているだけとも言えます。
実際、Bの3番目大きい固有値の絶対値とフィボナッチの2番目の特性値は符号が逆転しています。
この問題はむしろフーリエ級数展開と密接な関係にあると言えます。
式で書くと長くなってしまいましたが、下図のように書けば容易に理解できます。
同じ波長の正弦波は少しずらして加算しても、やはりもとの波長の正弦波です。
ただ、ずらす巾を一定とするとき、波数の少ないものほどそのその振幅は2倍近くになり、特に波長無限大(直流成分)は丁度2倍になります。
波長無限大成分を | 2m n | として特出すると、 |
◆京都府 大空風成 さんからの解答。
7の倍数の場合、
s6=1、s7=1、s8=3、s9=5 で、
s2n-1=s2n-
5+s2n-2、 s2n=s2n-3+s2n-2 として、
fn=s2n-1+s2n とおけば、
2n 7 |
-fn<nC7k< | 2n 7 |
+fn |
となります。
fnはフィボナッチ数列ではないのですが、
nC7k〜 nC7k+6の各項の差をとれば、
自然とs2nやs2n-1という数列が出てきて、それをfnとおきました。
9の倍数についてもやってみましたが、s3n、s3n-1、s3n-2という数列が出てき
ました。
4や6の倍数についてもやってみましたが、似たようなことになります。
しかし、次第にばらつきが激しくなるので、2nの2分割、3分割のような美しさが薄れますね。