平成１５年８月１７日

[流れ星]

　　　　　　　　第１２３回数学的な応募問題解答NO1

　　　　　　　　　　＜解答募集期間：７月２７日〜８月１７日＞

［フィボナッチ数列］

　　　

太郎さんは、月曜日第７限の「総合的な学習の時間」に１年生を対象にして、「楽しい数学」と称した講座を受け持っています。現在は「フィボナッチ数列」の調べ学習をしています。この中で、次のような性質があるのではないかと生徒に伝えています。
　参考：｛ａ_ｎ｝：｛１，１，２，３，５，８，１３，２１，３４，５５，８９，・・・｝をフィボナッチ数列という。

H−Ｅ

H

(Hⁿ−Ｅ)

＝

H

＋H²＋・・・＋H^n-1

Ｈ

＝

＝

^-

¹

−

１

１

１

０

０

１

１

１

＝

(

H−Ｅ)^-1

H

²

＝

１

１

１

２

＝

＋

１

０

０

１

０

１

１

１

＝

H

＋Ｅ

H

ⁿ⁺¹

＝

＝

Ｆ

_n

Ｆ

_n+1

Ｆ

_n+1

Ｆ

_n+2

＝

Ｆ

_n

F

_n+1

F

_n+F_n-1

F

_n+F_n+1

０

１

１

１

＝

Ｆ

_n-1

Ｆ

_n

Ｆ

_n

Ｆ

_n+1

H

ⁿ・Ｈ

＝

０

１

１

１

Ｆ

₀

Ｆ

₁

Ｆ

₁

Ｆ

₂

＝

H

＝

H

ⁿ

Ｆ

_n-1

Ｆ

_n

Ｆ

_n

皆さん、考え方がわかったら、全部でなくていいですから、解答とペンネームを添えて、メールで送ってください。
待っています。

ＮＯ１「H7K」さん 7/26: 10時34分 受信 更新8/17

帰納法でなくても解けるような気がするんですが...

1: ●n=1,2のとき
　　1+F1=2=F3.成立
    1+F1+F2=3=F4.成立
　 ●n=kのとき，成立していると仮定，
　　 すなわち，1+F1+F2+...+Fk=F(k+2)と仮定すると
　　 両辺にF(k+1)を足し，1+F1+F2+...+Fk+F(k+1)=F(k+2)+F(k+1)=F(k+3)=F(k+1+2).
　　 よって，n=k+1の場合も成立することが分かる．//
2: ●n=1,2のとき
　　 F1=F2.成立
　　 F1+F3=3=F4.成立
　 ●n=kのとき，成立していると仮定，
　　 すなわち，F1+F3+...+F(2k-1)=F(2k)と仮定すると
　　 両辺にF(2k+1)を足し，F1+F3+...+F(2k-1)+F(2k+1)=F(2k)+F(2k+1)=F(2k+2)
     ←→F1+F3+...+F(2k-1)+F(2(k+1)-1)=F(2(k+1)).
　　 よって，n=k+1の場合も成立することが分かる．//
3: ●n=1,2のとき
　　1+F2=2=F3.成立
    1+F2+F4=5=F6.成立
　 ●n=kのとき，成立していると仮定，
　　 すなわち，1+F2+F4+...+F(2k)=F(2k+1)と仮定すると
　　 両辺にF(2k+2)を足し，1+F2+F4+...+F(2k)+F(2k+2)=F(2k+1)+F(2k+2)=F(2k+3)
     ←→1+F2+F4+...+F(2k)+F(2(k+1))=F(2(k+1)+1)
　　 よって，n=k+1の場合も成立することが分かる．//
4: 「石飛び」で考える．
　　O O O O ...O O Oと2n+1この石があり，左から1,2,3,..,2n+1の番号が付いているとする．
　　ここで，1→nまで飛ぶ（但し石を抜かすのは1こ飛ばしのみ）とすると，この場合の通り数はF(n).
　　一方，2n+1個飛ぶ場合は
　　・n-1とn+1を飛ぶ（nは通過）F(n-1)F(2)F(n+1)=F(n-1)F(n+1)通り
　　・nを飛ぶ……FnF(n+2)=Fn^2+Fn(Fn+1)通り
　　なので，計Fn^2+(F(n-1)+Fn)F(n+1)=Fn^2+F(n-1)^2通りだが，全体はまたF(2n+1)通りでもあるはず，
　　よって示された．
5: ●n=1,2のとき
　 F1^2=1=F1F2.成立
   F1^2+F2^2=2=F2F3.成立
   ●n=kのとき，成立していると仮定，
　 　すなわち，F1^2+F2^2+...+Fk^2=FkF(k+1)と仮定すると
　 　両辺にF(k+1)^2を加え，F1^2+F2^2+...+Fk^2+F(k+1)^2=FkF(k+1)+F(k+1)^2=F(k+2)F(k+1)=F(k+1)F(k+1+1).
　　 よって，n=k+1の場合も成立することが分かる．//

ＮＯ２「toru」さん　　　7/29: 13時54分 受信 更新8/17

１．Fn+2―Fn+1＝Fn 　においてn=1,2,3,------,nとして辺辺をたすとFn+2―F2＝F1
＋F2＋F3＋-------＋Fn  F2＝1だから性質１が成り立つ。

２．F2n+2―F2n＝F2n+1 (n=1,2,3----)は, F0＝0とすればn=0でも成り立つから、
n=0,1,2,3,------,n-1 として辺辺たすとF2n＝F1＋F3＋F5＋---＋F2n-1

３． F2n+1―F2n-1＝F2n  においてn=1,2,3,------,nとして辺辺をたすとF2n+1―F1
＝F2＋F4＋F6＋-------＋F2n,  F1＝1だから性質3が成り立つ。

４． F2n＝2FnFn+1―Fn^2, F2n+1＝Fn^2＋Fn+1^2と仮定して数学的帰納法で証明する、
n=1のときF2=2F1F2―F1^2＝1,F3=F1^2＋F2^2＝2,で成り立つ、n=n+1として、F2n+2
＝F2n＋F2n+1＝(2FnFn+1―Fn^2)＋(Fn^2＋Fn+1^2)＝2FnFn+1＋Fn+1^2＝2(Fn+2
―Fn+1)Fn+1＋Fn+1^2＝2Fn+1Fn+2―Fn+1^2, F2n+3＝F2n+1＋F2n+2＝(Fn^2＋Fn+1^2)
＋(2Fn+1Fn+2―Fn+1^2)＝Fn^2＋2Fn+1Fn+2＝(Fn+2―Fn+1)^2＋2Fn+1Fn+2＝Fn+1^2
＋Fn+2^2 より性質４は証明された。

５．Fn+1Fn+2―FnFn+1＝Fn+1(Fn+Fn+1)―FnFn+1=Fn+1^2 においてF0=0 とすればこれ
はn=0でも成り立つからn=0,1,2,---n-1として辺辺たせば、FnFn+1＝F1^2＋F2^2
＋F3^2＋-------＋Fn^2

＜コメント＞性質１、２、３、５も数学的帰納法を使えば簡単に証明できますが、どうも答を与えられて確かめているだけのようで気に入らないので、なんでこんな式が出てくるのか考える上でも、直接導いてみました。ところが、どうも４はうまく行かずに結局帰納法を使った上にあまりスマートでない解答になってしまいました。きっと、もっとエ
レガントな方法があるのでしょうが、なかなか時間もとれず、取りあえず答を送っておきます。　

「toru」さん 8/01: 11時07分 受信 更新8/17

フィボナッチ数列F0=0,F1=1,Fn+2=Fn+1+Fn (n=0,1,2---)の一般項はx^2-x-1=0の２解
をα、β(α<β)とすると α＋β=1,αβ=-1で Fn=(β^n―α^n)／(β―α)　
ここで(β^(2n+1)―α^(2n+1))(β―α)＝β^2(n+1)＋α^2(n+1)＋β^(2n)＋α^(2n)
＝(β^n＋α^n)^2＋(β^(n+1)＋α^(n+1))^2が成り立つから、両辺を(β―α)^2で割
れば、F2n+1＝Fn^2＋Fn+1^2が成り立つことが分かります。ここでαβ=-1は使ってい
ますが、α＋β=1の方は使っていませんので、この関係はF0=0,F1=1,Fn+2=kFn+1+Fn
でも成り立つと思われます。例えばk＝２とすると、この数列
は(0),1,2,5,12,29,70,169,408,985,2378,5741,-----となりますが、1^2+2^2=5,
2^2+5^2=29, 5^2+12^2=169 というような感じで成り立っています。

＜コメント＞性質４について別解を作ってみました。一般解を求めてごりごり計算するのはどうかとも思いましたが、やってみるとこの問題に関してはこの方がよいかと？、どんなもんでしょう。

ＮＯ３「kasama」さん　 7/29: 23時01分 受信 更新8/17

【性質１】
　漸化式を適当に操作すると出来そうですね。漸化式を順番に並べてみると、

　　F(n) + F(n+1) = F(n+2)
　　F(n-1) + F(n) = F(n+1)
　　F(n-2) + F(n-1) = F(n)
　　　　　・・・
　　F(1) + F(2) = F(3)　となります。これらの式を加算すると

　2×{F(1)+F(2)+・・・+F(n)} - F(1) + F(n+1) =
　　 {F(1)+F(2)+・・・+F(n)} - F(1) - F(2) + F(n+1) + F(n+2)
　⇒ F(1)+F(2)+・・・+F(n) = F(n+2) - F(2)

　となります。ここで、F(2)=1ですから性質１は成り立ちます。以下の性質２、３から導くこともできると思います。でも順番通りに！

【性質２】
　これも漸化式を適当に操作すると出来そうですね。

　　F(2n) = F(2n-1) + F(2n-2)
　　　　　= F(2n-1) + F(2n-3) + F(2n-4)
　　　　・・・・・
　　　　　= F(2n-1) + F(2n-3) + F(2n-5) + ・・・ + F(3) + F(2)

　ここで、F(2)=F(1)ですから、性質２は成り立ちます。

【性質３】
　これも同様にして

　　F(2n+1) = F(2n) + F(2n-1)
　　　　　　= F(2n) + F(2n-2) + F(2n-3)
　　　　・・・・・
　　　　　　= F(2n) + F(2n-2) + F(2n-4) + ・・・ + F(2) + F(1)

　ここで、F(1)=1ですから、性質３は成り立ちます。


【性質４】
　うーん難しい、漸化式をうまく変形するとできる(？)かもしれませんが、技量がないので少し回り道をして考えました。
　まず、少し別の方向から考えて、自然数m、nに対して、

    F(n) = F(m+1)F(n-m) + F(m)F(n-m-1) ・・・ (1)

　が成り立つことを確かめます。mに関する数学的帰納法で証明します。

�@m=1の場合

　F(n) = F(1+1)F(n-1) + F(1)F(n-1-1)
　　　 = F(2)F(n-1) + F(1)F(n-2)
　　　 = F(n-1) + F(n-2)

　となり成り立ちます。

�Am=kのとき(1)式が成立するとして、m=k+1の場合
　仮定より、

　　F(n) = F(k+1)F(n-k) + F(k)F(n-k-1)

　です。これを変形して、

　　F(n) = F(k+1){F(n-k-1) + F(n-k-2)} + F(k)F(n-k-1)
　　　　 = F(k+1)F(n-k-1) + F(k+1)F(n-k-2) + F(k)F(n-k-1)
　　　　 = {F(k+1) + F(k)}F(n-k-1) + F(k+1)F(n-k-2)
　　　　 = F(k+2)F(n-k-1) + F(k+1)F(n-k-2)

　一方、(1)式にm=k+1を代入して

　　F(n) = F((k+1)+1)F(n-(k+1)) + F(k+1)F(n-(k+1)-1)
　　　　 = F(k+1+1)F(n-k-1) + F(k+1)F(n-k-1-1)
　　　　 = F(k+2)F(n-k-1) + F(k+1)F(n-k-2)

　よって、m=k+1の場合も成り立ちます。

�B上記�@、�Aよりすべての自然数m、nに対して、(1)式が成り立ちます。

　さて、かなり道草をしてしまいましたが、もう少しです。(1)においてn→2n+1、m→nとすると

　　F(2n+1) = F(n+1)F(2n+1-n) + F(n)F(2n+1-n-1)
　　　　　　= F(n+1)^2 + F(n)^2

　よって、性質４は成り立ちます。

【性質５】
　これも少し回り道をします。

　　F(i)F(i+1) = F(i){F(i-1) + F(i)} = F(i)F(i-1) + F(i)^2
　　⇒ F(i)^2 = F(i)F(i+1) - F(i)F(i-1) ・・・(1)

　(1)式をi=2,3,・・・,nの範囲で加算すると

　　左辺 = F(2)^2 + F(3)^2 + ・・・ + F(n)^2
　　右辺 = F(2)F(3) + F(3)F(4) + ・・・ + F(n)F(n+1)
　　　　 - { F(2)F(1) + F(3)F(2) + ・・・ + F(n)F(n-1) }
　　　　 = F(n)F(n+1) - F(2)F(1)

　つまり、

　　F(2)^2 + F(3)^2 + ・・・ + F(n)^2 = F(n)F(n+1) - F(2)F(1)

　となり、F(2)=F(1)=F(1)^2に注意すると、

　　F(1)^2 + F(2)^2 + F(3)^2 + ・・・ + F(n)^2 = F(n)F(n+1)

　よって、性質５は成り立ちます。

＜コメント＞さて、懲りずに第123回応募問題に挑戦してみました（作業を増やしてしまうことをご勘弁下さい）。
　問題のフィボナッチ数列の関係式はよく目にしますが、「証明してみて下さい」と言われると・・・うーんと言った感じですね。でも何とか頭をフル回転させて証明したつもりす。基本的には、コツコツと数学的帰納法でやれば、すべて証明できるものと思いますが、性質４以外は漸化式を変形して証明してみました。

「kasama」さん 8/01: 22時41分 受信 更新817

【準備】

　前回の問題では行列式（これは大学で習う）を使ってしまいましたが、今回は高校数学で習う行列を利用します。いきなり証明するのは大変なので少し準備体操をしておきます。

まず、フィボナッチ数列を以下のような行列で表現します。

Ｆ_n+1

 NO1「H7K」さん 7/26: 10時34分 受信 更新8/17

帰納法でなくても解けるような気がするんですが...

1: ●n=1,2のとき
　　1+F1=2=F3.成立
    1+F1+F2=3=F4.成立
　 ●n=kのとき，成立していると仮定，
　　 すなわち，1+F1+F2+...+Fk=F(k+2)と仮定すると
　　 両辺にF(k+1)を足し，1+F1+F2+...+Fk+F(k+1)=F(k+2)+F(k+1)=F(k+3)=F(k+1+2).
　　 よって，n=k+1の場合も成立することが分かる．//
2: ●n=1,2のとき
　　 F1=F2.成立
　　 F1+F3=3=F4.成立
　 ●n=kのとき，成立していると仮定，
　　 すなわち，F1+F3+...+F(2k-1)=F(2k)と仮定すると
　　 両辺にF(2k+1)を足し，F1+F3+...+F(2k-1)+F(2k+1)=F(2k)+F(2k+1)=F(2k+2)
     ←→F1+F3+...+F(2k-1)+F(2(k+1)-1)=F(2(k+1)).
　　 よって，n=k+1の場合も成立することが分かる．//
3: ●n=1,2のとき
　　1+F2=2=F3.成立
    1+F2+F4=5=F6.成立
　 ●n=kのとき，成立していると仮定，
　　 すなわち，1+F2+F4+...+F(2k)=F(2k+1)と仮定すると
　　 両辺にF(2k+2)を足し，1+F2+F4+...+F(2k)+F(2k+2)=F(2k+1)+F(2k+2)=F(2k+3)
     ←→1+F2+F4+...+F(2k)+F(2(k+1))=F(2(k+1)+1)
　　 よって，n=k+1の場合も成立することが分かる．//
4: 「石飛び」で考える．
　　O O O O ...O O Oと2n+1この石があり，左から1,2,3,..,2n+1の番号が付いているとする．
　　ここで，1→nまで飛ぶ（但し石を抜かすのは1こ飛ばしのみ）とすると，この場合の通り数はF(n).
　　一方，2n+1個飛ぶ場合は
　　・n-1とn+1を飛ぶ（nは通過）F(n-1)F(2)F(n+1)=F(n-1)F(n+1)通り
　　・nを飛ぶ……FnF(n+2)=Fn^2+Fn(Fn+1)通り
　　なので，計Fn^2+(F(n-1)+Fn)F(n+1)=Fn^2+F(n-1)^2通りだが，全体はまたF(2n+1)通りでもあるはず，
　　よって示された．
5: ●n=1,2のとき
　 F1^2=1=F1F2.成立
   F1^2+F2^2=2=F2F3.成立
   ●n=kのとき，成立していると仮定，
　 　すなわち，F1^2+F2^2+...+Fk^2=FkF(k+1)と仮定すると
　 　両辺にF(k+1)^2を加え，F1^2+F2^2+...+Fk^2+F(k+1)^2=FkF(k+1)+F(k+1)^2=F(k+2)F(k+1)=F(k+1)F(k+1+1).
　　 よって，n=k+1の場合も成立することが分かる．//

NO2「toru」さん　　　7/29: 13時54分 受信 更新8/17

１．Fn+2―Fn+1＝Fn 　においてn=1,2,3,------,nとして辺辺をたすとFn+2―F2＝F1
＋F2＋F3＋-------＋Fn  F2＝1だから性質１が成り立つ。

２．F2n+2―F2n＝F2n+1 (n=1,2,3----)は, F0＝0とすればn=0でも成り立つから、
n=0,1,2,3,------,n-1 として辺辺たすとF2n＝F1＋F3＋F5＋---＋F2n-1

３． F2n+1―F2n-1＝F2n  においてn=1,2,3,------,nとして辺辺をたすとF2n+1―F1
＝F2＋F4＋F6＋-------＋F2n,  F1＝1だから性質3が成り立つ。

４． F2n＝2FnFn+1―Fn^2, F2n+1＝Fn^2＋Fn+1^2と仮定して数学的帰納法で証明する、
n=1のときF2=2F1F2―F1^2＝1,F3=F1^2＋F2^2＝2,で成り立つ、n=n+1として、F2n+2
＝F2n＋F2n+1＝(2FnFn+1―Fn^2)＋(Fn^2＋Fn+1^2)＝2FnFn+1＋Fn+1^2＝2(Fn+2
―Fn+1)Fn+1＋Fn+1^2＝2Fn+1Fn+2―Fn+1^2, F2n+3＝F2n+1＋F2n+2＝(Fn^2＋Fn+1^2)
＋(2Fn+1Fn+2―Fn+1^2)＝Fn^2＋2Fn+1Fn+2＝(Fn+2―Fn+1)^2＋2Fn+1Fn+2＝Fn+1^2
＋Fn+2^2 より性質４は証明された。

５．Fn+1Fn+2―FnFn+1＝Fn+1(Fn+Fn+1)―FnFn+1=Fn+1^2 においてF0=0 とすればこれ
はn=0でも成り立つからn=0,1,2,---n-1として辺辺たせば、FnFn+1＝F1^2＋F2^2
＋F3^2＋-------＋Fn^2

＜コメント＞　性質１、２、３、５も数学的帰納法を使えば簡単に証明できますが、どうも答を与えられて確かめているだけのようで気に入らないので、なんでこんな式が出てくるのか考える上でも、直接導いてみました。ところが、どうも４はうまく行かずに結局帰納法を使った上にあまりスマートでない解答になってしまいました。きっと、もっとエレガントな方法があるのでしょうが、なかなか時間もとれず、取りあえず答を送っておきます。　

「toru」さん 8/01: 11時07分 受信 更新8/17

フィボナッチ数列F0=0,F1=1,Fn+2=Fn+1+Fn (n=0,1,2---)の一般項はx^2-x-1=0の２解
をα、β(α<β)とすると α＋β=1,αβ=-1で Fn=(β^n―α^n)／(β―α)　
ここで(β^(2n+1)―α^(2n+1))(β―α)＝β^2(n+1)＋α^2(n+1)＋β^(2n)＋α^(2n)
＝(β^n＋α^n)^2＋(β^(n+1)＋α^(n+1))^2が成り立つから、両辺を(β―α)^2で割
れば、F2n+1＝Fn^2＋Fn+1^2が成り立つことが分かります。ここでαβ=-1は使ってい
ますが、α＋β=1の方は使っていませんので、この関係はF0=0,F1=1,Fn+2=kFn+1+Fn
でも成り立つと思われます。例えばk＝２とすると、この数列
は(0),1,2,5,12,29,70,169,408,985,2378,5741,-----となりますが、1^2+2^2=5,
2^2+5^2=29, 5^2+12^2=169 というような感じで成り立っています。

＜コメント＞性質４について別解を作ってみました。一般解を求めてごりごり計算するのはどうかとも思いましたが、やってみるとこの問題に関してはこの方がよいかと？、どんなもんでしょう。

NO4「Kashiwagi」さん 8/03: 14時38分 受信 更新8/17

第123回問題

　色々考えてみましたが、やはりオーソドックスな帰納法で行く事に致しました。

1. ｎ＝１の時１＋F_１＝１＋１＝２＝F₃となり成立する。

ｎ＝ｋの時成立すると仮定すると、１＋F₁＋F₂＋…・＋F_k＝F_k+2

両辺にFk+1を加えると１＋F1＋F2＋…・＋Fk＋Fk+1＝Fk+2＋Fk+1

右辺のFk+2＋Fk+1＝Fk+3であるから、

１＋F1＋F2＋…・＋Fk＋Fk+1＝Fk+3＝F(k+1)+2、即ちｎ＝k+1でも成立する。

因って本命題は証明された。

(2)､(3)も(1)と全く同様にして証明できますので省略させて頂きます。

次に(4)ですが、まず(5)から証明させて頂きます。

(5) ｎ＝１の時F１²＝１²＝１＝１×1＝F1F２となり成立する。

ｎ＝ｋの時成立すると仮定すると、F1²＋F2²＋…・＋Fk²＝FkFk+1

両辺にF^２k+1を加えると

F1²＋F2²＋…・＋Fk+1²＝FkFk+1＋Fk+1²＝Fk+1(Fk+1＋Fk)＝Fk+1Fk+2

即ちｎ＝k+1でも成立する。因って本命題は証明された。

(4) ｎ＝１の時F１²＋F2²＝１+1＝2＝F₃となり成立する。

ｎ＝ｋの時成立すると仮定すると、

(F１²＋F2²)＋(F2²＋F3²)＋(F3²＋F4²)＋…・＋(Fk²＋Fk+1²)＝F3＋F5＋F7＋…・F2k+1

両辺にFk+1²＋Fk+2²を加えると、

左辺は(F１²＋F2²＋…・＋Fk+1²)＋(F2²＋F3²＋…・＋Fk+2²) 、ここで先ほどの性質５を適用するとFk+1Fk+2＋Fk+2Fk+3 −F1²

又、右辺はF3＋F5＋F7＋…・F2k+1 ＋Fk+1²＋Fk+2²、ここで先ほどの性質２を適用するとF2k+2−F1 ＋Fk+1²＋Fk+2²

因ってFk+1Fk+2＋Fk+2Fk+3 −F1² ＝F2k+2−F1 ＋Fk+1²＋Fk+2²

F1²＝F1＝１であるから、変形して、

Fk+1²＋Fk+2² ＝Fk+1Fk+2＋Fk+2Fk+3 −F2k+2

ここで補題　Fa+ｂ＝Fa-1Fb＋FaFb+1を用いる。

今、a＝k+2、ｂ＝k+2を上記式に代入すると、Fk+1Fk+2＋Fk+2Fk+3＝F2k+4となる。

これを先ほどの式に代入すると、

Fk+1Fk+2＋Fk+2Fk+3 −F2k+2＝F2k+4−F2k+2＝F2k+3

因ってFk+1²＋Fk+2² ＝F2k+3

即ちｎ＝k+1でも成立する。因って本命題は証明された。

＜コメント＞　今回の問題は正に性質４の証明に狙いが有るのですね。私はまず性質５を証明し、補題まで
使ってしまいました。高校生にどの様に証明なさるのですか？お教え頂けると幸いでございます。性質２，３の証明を書くのが面倒で飛ばしてしまいました

NO5「午年のうりぼう」さん 8/:16 22時55分　受信 更新8/17

（１）

（２）

（３）

NO6「中川幸一」さん 8/17 15時03「分　受信 更新8/31

　　　　＜自宅＞　　mizuryu@aqua.ocn.ne.jp