『フィボナッチ数列の性質 Part4』 解答

◆広島県　清川　育男 さんからの解答。

●準備

1)

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

n=1のとき、
F(m+1)=F(m-1)*F(1)+F(m)*F(2)=F(m-1)+F(m)
成立。

n≦kのとき、
F(m+k)=F(m-1)*F(k)+F(m)*F(k+1)が成立すると仮定する。

F(m+k)+F(m+(k-1))
=F(m-1)*F(k)+F(m)*F(k+1)+F(m-1)*F(k-1)+F(m)*F(k)
=F(m-1)*(F(k)+F(k-1))+F(m)*(F(k+1)+F(k))
=F(m-1)*F(k+1)+F(m)*F(k+2)

n=k+1 でも成立。

2)

F(m)はF(mn)を割り切る。すべての自然数m,n

n=1のとき、F(m) | F(m)
成立。

n=kのとき、F(m) | F(mk)が成立すると仮定する。

F(m(k+1))=F(mk+m)=F(mk-1)*F(m)+F(mk)*F(m+1)

F(m) | F(mk) であるから、F(m) | F(m(k+1))

n=k+1 でも成立。

●問題の証明

[m,n]=k とする。
m=a1*k、n=a2*k
左辺=F(k)

準備 2)より、
F(m)=F(a1*k)、F(k) | F(m)
F(n)=F(a2*k)、F(k) | F(n)
[F(m),F(n)]=F(k)
右辺=F(k)

以上で証明された。

◆茨城県　小川　康幸 さんからの解答。

この問題を一般化して、以下で定義する数列U_nに対して、定理を示すことにする。

a,bを互いに素な整数とする。

U_nを、U₀=0、U₁=1、U_n+1=a*U_n-b*U_n-1 （ただしn≧1)、
V_nを、V₀=2、V₁=a、V_n+1=a*V_n-b*V_n-1 （ただしn≧1)、

以後、nを0以上の整数とする。
U_nとV_nは、二次方程式、x²-a*x+b=0の二つの解をαとβとすると、

UnはUn=

αn-βn α-β

、

V_nは、V_n=αⁿ+βⁿと書ける。

この事を使って、kとhを0≦h≦kなる自然数とすると、

式１
U_k+h=U_k*V_h-b^h*U_k-h

式２
U_2k=U_k*V_k

が成立する事が分かる。

定理１

kがmで割り切れるならば、U_kもU_mで割り切れる。

証明

仮定より、m=k*gと書ける。

gに関する数学的帰納法で証明する。

g=1のときは明らか、
g=2のときはU_2k=U_k*V_kより、定理が成り立つ。

g=s、s-1のとき、正しいと仮定する。
（ただし、sは2以上の自然数）

U_(s+1)*k=U_s*k*V_k-b^k*U_(s-1)*k

仮定より、
U_s*k=U_k*L、U_(s-1)*k=U_k*Fと書ける。

U_(s+1)*k=U_k*(L*V_k-b^k*F)

よって、g=s+1のときも正しい。

証明終

自然数hが数列U_n(nは1以上の自然数とする)のうちの、あるU_nの値を割り切るとき、
hが割り切るU_nのうち、nの値が最小となるものをとり、このときのnの値をρ(h)とする。

定理２

hを、bと互いに素な整数とする。
mがρ(h)で割り切れる。⇔U_mが、U_ρ(h)で割り切れる。

証明

⇒は定理１より明らか。
逆を示す。

mをρ(h)で割り、商をq、余りをrとする。

m=ρ(h)*q+r　[0≦r＜ρ(h)]

mがρ(h)で割り切れない、つまり、r>0と仮定すると。

qが奇数のとき
式１より、
U_m=U_{{(q+1)/2}*ρ(h)}*V_{{(q-1)/2}*ρ(h)+r}-b^{{(qｰ1)/2}*ρ(h)+r}*U_ρ(h)-r

定理１より、b^{{(q-1)/2}*ρ(h)+r}*U_ρ(h)-rがhで割り切れる。
ところが、bはhと互いに素なので、U_ρ(h)-rがhで割り切れる。
しかし、0<ρ(h)-r<ρ(h)だから、この事は、ρ(h)の最小性に反する。

qが偶数のとき、
式１より、
U_m=U_{{q/2+1}*ρ(h)}*V_{{q/2-1}*ρ(h)+r}-b^{{q/2-1}*ρ(h)+r}*U_2*ρ(h)-r

定理１より、b^{(q/2-1)*ρ(h)+r}*U_2*ρ(h)-rが、hで割り切れる。

hはbと互いに素なので、U_2*ρ(h)-rが、hで割り切れる。

再び式１より、U_2*ρ(h)-r=U_ρ(h)*V_ρ(h)-r-b^ρ(h)-r*U_r

上と同様にして、U_rがhで割り切れることがわかる。

ところが、0＜ｒ＜ρ(h)だから、この事は、ρ(h)の最小性に反する。

qが奇数のときと偶数のとき、ともに矛盾していているので、
r=0、つまり、題意が言えた事になる。

証明終

定理３

自然数hが、数列U_n(nを1以上の自然数とする)のうちの、
あるU_nの値を割り切るとき、hとbは互いに素である。

証明

仮定より、数列U_nのうちの、U_tが、hで割り切れる。

hとbが共通の素因数pを持つと仮定する。

t≧2のとき、

U_t≡a*U_t-1-b*U_t-2≡a*U_t-1 (mod p)より、

0≡U_t≡a*U_t-1≡a^t-2≡･･･≡a^t-1*U₁≡a^t-1 (mod p)

つまり、a^t-1がpで割り切れる。

pは素数より、aとbが公約数pを持つ事になって、aとbが互いに素である事に反する。

t=1のとき、
U₁=aがhで割り切れるときは、明らかに、hとbは互いに素である。

いずれにしても、hとbは互いに素である。

証明終

問題の解答

まず、[m，n]はmとnを割り切るので、
定理１より、U_[m，n]はU_m、U_nを割り切る。

よって、U_[m，n]は、U_mとU_nの公約数である。
よって、U_mとU_nの最大公約数[U_m，U_n]の約数である。･･･○

また、h=[U_m，U_n]とおく。
hはU_m、U_nを割り切るので、定理３より、bとhは互いに素である。
よって、定理２より、ρ(h)はmとnを割り切る。

この事より、ρ(h)はmとnの公約数、
つまりρ(h)は[m，n]の約数であることがわかる。

ゆえに、定理１より、U_ρ(h)はU_[m，n]を割り切る。

明らかに、hはU_ρ(h)を割り切るから、hはU_[m，n]を割り切る事が分かる･･･●

○と●より、[U_m，U_n]=U_[m，n]

つまり、題意が示された事になる。

解答終

【コメント】

以前、フィボナッチ数列の問題の解答した事が思い出されます。

◆東京都　はにゃん さんからの解答。

F[1]=F[2]=1
F[n+2]=F[n+1]+F[n] (n=1,2,3,...)

の一般項は，

F[n]=

An-Bn A-B

---(*)である．

ただし，A=

1+ 2

, B=

1- 2

である．

いま，

f(n)=c(xⁿ-yⁿ) (n=1,2,3,...) ---(**)

とすると，f(n)がf(m)で割りきれるのは，nがmで割りきれる時のみである．

実際，nがmで割りきれる時，
X=x^m，Y=y^mとおけば，f(n)=X^n/m-Y^n/mは，X-Yで割りきれる．

一方，nがmで割りきれない時，X=x^m，Y=y^mとおけば，
f(n)=x^n-[n/m]*X^[n/m]-y^n-[n/m]*Y^[n/m]は，
X=Yとしたとき，f(n)=0とならないのでX-Yでは割り切れない．

（注：ここでX=Yとすると，x=yよりf(n)=0となって割り切れるのではないかと思うかもしれないが，
これはつまり非整数のn/mに対して，
f(n)=X^n/m-Y^n/m=0になると言っていると同じである．
ここで「割り切れる」とはあくまで有理数の範囲内なので，このような考え方は適用できない．
実際にn=10,m=4などとして状況を確かめるとわかるかもしれない．）

これより，nがmで割りきれる時のみF[n]はF[m]で割り切れる．

よって明らかに，一般のn,mに対してF[n]とF[m]の両方に割り切れるF[l]は，lがnとmの公約数になるときのみである．

以上より [F[n],F[m]]=F[[m,n]] が成り立つ．

　『フィボナッチ数列の性質 Part4』 へ

　数学の部屋へもどる