21
大学数学基礎解説
文献あり

フィボナッチ数列の1項飛ばし数列の漸化式を作ろう ~C-finite数列への誘い~

1107
0

イントロダクション

フィボナッチ数列(Fn)nN
F0=0,F1=1,Fn+2=Fn+1+Fn (for nN)
で定めます。

最初の方をいくつか見てみると次のようになっています。

n012345678
Fn01123581321

では問題です。

フィボナッチ数列の1個飛ばし数列(Gk)kN
Gk=F2k
で定めます。フィボナッチ数列のときと同様の漸化式を(Gk)kNに対して探してください。

いきなり答えを書くと
Gk+2=3Gk+1Gk
です。
たとえば上の表を見ると3G3G2=3F6F4=383=21=F8=G4なのでk=4では成り立っています。一般に成り立つことは数学的帰納法で示すことができます。

では、これはどう導出すればいいのか?1個飛ばしではなくて、任意に固定したmNについてmの倍数番目を取りだした数列だとどうか?一般の定数係数で斉次の線形漸化式で定義される数列に対して適用できる方法はあるのでしょうか?

こういったことを今から議論していきます。

導出

シフト演算というものを定義します。これは数列を受け取って数列を返す関数D
D:(xn)nN(xn+1)nN
と定義されます。つまり初項を捨てて、あとの項は1個左にずらすという写像です。

このシフト演算を使うとフィボナッチ数列の漸化式Fn+2=Fn+1+Fnは次のように表現できます。
(D2DI)(Fn)nN=0
ここで左辺のD2D二つの合成、Iは恒等変換、右辺の0は常に0な数列を表すことにします。

この式の両辺に左側から(D2+DI)を作用させます。
(D2+DI)(D2DI)(Fn)nN=0
左辺を計算してみると
((D2I)2D2)(Fn)nN=0

(D43D2+I)(Fn)nN=0
となります。
さて、これをもとの漸化式のような形で書き直すとどうなるでしょうか。次のようになります:
Fn+43Fn+2+Fn=0.
ここのn2kを代入すればほしい式そのものですね。これで導出できました。

考察と一般化

上の導出では(D2+DI)というものを天下りに与えて、計算するとうまくいっていました。これは何をやっているのでしょうか?

g(x)=x2x1と多項式を定義したときにg(D)(Fn)nN=0ですが、このときh(x)=x2+x1という別の多項式を与えたら、g(x)h(x)=x43x2+1と偶数次数の元だけ残ったことがポイントです。

つまり、多項式g(x)について多項式h(x),f(x)であって
g(x)h(x)=f(x2)
となることを見つけられたのがよかったのです。

このことを一般に述べると次です。

自然数m1を固定しましょう。定数係数で斉次の線形漸化式
an+r+cr1an+r1++c1an+1+c0an=0
が与えられます。今c0,,cr1は定数でc00とします。多項式g(x)
g(x)=cr1xr1++c1x+c0
で定めるとシフト演算Dを使って漸化式は
g(D)(an)nN=0
と書けます。
ここに多項式h(x),f(x)であって
g(x)h(x)=f(xm)
なるものが見つけられたとしたら
f(Dm)(an)nN=0
となるので
f(D)(amk)kN=0
となり、多項式fの係数で数列(amk)kNの漸化式が得られます。

多項式fの存在

さて、問題は与えられた多項式g(x)に対して
g(x)h(x)=f(xm)
となる多項式h(x),f(x)を求めることに帰着しました。これはいつでも存在するでしょうか。

考えている係数体が標数0という仮定のもとでYesです。

Kを標数0の体とする。g(x)K[x]を多項式とする。m1以上の自然数とする。
このときh(x),f(x)K[x]があって
degg(x)=degf(x)
かつ
g(x)h(x)=f(xm)
となる。

1の原始m乗根の一つをζとおき、ζを添加した体L=K(ζ)で考える。F(x)L[x]を次で定める。

F(x)=ξm=1g(ξx)
とおく。
ξ=1のときの因子を含んでいるので明らかにg(x)F(x)である。

F(x)K[x]を示す。Kが標数0なのでL/Kは分離拡大である。またζK上共役な元は1の原始m乗根なのでLに入っている。よってL/Kは正規拡大。したがってガロアの基本定理よりGal(L/K)の任意の元で不変なLの元全体の集合はKに等しい。
今多項式F(x)Gal(L/K)の元σを作用させると、σζをあるζk (kmと互いに素な整数)に写すものなので、F(x)σを作用させた多項式Fσ(x)を考えると
Fσ(x)=(ξm=1g(ξx))σ=(0i<mg(ζix))σ=(0i<mg(σ(ζ)ix))=(0i<mg(ζkix))=(0j<mg(ζjx))=F(x)
となり不変。よって、F(x)K[x]である。

また、任意の1m乗根ξについて
F(ξx)=ξm=1g(ξξx)=ξm=1g(ξx)=F(x)
なことからF(x)mの倍数の次数の項しかないことが分かる (標数0なことを再び使った)。

そこでf(xm)=F(x)となる多項式f(x)がある。F(x)K[x]なのでf(x)K[x]である。

degF(x)=mdegg(x)を考えると、degg(x)=degf(x)が分かる。

フィボナッチ数列の2項飛ばし、3項飛ばし, etc

2項飛ばし

さて一般的な方法が分かったのでフィボナッチ数列の2項飛ばしや3項飛ばしなどに応用してみましょう。

まずは2項飛ばし (m=3)です。

g(x)=x2x1に対して
F(x)=g(x)g(ωx)g(ω2x)
を計算しましょう。ここでω1の原始3乗根です。

.........

F(x)=x64x31
と出ました。

よって
f(x)=x24x1

F3(n+2)=4F3(n+1)+F3n
です!

3項飛ばし

次は3項飛ばし (m=4)です。

F(x)=g(x)g(ix)g(x)g(ix)を計算しましょう。

.........

F(x)=x87x4+1
と出ました。
よって
f(x)=x27x+1
で、
F4(n+2)=7F4(n+1)F4n
です。

4項飛ばし

次は4項飛ばし (m=5)です。しんどいのでMathematicaにやってもらいました。

f(x)=x211x51
で、
F5(n+2)=11F5(n+1)+F5n
です。

5項飛ばし

次は5項飛ばし (m=6)です。同じくMathematicaで。

f(x)=x218x5+1
で、
F6(n+2)=18F6(n+1)F6n
です。

mを動かしたときに何か係数に規則性があるのか…?という疑いも生じてきますが、この辺で終わりにします。

まとめ

定数係数で斉次の線形漸化式を満たす数列 (こういうのをC-finite sequenceというそうです)の固定した自然数の倍数番目の項を取り出した数列の漸化式を与える方法を紹介しました。それをフィボナッチ数列に応用してみました。

この話は参考文献のThe Concrete Tetrahedronの定理4.2がもとになっています。C-finite sequenceの固定した自然数の倍数番目の項を取り出した数列もまたC-finite sequenceとなることが書かれているんですが、証明は読者の演習問題となっています。そこで考えてみたという次第です。

まだ読んでいる途中なのですが、なかなか面白い本です。

追記 (2021/7/4)

以上を見ると

  • Fn+2Fn+1Fn=0
  • Fn+43Fn+2+Fn=0
  • Fn+64Fn+3Fn=0
  • Fn+87Fn+4+Fn=0
  • Fn+1011Fn+5Fn=0
  • Fn+1218Fn+6+Fn=0
    ですね。規則性が気になります。最後の項は(1)mFnでしょうね。真ん中の項の係数はどうでしょうか。OEISに投げてみました。

OEIS OEIS

なんと、真ん中の項の係数はリュカ数列の模様です!つまり、次の式ということです。

Fn+2mLmFn+m+(1)mFn=0

これの証明はたとえば以下のようにすればいいでしょう。

方程式x2x1=0の解をφ1=(1+5)/2,φ2=(15)/2とします。解と係数の関係よりφ1φ2=1です。多項式f(x)=x2Lmx+(1)m(x2x1)f(xm)を満たすことを言えばよいでしょう。そのためにはf(φ1m)=f(φ2m)=0を言えばいいです。これは言えて、実際、たとえばφ1の方は
f(φ1m)=(φ1)2mLm(φ1)m+(1)m=(φ1)2m((φ1)m+(φ2)m)(φ1)m+(1)m=(φ1φ2)m+(1)m=0
なのでOKです。ここにリュカ数列の一般項Lm=(φ1)m+(φ2)mを使いました。

追記2 (2021/7/10) 正標数の場合

定理1は標数0の場合を扱いましたが、実は正標数でも成り立ちます。この節は @waidotto さんの助言をもとに執筆しました。

Kを体とする。g(x)K[x]を多項式とする。m1以上の自然数とする。
このときh(x),f(x)K[x]があって
degg(x)=degf(x)
かつ
g(x)h(x)=f(xm)
となる。

標数0の場合は証明したので、標数p>0の場合を示す。m=peqqpと互いに素とする。
g(x)=cnxn++c1x+c0
と表したときに、
g(x)=(cn)pexn++(c1)pex+(c0)pe
とおく。すると、フロベニウス写像xxpの準同型性より、
g(x)pe=g(xpe)
が分かる。

今、原始q乗根ζを考えて、L=K(ζ)とおく。pqが互いに素なのでこれは考えることができる。定理1の証明と同様にF(x)=0i<qg(ζix)を考えよう。

L/Kは分離拡大である。なぜなら、多項式xq1はその微分qxq1と互いに素だから分離多項式である。よってその約元であるζの最小多項式も分離多項式であるからである。よって定理1の証明と同様にF(x)K[x]が導かれる。

F(x)=f(xq)となるf(x)K[x]があることも同様にわかる。ただしこの証明ではqで割る操作が必要になるのだが、pqが互いに素なおかげで可能なことに注意しておく。

したがって、degf(x)=degg(x)=degg(x)かつg(x)f(x)となり証明が終わる。
実際、g(x)g(x)pe=g(xpe)F(xpe)=f(xm)である。

参考文献

[1]
Manuel Kauers, Peter Paule, The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates, Texts and Monographs in Symbolic Computation, Springer, Vienna, 2011
投稿日:202173
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

でぃぐ
でぃぐ
58
3735

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. イントロダクション
  2. 導出
  3. 考察と一般化
  4. 多項式fの存在
  5. フィボナッチ数列の2項飛ばし、3項飛ばし, etc
  6. 2項飛ばし
  7. 3項飛ばし
  8. 4項飛ばし
  9. 5項飛ばし
  10. まとめ
  11. 追記 (2021/7/4)
  12. 追記2 (2021/7/10) 正標数の場合
  13. 参考文献