計算代数を駆使して （一般化）
フィボナッチ数列の一般項を求める
Hiromi ISHII

2022/03/06
Tsukuba Compter Mathematics Seminar 2022導入
導入話題：一般化 Fibonacci 数列を純計算代数的に解く
Fibonacci 数列： 𝑓 = 0, 𝑓 = 1, 𝑓 + = 𝑓 + 𝑓 +0, 1, 1, 2, 3, 5, 8, …
線型隣接三項間漸化式で定まる数列の代表的な例
定義 1

導入

1/36

線型隣接多項間漸化式の第 𝑛項の求め方
愚直に 𝑛 回繰り返して解く
ありきたりな方法：行列を使って求める
既知の一般項を使う
一般項：一般の 𝑎 を 𝑛 についての閉じた式で表したもの
Fibonacci 数列の一般項は以下で与えられることが知られている：
𝐹 =151+ 52−1− 52

一般項はどう求める？

導入2/36行列の方法：ありきたりな方法から
𝑁 + 1 - 項間漸化式は以下のように行列を使って表せる：
𝑎 +𝑎 +⋮𝑎−=𝑐 −10⋮0𝑐 −01⋮0⋯⋯⋯⋱⋯𝑐00⋮1𝑐00⋮0𝑎 +𝑎 +−−⋮𝑎1

行列を 𝐴 と置けば，𝑎 を求めるには 𝐴 を求めればよい
𝐴 の固有値・固有ベクトルを求める問題に帰着

導入

3/36

完

完ではない一般項が求めたいのよ
記号的に固有値は求まる（適切な代数拡大体で）そこから劣決定な連立方程式を解けば固有ベクトルがわかる（記号的にできるの？）
𝑄− 𝐴 𝑄 が対角になるので， これを使って式を解いて 1- 行目をみれば一般項はわかる
線型代数に甘えるなもっと面白い解き方はないのか？
あります（計算量は無視して）

導入

6/36

母関数法による Fibonacci 数列の一般項導出 (1)以下の冪級数 𝐹 𝑋 を数列 𝑎<の母関数と呼ぶ：

𝐹 𝑋 = 𝑎 +𝑎 𝑋+𝑎 𝑋 +⋯+𝑎 𝑋 +⋯単に数列の横に 𝑋 たちを並べただけでは？
ところが冪級数を「それっぽく」扱うといつの間にか一般項がわかる（！）
方針：各項の関係を使い，𝐹 𝑋 を閉じた有理式にする．
𝑋 𝐹 𝑋 =𝑓 𝑋 +𝑓 𝑋 +⋯𝑋𝐹 𝑋 = 𝑓 𝑋+𝑓 𝑋 +𝑓 𝑋 +⋯∴ 𝑋 +𝑋 𝐹 𝑋 = 𝑓 𝑋+𝑓 𝑋 +𝑓 𝑋 +⋯導入=−+7/36

母関数法による Fibonacci 数列の一般項導出 (2)変形の続き：右辺を整理すると，
𝑋 +𝑋 𝐹 𝑋 = 𝐹 𝑋 −𝑓 − 𝑓 −𝑓 𝑋

(1)

𝐹 𝑋 を移項して，
𝑋 +𝑋−1 𝐹 𝑋 = − 𝑓 + 𝑓 −𝑓 𝑋= −𝑋∴𝐹 𝑋 =−𝐹 𝑋 を移項
𝑓 = 0, 𝑓 = 1より

𝑋𝑋 +𝑋−1

導入𝑋 + 𝑋 − 1で両辺を割る

8/36

母関数法による Fibonacci 数列の一般項導出 (3)
ここで多項式 𝑋 + 𝑋 − 1 の根を 𝛾, 𝛾̅ とおいて部分分数分解をして，
𝑋𝑋
11𝐹 𝑋 =−=−𝛾 − 𝑋 𝛾̅ − 𝑋𝛾 − 𝛾̅ 𝛾 − 𝑋 𝛾̅ − 𝑋
等比級数の公式より，
1
1= ⋅𝑎−𝑋
𝑎1𝑋
1−𝑎=1
𝑋=𝑎 < 𝑎<だから，𝐹 𝑋 =1𝛾 − 𝛾̅ < <11−𝑋𝛾𝛾̅𝑋𝑎 +母関数法による Fibonacci 数列の一般項導出 (4)𝑋 + 𝑋 − 1 の二つの根は−1± 5であることに気を付ければ，
2111𝑓 =−𝛾 − 𝛾̅ 𝛾𝛾̅=151+ 52−1− 52となり，これは先に掲げた式に一致する．
なんでこれでいいのか？

導入

10/36

形式的冪級数環による正当化
形式的冪級数環による正当化

母関数法の正当化『数学ガール』[1] 等に（正当化なしで）紹介されている十年以上前に読んで「カッコイイ！」となった

形式的冪級数環 𝑅 𝑋 の環構造を使えば普通に正当化できる
定義 2 (形式的冪級数環)

形式的冪級数環による正当化

11/36

形式的冪級数環は環
定理 3

形式的冪級数環による正当化12/36

記号の約束記法 5

形式的冪級数環による正当化13/36

母関数の定数倍・重ね合わせの正当化
補題 6 (冪によるシフト)

形式的冪級数環による正当化

14/36

形式的冪級数環の可逆元
定理 7 (形式的冪級数環の可逆元)

形式的冪級数環による正当化

15/36

連分数展開は？
通分などの操作は，分母たちが可逆なら任意の可換環で成立
母関数による Fibonacci 数列の解法は以下まで正当化出来る：
𝑋11𝐹 𝑋 =−𝛾 − 𝛾̅ 𝛾 − 𝑋 𝛾̅ − 𝑋
また，定数倍も明らかに分配則を満たす：
定理 8 (スカラー倍)

形式的冪級数環による正当化

16/36

等比級数公式「等比級数の公式」は 𝑅 𝑋 でも確かに成り立つ！
系 9 (等比級数の公式)

形式的冪級数環による正当化

17/36

Fibonacci 数列の母関数解法まとめ
Fibonacci 数列 𝑓<の一般項は以下の手順で求まった(a) 母関数 𝐹 𝑋 = 𝑓 + 𝑓 𝑋 + ⋯ + 𝑓 𝑋 + ⋯ を考える
(b) 漸化式を使い，𝐹 𝑋 = −𝑋/ 𝑋 + 𝑋 − 1 と表す．
これは形式的冪級数環 𝑅 𝑋 が実際に可換環であり，分母の多項式 𝑋 + 𝑋 − 1 が 𝑅 𝑋 で可逆であることから可能(d) 分母を因数分解し，一次式に部分分数分解する．
(e) 等比級数公式を線型に重ね合わせて，第 𝑛 項の式を導く．

形式的冪級数環による正当化

18/36

多項への一般化
多項への一般化𝑁 + 1 - 項間漸化式への一般化
母関数法を 𝑁 + 1 - 項間に一般化，計算機に解かせたい
可能な限り一般的な係数環で解けるようにしたい
ネタバレ：因数分解が計算可能な整域なら OK必要なもの：(a) 一般の場合でも使える母関数 𝐹 𝑋 の有理式表現（やるだけ）(b) 有理式の部分分数分解（既知）(i) 更に分母の一次式への因数分解が必要（ちょっと工夫が必要）(c) 無限和で表し重ね合せ：等比級数の公式の冪乗版が必要（簡単）

多項への一般化19/36

有理式表現𝑐 − 𝑋 , 𝑐 − 𝑋 , …, 𝑐 𝑋 を 𝐹 𝑋 に掛け足し合わせる
更に，定数項の分の帳尻を 𝑐/ 1 − 𝑋 で合わせて整理して：
𝑐 𝑋 − −1 𝐹 𝑋 = 𝑔 𝑋 −<𝑎 𝑋 +<where 𝑔 𝑋 =𝑐𝑋,
𝑋−1(4)

𝑐 − ++ 𝑎𝑋 .
< <左辺の 𝐹 𝑋 の係数の定数項は可逆
𝐹 𝑋 以外の項は全て有限次なので，𝐹 𝑋 は有理式で表せる

多項への一般化20/36

有理式の部分分数分解
定義 10

多項への一般化21/36

部分分数分解の存在と一意性：第一ステップ
係数が体の時を考える（整域なら分数体や擬剰余を考える）
補題 11

部分分数分解の存在と一意性：第二ステップ
あとは先程の結果を 𝑔 - 進展開してやればよい．
整数を 𝑝- 進展開するように，𝑓̂ を繰り返し 𝑔 で剰余をとれば，
𝑓̂ = 𝑓 𝑔 − + ⋯ + 𝑓−𝑔 +𝑓deg 𝑓< deg 𝑔と表示でき，𝑔 で割れば所要のもの．
Modern Computer Algebra [3] などでも紹介されている方法部分分数展開は 𝑔 が与えられて初めて定まるので，母関数の分解には，分母の因数分解があればよい

多項への一般化23/36

因数分解をどうするか？
有限体や有理数体， 整数環上の因数分解の方法は既知 （ここではやらない）
Modern Computer Algebra [3] や『計算機代数の基礎理論』 [4] 参照

武器が等比級数公式だけなので一次式の積しか扱えない！
代数閉包を取ってもよいが，そこでの因数分解が必要

今回の方針(a) まずは係数環やその分数体上で因数分解(b) 高次因子は剰余環を繰り返し取り，分解体上で扱う

多項への一般化24/36

分解体での計算
𝑓 𝑋 を平方因子を含まないモニックな既約多項式とする
𝑅 𝑋 /𝑓 𝑋 は 𝑓 𝑋 の根を少なくとも一つ含む
deg 𝑓 = 1 なら元の 𝑅 と同型
deg 𝑓 = 2 なら，𝑅 𝑋 /𝑓 は 𝑓 𝑋 の二つの根を全て含む
一つは 𝜉 = 𝑋 ， もう一つは因数定理より 𝑓/ 𝑋 − 𝜉 が知ってる （二次方程式の解と係数の関係）

deg 𝑓 > 2 の場合 𝑓/ 𝑋 − 𝜉 に対して以下同文同型にはなるが，三次以上の場合でも複数根が付与される場合はないか？

𝑓 にしか興味ないので拡大体での一般的な因数分解は不要
多項への一般化25/36

等比級数公式の冪乗版 (1)母関数 𝐹 𝑋 をこんな感じで一次式の冪乗和に分解できた：
𝐹 𝑋 =𝑔 𝑋 +

ℎ 𝑋
𝑋−𝜉

𝑑=𝑔 𝑋 +≤

但し，𝑔 𝑋 ∈ 𝑅 𝑋 , 𝑑⋯ 𝑋−𝜉

≤ ≤𝑋−𝜉

（分母因数分解）（部分分数分解）∈ 𝑅．

Fibonacci の場合と違って 𝑋 − 𝜉−の項が出てきうる．

多項への一般化26/36

等比級数公式の冪乗版（面倒だが）簡単な帰納法で次が示せる：
補題 12 (等比級数公式，冪乗版)

多項への一般化27/36

例： 𝔽 上の定数項つき Fibonacci (1)次の定数項つきの Fibonacci 数列を有限体 𝔽 上で解いてみる：
𝑎 = 0, 𝑎 = 1, 𝑎 + = 𝑎 + 𝑎 + + 2
まず母関数の公式 (4) に各値を代入して整理すると，
𝑋 +𝑋
𝐹 𝑋 =
𝑋 − 2𝑋 + 1
分母に有限体上での因数分解を施して，
𝐹 𝑋 =

𝑋 +𝑋
𝑋−1 𝑋−2多項への一般化

28/36

例： 𝔽 上の定数項つき Fibonacci (2)部分分数分解をすると：
𝐹 𝑋 =

2
41++
𝑋−1 𝑋−2𝑋−2

これに式 (5) を適用して𝐹 𝑋 =−2𝑋 +<−<

42+𝑋 +3+3 + +4 𝑛+1 3 𝑋=<よって一般項は 𝑎 = 3 + 3 + + 4 𝑛 + 1 3 ．

<𝑛+1𝑋+2

ℚ上のトリボナッチ数列の一般項 (1)高次の分解体が必要で 𝑁 + 1 - 項が解ける例として以下で定まるトリボナッチ数列を考える：
𝑡 = 0, 𝑡 = 1, 𝑡 = 1, 𝑡 + = 𝑡 + 𝑡 + + 𝑡 +計算機によれば母関数は𝑇 𝑋 =−𝑋
𝑋 +𝑋 +𝑋−1

大人しめだが，これの一般項はものすごいことになる

多項への一般化30/36

ℚ上のトリボナッチ数列の一般項 (1)
ものすごい一般項が出る𝜉
73𝑡 =+ 𝜉+
112222𝜉 +𝜉+1+ −25𝜉
1𝜉+ 𝜁−+
1122
11 22+ −352
𝜉− 𝜁−𝜉𝜁222211−𝜉𝜁 + −𝜉 − 𝜉

ただし 𝜉 + 𝜉 + 𝜉 − 1 = 0, 𝜁 + 𝜉 + 1 𝜁 + 𝜉 + 𝜉 + 1 = 0．

多項への一般化31/36

変な数列 over 𝔽𝔽

上で 𝑎 = 0, 𝑎 = 0, 𝑎 = 0, 𝑎 = 1 として
𝑎 + = 4𝑎 + 3𝑎 + + 2𝑎 + + 𝑎 + + 1→ 0, 0, 0, 1, 2, 5, 13, 0, 16, 8, 8, 5, 8, 7, 3, …

一般項は𝑎 = 13 ⋅ 6 + 15 + 3𝜉 + 2𝜉 + 15 5𝜉 + 6𝜉 + 12+ 7𝜉 + 12𝜁 + 14𝜉 + 1 12𝜉𝜁 + 12𝜉 + 11𝜉+ 8𝜉 + 5𝜁 + 7 5𝜉𝜁
但し 𝜉 + 8𝜉 + 16𝜉 + 10 = 0, 𝜁 + 𝜉 + 8 𝜁 + 𝜉 + 8𝜉 + 16 = 0．

まとめ
母関数の有理式表現を用い，因数分解が計算可能な整域上で一般化 Fibonacci 数列の一般項を計算機に求めさせた．
実装 [5] と冪級数の性質の形式的証明 [6] は GitHub にあり

形式的冪級数環 𝑅 𝑋 の代数構造を使うと完全に正当化可能計算の過程では計算代数の色々な要素が顔を出す(a) 多項式の因数分解（整数環・有理数体・有限体上）(b) 剰余環での計算（多項式剰余）Gröbner までは不要(c) 部分分数分解

多項への一般化

33/36

参考文献
[1] 結城浩 , “数学ガール ,” SB クリエイティブ , June 2007, vol. 1, ISBN: 9784797341379.
[2] H. Basold et al., “Newton Series, Coinductively: A COmparative Study of Composition,”
Mathematical Structures in Computer Science, pp. 1–1, 2019, doi:10.1017/S0960129517000159.
[3] J. v. z. Gathen and J. Gerhard, “Modern Computer Algebra,” Third Edition ed., Cambridge
University Press, 2013, ISBN: 978-1-107-03903-2.
[4] 長坂 耕作 et al., “計算機代数の基礎理論 ,” 共立出版 , 3 2019, ISBN: 978-4-320-11373-2.

[5] Hiromi Ishii, Algebra.Ring.LinearRecurrentSequence module, 2022. URL: https://github.com/konn/computational-algebra/blob/6e87b1eb9/halgpartial-fraction/src/Algebra/Ring/LinearRecurrentSequence.hs .
[6] Hiromi Ishii, laurent , 2022. URL: https://github.com/konn/laurent .

御清聴
ありがとうございましたAny Questions?
母関数の有理式表現を用い，因数分解が計算可能な整域上で一般化 Fibonacci 数列の一般項を計算機に求めさせた．
実装 [5] と冪級数の性質の形式的証明 [6] は GitHub にあり形式的冪級数環 𝑅 𝑋 の代数構造を使うと完全に正当化可能計算の過程では計算代数の色々な要素が顔を出す(a) 多項式の因数分解（整数環・有理数体・有限体上）(b) 剰余環での計算（多項式剰余）Gröbner までは不要(c) 部分分数分解

多項への一般化36/36