FC2ブログ

Welcome to my blog

[答30] 拡張フィボナッチ数列

ヤドカリ

ヤドカリ


'


[答30] 拡張フィボナッチ数列

 数列 { Fn } を、F1=A, F2=B, Fn+2=Fn+1+Fn で定義する。

 また、Sm=F1+F2+……+Fm とする。

 F1=A, F2=B, F3=A+B, F4=A+2B, F5=2A+3B, F6=3A+5B,……

 S1=A, S2=A+B, S3=2A+2B, S4=3A+4B, S5=5A+7B, S6=8A+12B,……

 となって、A,Bがどんな自然数でも S6 は F5 の4倍です。

 では、A,Bがどんな自然数でも Sm が F25 の倍数であるとき、m=?

☆ F1=F2=1 のとき、フィボナッチ数列、 F1=1, F2=3 のとき、ルーカス数列といいます。



[解答] 一般に、A,Bがどんな自然数でも Sm が Fn の倍数であるとき、

 x2=x+1 の解を α,β(α>β) とすると、α≒1.6 で、α+β=1, αβ=-1 で、

 (α-β)Fn=(αn-1-βn-1)B+(αn-2-βn-2)A
 (α-β)Sm=(αm+1-βm+1-α+β)B+(αm-βm)A

 αβ=-1 を利用して、

 αn-1(α-β)Fn={ α2n-2+(-1)n }B+{ α2n-4-(-1)n }αA
 αm+1(α-β)Sm={ α2m+2+(-1)m-αm+2-αm }B+{ α2m-(-1)m }αA

 以下の計算を簡単にするために書きかえると、

 αn-1(α-β)Fn=α2n-4α(αB+A)+(-1)n(B-αA)
 αm+1(α-β)Sm=αmm-1)α(αB+A)-{ αm-(-1)m }(B-αA)

 よって、

 α2n-4 : (-1)n=αmm-1) : -{ αm-(-1)m }
 (-1)nαmm-1)=-α2n-4{ αm-(-1)m }
 ここで、αm-1>0,αm-(-1)m>0 だから、nは奇数で、
 αmm-1)=α2n-4{ αm-(-1)m }

 mが偶数のときは、m=2n-4。m>0 より、n>2。よって、nは3以上の奇数。
 このとき、Sm=(αn-2+βn-2)Fn
 ここで、Lk=αk+βk とおくと、
 L1=α+β=1, L2=α2+β2=α+1+β+1=3,
 Lk+2=αk+2+βk+2=αk+1+βk+1+αk+βk=Lk+1+Lk
 だから、Ln-2 は自然数、Sm は Fn の自然数倍になる。

 mが奇数のときは、
 αmm-1)=α2n-4m+1)
 (αm-α2n-4)(αm-1)=2α2n-4
 (αm-1)(αm-2n+4-1)=2
 ここで、m は奇数で、m=1 のときは 0<αm-1<1、m≧3 のときは αm-1>2
 また、α2=α+1 を利用して、(α3-1)(α-1)=2α(α-1)=2 だから、
 m=1, m-2n+4=3 または、m=3, m-2n+4=1 すなわち、n=m=1 または n=m=3。
 F1=A, S1=A, F3=A+B, S3=2A+2B で成り立つ。

 まとめると、
 nは3以上の奇数で m=2n-4 または m=n=1 または m=n=3


 問題では、n=25 より、m=46



[別解] uch*n*an様より下のコメント欄に頂きました。一般項を使わない素晴らしい解答です。

 まず,an = an-1 + an-2,a1 = a2 = 1 より,少し調べれば,
 Fn = an-2 ・ A + an-1 ・ B
 Sm = am ・ A + (am+1 - 1) ・ B
 となるのが分かります。ただし,a-1 = 1,a0 = 0 です。
 そこで,任意の A,B に対して,Sm = c ・ Fn, c, m, n は自然数,となるには,
 am = c ・ an-2 ≧ an-2
 am+1 = c ・ an-1 + 1
 です。ここで,最初の式より m ≧ n-2 です。
 そして,
 am+1 = c ・ an-1 + a-1
 am = c ・ an-2 - a0
 と書けるので,順次,辺々を引いて
 am-1 = c ・ an-3 + a1
 am-2 = c ・ an-4 - a2
 am-3 = c ・ an-5 + a3
 …
 am-(n-3) = c ・ a1 + (-1)n-2 ・ an-3 = c + (-1)n-2 ・ an-3
 am-(n-2) = c ・ a0 + (-1)n-1 ・ an-2 = (-1)n-1 ・ an-2

 そこで,
 n が偶数のとき,am-(n-2) = - an-2 ≦ 0 で,このような m ≧ n-2 は存在しません
 n が奇数のとき,am-(n-2) = an-2,c = am-(n-3) + an-3
 n ≧ 5 ならば,m-(n-2) = n-2,m = 2(n-2),c = an-1 + an-3
 n = 3 ならば,m = 2, c = 1 又は m = 3, c = 2
 n = 1 ならば,m = 1, c = 1
 です。

 まとめると,
 n = 1 ならば,m = 1, c = 1
 n = 3 ならば,m = 2, c = 1 又は m = 3, c = 2
 n が 5 以上の奇数ならば,m = 2(n-2), c = an-1 + an-3
 n が偶数ならば,m は存在しない,
 になります。


.

スポンサーサイト



Comments 13

There are no comments yet.
ヤドカリ  
No title

3項間の漸化式の解き方を既知のものとして説明しました。
途中の計算が多いのですが、結果は簡単です。

いっちゃん  
No title

こんばんは。
海っていつ見てもいいですね。見てるだけで癒されます。
海って自分のこころの色でいろいろ彩どりますね。。
沖縄のコバルトブルーの海はすてきでした。。今でも遊泳できる
そうです。。笑

ヤドカリ  
No title

そうですね、見てるだけで癒されます。
陽が昇る時と沈む時もいいですね。

uch*n*an  
No title

ご参考までに,私の解法を書いておきます。
まず,a(n) = a(n-1) + a(n-2),a(1) = a(2) = 1 より,少し調べれば,
F(n) = a(n-2) * A + a(n-1) * B
S(m) = a(m) * A + (a(m+1)) - 1) * B
となるのが分かります。ただし,a(-1) = 1,a(0) = 0 です。
そこで,任意の A,B に対して,S(m) = c * F(n), c, m, n は自然数,となるには,
a(m) = c * a(n-2) >= a(n-2)
a(m+1) = c * a(n-1) + 1
です。ここで,最初の式より m >= n-2 です。

uch*n*an  
No title

そして,
a(m+1) = c * a(n-1) + a(-1)
a(m) = c * a(n-2) - a(0)
と書けるので,順次,辺々を引いて
a(m-1) = c * a(n-3) + a(1)
a(m-2) = c * a(n-4) - a(2)
a(m-3) = c * a(n-5) + a(3)
...
a(m-(n-3)) = c * a(1) + (-1)^(n-2) * a(n-3) = c + (-1)^(n-2) * a(n-3)
a(m-(n-2)) = c * a(0) + (-1)^(n-1) * a(n-2) = (-1)^(n-1) * a(n-2)

uch*n*an  
No title

そこで,
n が偶数のとき,a(m-(n-2)) = - a(n-2) <= 0 で,このような m >= n-2 は存在しません
n が奇数のとき,a(m-(n-2)) = a(n-2),c = a(m-(n-3)) + a(n-3)
n >= 5 ならば,m-(n-2) = n-2,m = 2(n-2),c = a(n-1) + a(n-3)
n = 3 ならば,m = 2, c = 1 又は m = 3, c = 2
n = 1 ならば,m = 1, c = 1
です。まとめると,
n = 1 ならば,m = 1, c = 1
n = 3 ならば,m = 2, c = 1 又は m = 3, c = 2
n が 5 以上の奇数ならば,m = 2(n-2), c = a(n-1) + a(n-3)
n が偶数ならば,m は存在しない,
になります。

サリー  
No title

この頁を私の肩越しに見ていた主人が一言、"Fibonacci?"
一瞬、「わぁ、英語も一緒なんだ・」と思いましたが、人名だから当たり前ですね・・・ハハ。

ヤドカリ  
No title

> uch*n*an様
詳しい解答をありがとうございます。
添え字を見やすくして上にも掲載させて頂きました。

ヤドカリ  
No title

サリーさんへ^^
ご主人さんは、数学の素養がおありですね。
私もこの項目が外国語で書かれていても、式をみれば、"Fibonacci"
と判断できます。

サリー  
No title

早速主人に伝えたところ、「自分には数学の素養はないけれども、Fibonacciはとても興味深い。Fibonacciの素晴らしいところは、数学の素養のない人や子供でさえも楽しめるところだ。」と目を輝かせて力説してます。

ヤドカリ  
No title

サリーさん、私は以前にもフィボナッチを扱っています。
http://blogs.yahoo.co.jp/oka_yadokary/881120.html
http://blogs.yahoo.co.jp/oka_yadokary/955787.html
機会があれば、サリ夫さんにも伝えてあげて下さい。

uch*n*an  
No title

やどかりさん,掲載ありがとうございます。面白い問題でした。

ヤドカリ  
No title

uch*n*anさん、貴殿の解答は力作です。
コメント欄では添え字が使えず、見にくいので、
添え字を使った見やすい形での解答にしたいと思い、記事に追加しました。