メモ（数論11）: 不思議っち☆フィボナッチ

チラ裏　＞　数論 i　＞　メモ11

「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。誤字脱字・間違いがあるかもしれません。

• 2022-10-30　不思議っち☆フィボナッチ　第14項377が14の倍数より1小さい…
• 2022-11-01　不思議っち☆フィボナッチ（第2話）　Binet の公式
• 2022-11-03　不思議っち☆フィボナッチ（第3話）　一年生の夢
• 2022-11-05　不思議っち☆フィボナッチ（第4話）　夢のもつれ
• 2022-11-10　不思議っち☆フィボナッチ（第5話）　星のらせん階段
• 2022-11-12　不思議っち☆フィボナッチ（最終回）　星のコンペイトウ
• 2022-11-13　フィボナッチ数列の加法定理　F_a+b = ？
• 2022-11-14　フィボナッチ数列の加法定理（その2）　①の証明
• 2022-11-17　フィボナッチ数列の加法定理（その3）　F₅₀を筆算しよう
• 2022-11-21　フィボナッチ数列の加法定理（その4）　②の証明
• 2022-11-23　シャア専用フィボナッチ公式　通常の3倍ｗ
• 2022-11-25　カッシーニの隙間をたたけ！　古典パズルを越えて
• 2022-11-27　土星の輪っかとフィボナッチ　知られざる Lucas の隙間
• 2022-11-30　フィボナッチ数の3乗　加法定理の直接証明
• 2022-12-02　フィボナッチ数の4乗・5乗など　Hunter–Carlitz の恒等式
• 2022-12-06　ビネの公式の一般化　第2部・最終回

2022-10-30　不思議っち☆フィボナッチ　第14項377が14の倍数より1小さい…

#数論　#フィボナッチ

この数列の次の項は何でしょう？
　　1, 1, 2, 3, 5, 8, 13, 21, 34, …
　　1, 3, 4, 7, 11, 18, 29, 47, 76, …

フィボナッチ数列で遊んでたら、ちょっと発見があった！　「発見」といっても、昔から知られてる事実なんだろうけど…。次の表は、左から自然数 n、フィボナッチ数列の第 n 項（F_n とする）、そしてその項を n で割った余り（r とする）。

n : Fn : r
1 : 1 : 0
2 : 1 : 1[*/**]
3 : 2 : 2[**]
4 : 3 : 3[**]
5 : 5 : 0#
6 : 8 : 2
7 : 13 : 6**
8 : 21 : 5
9 : 34 : 7
10 : 55 : 5#
11 : 89 : 1*
12 : 144 : 0
13 : 233 : 12**
14 : 377 : 13**
15 : 610 : 10#
16 : 987 : 11
17 : 1597 : 16**
18 : 2584 : 10
19 : 4181 : 1*
20 : 6765 : 5#
21 : 10946 : 5
22 : 17711 : 1*

第一に、n が5の倍数のとき、F_n も5の倍数、従って r も5の倍数（#印）。第二に、n が 1 or 9 で終わる素数（末尾の桁が 1 or 9 という意味）か、またはそのような素数の2倍のとき、r は 1 になる（*印）――言い換えると F_n は n の倍数より1大きい。第三に、n が 3 or 7 で終わる素数か、またはそのような素数の2倍のとき（ただし 6 は例外）、r は n−1 になる（**印）――言い換えると F_n は n の倍数より1小さい。

第二・第三については、n が7以上なら逆も成り立つようだが、逆についてはまだちゃんと調べてない。

〔追記〕　逆は成り立たない。第二・第三の命題の逆について、最小の奇数の反例（フィボナッチ擬素数）は、それぞれ n = 323 = 17 × 19 と 5777 = 53 × 109。合成数だが F_n ≡ ±1 (mod n) を満たす。（2022年10月31日）

第一の観察は、フィボナッチ数列の基本性質だろうし、第二・第三の観察についても、n が素数の場合については、一般項の形（次回）から mod 5 従って mod 10 の話になり、末尾の数字によって挙動が変わるのだろう。けど、n が「素数の2倍」のときの挙動は、Binet の式からは見通せない。この部分が「発見」。

一体全体これはどーゆー現象なのか？？？　無い知恵を絞って考えた結果、まず Lucas 数列 L_n について同様のことをすると、n が素数のとき r が 1 になる:

n : Ln : r
1 : 1 : 0
2 : 3 : 1*
3 : 4 : 1*
4 : 7 : 3
5 : 11 : 1*
6 : 18 : 0
7 : 29 : 1*
8 : 47 : 7
9 : 76 : 4
10 : 123 : 3
11 : 199 : 1*

p が素数のとき、L_p ≡ 1 (mod p) なので:
　　F_2p = F_pL_p ≡ F_p (mod p)
この左端の等号は p が素数でなくても成り立つ（後述の【14】）。

だから F_2p ≡ F_p ≡ ±1 (mod p) が奇数なら F_2p ≡ ±1 (mod 2p) も成り立つ。

数値例。
　　p = 3, n = 6 のとき★
　　　8 = F₆ = F₃L₃ = 2 × 4 ≡ 2 (mod 3)　なぜなら 4 ≡ 1
　　p = 5, n = 10 のとき★
　　　55 = F₁₀ = F₅L₅ = 5 × 11 ≡ 5 (mod 5)　なぜなら 11 ≡ 1
　　p = 7, n = 14 のとき
　　　377 = F₁₄ = F₇L₇ = 13 × 29 ≡ 13 (mod 7)　なぜなら 29 ≡ 1
　　p = 11, n = 22 のとき
　　　17711 = F₂₂ = F₁₁L₁₁ = 89 × 199 ≡ 89 (mod 11)　なぜなら 199 ≡ 1
　　etc.

最初の2個（★印）は、結論的には例外だが、この合同式の部分については同じように振る舞う。F₆ が例外になるのは、奇数でないから。F₃ を除けば、素数番目の Fibonacci 数は奇数、そのため F₆ だけはパターンから外れる。F₁₀ が例外になるのは、5の倍数番目の Fibonacci 数は別系列だから。

簡単過ぎず、難し過ぎず、なかなか面白そうだ。（下に続く）

2022-11-01　不思議っち☆フィボナッチ（第2話）　Binet の公式

#数論　#フィボナッチ

次のような数列の第50項――
　　1, 1, 2, 3, 5, 8, 13, 21, 34, …
　　1, 3, 4, 7, 11, 18, 29, 47, 76, …
第3項から地道に順々に計算してけば求まるが、順々に計算せず、一般項を直接求める式を作るには、どうすればいいのだろう？

【1】　フィボナッチ数列のある項と直前の項の比は、黄金比 (1 + √5)/2 = 1.61803… に近づいていく。例えば、F₉ = 34 は F₈ = 21 の約1.619倍。多少の誤差を無視すれば、フィボナッチ数列は「項が次々に (1 + √5)/2 倍になっていく等比数列」に似ている（理由は下記【3】）。

見方を変えて、もし本物の等比数列が「フィボナッチ数列のような性質」（ある項は直前の2項の和）を持つとしたら、どんな場合だろうか？

最初の項（第1項）が b で、項の値が次々に x 倍になっていく等比数列は、
　　b, bx, bx², bx³, …
と書けるが、ここでは話をシンプルにするため b = x として
　　x, x², x³, x⁴, …
という数列を考える。つまり第n項 A_n の値を xⁿ とし、さらに「n が 3 以上のとき A_n は直前の2項の和 A_n−2 + A_n−1 に等しい」というフィボナッチっぽい性質を仮定しよう。

くだらない例として x = 0 が考えられる:
　　0, 0, 0, 0, …
このくだらない数列（全部の項が 0）では、確かに（第3項以降について）各項が直前の2項の和になっている。このつまらないケースを除外した上で（つまり x ≠ 0 として）、x が満たすべき条件…
　　xⁿ = xⁿ⁻² + xⁿ⁻¹
…について、各項を xⁿ⁻² で割ると（xⁿ⁻² ≠ 0 なので、この割り算は許される）:
　　x² = 1 + x　つまり　x² − x − 1 = 0
この2次方程式を解くと x = (1 ± √5)/2。

複号でプラスを選んだ解を u = (1 + √5)/2 としよう。これは黄金比――よく φ（ファイ）とか α（アルファ）で表される数。他方の解を v = (1 − √5)/2 としておく（一般的には ψ（プサイ）や β で表される黄金比の相棒）。

予定通りになってるか、x = u について最初の方を確かめてみると…

• A₁ = u¹ = (1 + √5)/2
• A₂ = u² = [(1 + √5)/2]² = (1 + 2√5 + 5)/4 = (3 + √5)/2
• A₃ = u³ = u² × u = (3 + √5)/2 × (1 + √5)/2
  = (3 + 3√5 + √5 + 5)/4 = (4 + 2√5)/2
• A₄ = u⁴ = u³ × u = (4 + 2√5)/2 × (1 + √5)/2
  = (2 + 2√5 + √5 + 5)/2 = (7 + 3√5)/2

A₃ = (4 + 2√5)/2 は、ちゃんと直前の2項 A₁ = (1 + √5)/2 と A₂ = (3 + √5)/2 の和になってる（A₃ は 2 で約分できるが、パターンが分かりやすいように、あえて分母を 2 にしてある）。A₄ も、同様に直前の2項の和。どうやら、うまくいったようだ。念のため、あと2項くらい調べてみる…

• A₅ = u⁵ = u⁴ × u = (7 + 3√5)/2 × (1 + √5)/2
  = (7 + 7√5 + 3√5 + 15)/4 = (11 + 5√5)/2
• A₆ = u⁶ = u⁵ × u = (11 + 5√5)/2 × (1 + √5)/2
  = (11 + 11√5 + 5√5 + 25)/4 = (18 + 8√5)/2

ちゃんと直前の2項の和になる。u の代わりに v を使った場合、u に含まれる √5 の部分が −√5 に変わるだけで、それが2乗されて整数 5 になる部分は (−√5)² でも同じなので、分子の「整数部分」は変わらない; 分子の √5 の前にある数の符号だけが、プラスからマイナスに変わる。vⁿ によって定義される数列を B_n とすると…
　　B₁ = v¹ = (1 − √5)/2, B₂ = v² = (3 − √5)/2,
　　B₃ = v³ = (4 − 2√5)/2, B₄ = v⁴ = (7 − 3√5)/2, etc.
やはりフィボナッチ数列と似た性質を持つ（B₁ + B₂ = B₃ など）。

【2】　A_n = uⁿ について（あるいは B_n = vⁿ について）上記の分子の整数部分（前半の項）を見ると 1, 3, 4, 7, 11, 18, … と Lucas（ルュカ）数列になっている。√5 の係数は 1, 1, 2, 3, 5, 8, … と Fibonacci（フィボナッチ）数列になっている。A_n の第3項以降は直前の2項の和で、直前の2項を足すときには「分子の整数同士」「√5 の係数同士」がそれぞれ足し合わされるのだから、この調子で、どこまでも分子の「整数部分」は Lucas 数列になり、√5 の「係数部分」は Fibonacci 数列になるだろう。

この「整数部分」を取り出して、Lucas 数列の一般項の公式を得るには、単に A_n = uⁿ と B_n = vⁿ を足し合わせればいい。例えば…
　　A₄ + B₄ = (7 + 3√5)/2 + (7 − 3√5)/2 = 7
…は、Lucas 数列の第4項 L₄ に当たる。足し算の代わりに引き算すれば、次の例のようになる:
　　A₄ − B₄ = (7 + 3√5)/2 − (7 − 3√5)/2 = 3√5
これは Fibonacci 数列の第4項 F₄ = 3 の √5 倍だから、√5 で割れば F₄ = 3 が得られる。一般に:

de Moivre–Euler–Binet（ビネ）の公式
　　ルュカ数列の第n項　L_n = uⁿ + vⁿ
　　フィボナッチ数列の第n項　F_n = (uⁿ − vⁿ) / √5
　ここで u = (1 + √5)/2 は黄金比、v = (1 − √5)/2 はその相棒

「整数の数列なのに、無理数によって記述される」ってのが奇妙かもしれないが、これも、数の世界の奥深さだろう。不思議っち！

これらの式は、実際の計算には必ずしも便利ではない（例えば第50項を知りたい場合）。理論上の研究には非常に役立つ。1710年代に de Moivre によって発見されたらしい。1760年代、Euler も本質的に同じ式を発表した:
http://eulerarchive.maa.org/backup/E326.html
1843年に Jacques Binet によって記述されたことから（下記563ページ）、一般には「Binet の公式」と呼ばれる。
https://archive.org/details/comptesrendusheb17acad
Pell 方程式の Pell や、Bézout の定理の Bézout もそうだが、数学用語は結構いいかげん…。のべっち！

【3】　公式が成り立つことは分かったが、念のため、帰納法を使って証明しておく。「帰納法を使って証明」だなんて学校くさいというか、この文脈では、ばかばかしい感じだが…。前記の数値を使い、最初の2個について直接計算:
　　L₁ = u¹ + v¹ = (1 + √5)/2 + (1 − √5)/2 = 1
　　L₂ = u² + v² = (3 + √5)/2 + (3 − √5)/2 = 3
　　F₁ = (u¹ − v¹)/√5 = [(1 + √5)/2 − (1 − √5)/2]/√5 = 1
　　F₂ = (u² − v²)/√5 = [(3 + √5)/2 − (3 − √5)/2]/√5 = 1

u, v は x² − x − 1 = 0 つまり x² = 1 + x の解だから、次が成立:
　　1 + u = u², 1 + v = v²　　‥‥④

今 n−2, n−1 に対して公式が正しいとすると（n ≥ 3）:
　　L_n = L_n−2 + L_n−1 = uⁿ⁻² + vⁿ⁻² + uⁿ⁻¹ + vⁿ⁻¹
　　= uⁿ⁻²(1 + u) + vⁿ⁻²(1 + v)　　［ここで④を使って］
　　= uⁿ⁻²(u²) + vⁿ⁻²(v²) = uⁿ + vⁿ
同様に F_n = F_n−2 + F_n−1 = (uⁿ⁻² − vⁿ⁻² + uⁿ⁻¹ − vⁿ⁻¹)/√5
　　= [uⁿ⁻²(1 + u) − vⁿ⁻²(1 + v)]/√5 = (uⁿ − vⁿ)/√5
従って n に対しても公式は正しい。□

v = (1 − √5)/2 = −0.618… は絶対値1未満の数なので、n が大きいとき、vⁿ の絶対値は非常に小さい。一方、黄金比 u = 1.618… は1より大きい数なので、n が大きくなるとき uⁿ は限りなく大きくなる。例えば n = 15 のとき v¹⁵ の絶対値は 0.001 未満だが、u¹⁵ は約1364。結局、F_n の式において、uⁿ に比べると vⁿ はほとんど無視できるくらい小さい影響しか持たず、
　　近似的に　F_n ≈ (uⁿ) / √5
…が成り立つ。「大ざっぱに、項が次々と u 倍になる」という最初の観察も、そうなって当然。

【4】　Binet の公式について、上記の導出は（簡単で分かりやすいかもしれないが）行き当たりばったりだった。ある等比数列を考えたら、その表現の一部として、たまたま望む数列が出てきたので、それを取り出しただけ…。

次のようにすれば、行き当たりばったりでなく、一般項の式をきっちり構成できる。まず uⁿ の定数倍 cuⁿ も、uⁿ 同様「ある項の値は直前の2項の和」という性質を持つ。和について「そういう性質を持つ数列」全体が c 倍されるのだから、同じ性質が維持されるのは当然だろう。同様に、vⁿ の定数倍 dvⁿ も同じ性質を持つ。さらに
　　「ある項の値は直前の2項の和」という性質を持つ数列と、
　　同じ性質を持つ別の数列の、項ごとの和
を考えても、結果は引き続き「ある項の値は直前の2項の和」という性質を持つ。例えば:
　　F_n = 1, 1, 2, 3, 5, …
　　L_n = 1, 3, 4, 7, 11, …
　　X_n = 2, 4, 6, 10, 16, …
とすると、X₂ = F₂ + L₂, X₃ = F₃ + L₃, X₄ = F₄ + L₄ = (F₂+L₂) + (F₃+L₃) = X₂ + X₃。以上の観察を総合すると: 「ある項の値は直前の2項の和」という性質を持つ数列の第n項は、cuⁿ + dvⁿ の一般形を持つ（c, d: 定数）。あとは、考えている具体的な数列の最初の2項と値が合うように、2種類の係数 c, d を決定すればいい。

この場合、Fibonacci 数列の第0項 F₀ = 0 と第1項 F₁ = 1 を使うと、話が早い（今まで第1項から始めていたのに、急に第0項を持ち出すのは変かもしれないけど、第0項を付け足して 0, 1, 1, 2, 3, 5, 8, … としても「直前の2項の和が次の項」という数列の性質は保たれる）:
　　F₀ = cu⁰ + dv⁰ = c + d = 0
　　F₁ = cu¹ + dv¹ = cu + dv = 1
第1式から d = −c、これを第2式に代入して cu − cv = c(u − v) = 1。ここで…
　　u − v = (1 + √5)/2 − (1 − √5)/2 = √5
…なので、c(u − v) = 1 は c√5 = 1 つまり c = 1/√5 を含意する。だから d = −c = −1/√5 となり、望む結果に至る:
　　cuⁿ + dvⁿ = (1/√5)uⁿ + (−1/√5)vⁿ = (uⁿ − vⁿ)/√5

第0項を使わず、第1項 F₁ = 1 と第2項 F₂ = 1 に基づくなら:
　　F₁ = cu + dv = 1
　　F₂ = cu² + dv² = 1
第1式から d = (1 − cu)/v、これを第2式に代入して:
　　cu² + [(1 − cu)/v]v² = cu² + v − cuv = 1
ここで uv = (1 + √5)/2 × (1 − √5)/2 = (1 − 5)/4 = −1 なので、上の式はこうなる:
　　cu² + v − c(−1) = c(u² + 1) + v = c(u + 2) + v = 1　［なぜなら④から　u² = u + 1］
従って c = (1 − v)/(u + 2) だが、この分子は…
　　1 − v = 2/2 − (1 − √5)/2 = (1 + √5)/2
…なので:
　　c = [(1 + √5)/2] / [(1 + √5)/2 + 2] = (1 + √5) / (5 + √5)
　　= (1 + √5) / [(√5 + 1)√5] = 1/√5

後はこの c = 1/√5 を d = (1 − cu)/v に入れれば、次のように d = −1/√5 となる。簡潔化のため √5 を y と略すと:
　　c = 1/y
　　cu = (1/y) × (1+y)/2 = (1+y)/(2y)
　　1 − cu = (2y)/(2y) − (1+y)/(2y) = (y−1)/(2y)
　　d = (1 − cu)/v = (y−1)/(2y) × 2/(1−y) = −1/y

〔参考〕　(F_n) と (L_n) の項ごとの和である前記 (X_n) は、Fibonacci 数列の第2項以降 1, 2, 3, 5, 8, … の2倍に等しい。この関係は、ある種の加法定理に関係している。

「帰納法による証明」【3】は、間違いではないが、あまり意味がない: というのも、個別のケースを証明するまでもなく「uⁿ の定数倍と vⁿ の定数倍の和」は、自動的にフィボナッチ的性質を持ち、最初の2項が一致すれば、それだけで数列全体が一致する――「直前の2項の和が次の項になる数列」では、最初の2項が一致すれば全部の項が一致することは、明らかだろう。（下に続く）

2022-11-03　不思議っち☆フィボナッチ（第3話）　一年生の夢

#数論　#フィボナッチ　#二項定理　#平方剰余

「一年生の夢」あるいは「新入生の夢」（freshman’s dream）とは (x + y)³ = x³ + y³ のような計算（分配法則？）をいう。整数や実数の世界では、そんなうまい話があるわけない。
　　『あ』　(x + y)³ = x³ + 3x²y + 3xy² + y³
が正しい。けれど mod 3 の世界では、3の倍数は ≡ 0 なので、右辺の第2項・第3項は消滅して両端だけが残り…
　　『い』　(x + y)³ ≡ x³ + y³ (mod 3)
…となる。「一年生の夢」がかなう！

「一年生の夢」を笑う「優等生」も、意外と (xy)^z = (x^z)(y^z) のような錯覚に陥っていることが多い（この「分配法則」は、複素数の範囲では、一般には成り立たない）。

【5】　Fibonacci 数列に限らず数論の話題では、『い』の形がしばしば重要な役割を果たす。事実関係を整理すると、
　　(x + y)⁷
のようなものを展開したいとき（二項定理）、原理的には
　　= [(x + y)(x + y)] ⋅ (x + y)⁵
　　= (x² + 2xy + y²) ⋅ (x + y)⁵
　　= [(x² + 2xy + y²)(x + y)] ⋅ (x + y)⁴
　　= …
のように、ばか正直に一つずつ計算することもできるし、あるいは全部展開した最終結果を丸暗記しておいてもいいのだが、一般論としては、次のように考えるのが普通だろう:
　　「結果は　x^ay^b　の形の項の和」
　　　　a は 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0 と変わり
　　　　b は 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 と変わる
　　　　（要するに a+b = 7）
つまり、展開結果は次の形になる:
　　□x⁷y⁰ + □x⁶y¹ + □x⁵y² + □x⁴y³ + □x³y⁴ + □x²y⁵ + □x¹y⁶ + □x⁰y⁷
そして「0乗は1」「1乗はその数自身」ということから、こうなる:
　　□x⁷ + □x⁶y + □x⁵y² + □x⁴y³ + □x³y⁴ + □x²y⁵ + □xy⁶ + □y⁷

問題は □ に入る係数（二項係数）。「7乗」のように値が小さく固定されているなら、Pascal の三角形を使うのが早道だろう。メモ用紙の余白に（あるいは頭の中で）
　　1　　　1
と書いて、あとは左上の数と右上の数の和を次々と書いていけばいい（左上・右上が空欄なら 0 と見なす）:

      1   1
     1  2  1
    1  3  3 1
   1 4  6  4 1　　　（よろしい）
  1 5 10 10 5 1　　　（古都統合）
 1 6 15 20 15 6 1　　　（ジャム！　いちごの煮汁　いちごジャム）
1 7 21 35 35 21 7 1　　　（なんかふと～い　産後産後　ふと～いなんか）

これが7乗の展開の係数なので、結局 (x + y)⁷ はこうなる（1倍は何もしないことと同じなので、係数 1 は省略）:
　　x⁷ + 7x⁶y + 21x⁵y² + 35x⁴y³ + 35x³y⁴ + 21x²y⁵ + 7xy⁶ + y⁷

【6】　12乗くらいまでなら Pascal の三角形を使う方法は十分実用になるが、13乗から二項係数が一部4桁になり、三角形の「足し算」もどんどん面倒になる。何より「一般的に n 乗」を扱いたいとき、Pascal の三角形では数のパターンを把握しづらい。そこで非常に役立つのが、次のような別の考え方。――実は上の係数は、次のきれいなパターンを持つ:
　　7 = (7)/(1)
　　21 = (7⋅6)/(1⋅2)
　　35 = (7⋅6⋅5)/(1⋅2⋅3)
　　35 = (7⋅6⋅5⋅4)/(1⋅2⋅3⋅4)
　　21 = (7⋅6⋅5⋅4⋅3)/(1⋅2⋅3⋅4⋅5)
　　7 = (7⋅6⋅5⋅4⋅3⋅2)/(1⋅2⋅3⋅4⋅5⋅6)
要するに、「n乗」（この場合は「7乗」）の展開では、両端以外の係数は、次の形の分数に等しい。
　　分子　(n)(n−1)(n−2)…　　←k個の数の積
　　分母　(1)(2)(3)…　　←k個の数の積
　　　　ここで k は、左端を第0項とした第1項では k=1、第2項では k=2、等々。

この方法では、右端（第n項）の係数が 1 になることも明らかだろう:
　　1 = (7⋅6⋅5⋅4⋅3⋅2⋅1)/(1⋅2⋅3⋅4⋅5⋅6⋅7)
さらに、左端（第0項）の係数も 1 になる:
　　1 = ()/()
掛け算は「倍数計算」、倍数の世界で「何もしない」ことは「1倍」なので^*1、上記の空っぽの ()/() は 1/1 に等しい。左端の項では k=0、右端の項では k=n と見れば、各項の係数は例外なく
　　(n↓_k)/(1↑_k)
となる。ここで n↓_k は、「n から始めて1ずつ減っていく整数 k 個の積」。 1↑_k は、「1 から始めて1ずつ増えていく整数 k 個の積」。後者は k! に他ならない（k の階乗）。

〔例〕　n = 7, k = 3 のとき: (7↓₃)/(1↑₃) = (7 × 6 × 5)/(1 × 2 × 3) = 210/6 = 35

*1　「0乗」が 1 になるのも、同じ原理。空積（empty product）と呼ばれる。「なぜ 0 乗が 1 か」「なぜマイナスかけるマイナスはプラスか」といったことは、あまり哲学的に悩まず、「そう定義するとつじつまが合うし、公式なども簡潔に書けて便利だから」「便宜上の話」と、気楽に考えよう！

これを（丸暗記でなく）ちゃんと理解するためには、次の三つに分けて考えるといいかも…。
　　①　なぜ上のような分数のパターンになるのか（説明）
　　②　なぜ上のような分数が必ず割り切れて、整数になるのか（説明）
　　③　階乗の記号や、いろいろな変な記号を使った表現:
　　　　以下では上記の係数 (n↓_k)/(1↑_k) を _nC_k で表す。
　　　　一般的には、しばしば ( n k ) で表される。

【7】　上記のパターンの結果として、(x + y)ⁿ を展開した両端の係数は常に 1、左端から2番目・右端から2番目の「一つ内側」の係数は（パスカルの三角形を見れば一目瞭然だが）常に n。
　　(x + y)ⁿ = xⁿ + nxⁿ⁻¹y + … + nxyⁿ⁻¹ +yⁿ
さらに n が素数の場合（この素数を n = p とする）、両端以外の第k項の係数は
　　[(p)(p−1)(p−2)…(p−k+1)] / [(1)(2)(3)…(k)]
となるが、両端以外なので k は p より小さい。素数 p は「自分より小さい2以上の整数」では割り切れないので、この分数を約分すると、分子の p は最後まで消えずに残る。例えば…
　　 (7⋅6⋅5⋅4)/(1⋅2⋅3⋅4) = (7⋅6⋅5⋅4)/(1⋅2⋅3⋅4) = 7⋅5 = 35

従って、両端以外の係数は必ず p の倍数になり、p の倍数は mod p では ≡ 0 なので、「一年生の夢」が実現する:
　　(x + y)^p = xⁿ + px^p−1y + …（この部分の項は全部pの倍数）… + pxy^p−1 +y^p
　　≡ x^p + 0 + 0 + … + 0 + 0 + y^p (mod p)
　　≡ x^p + y^p (mod p)　　ただし x, y は整数

【8】　Fibonacci 数列の Binet の式 F_n = (uⁿ − vⁿ)/√5 についても、同様の考え方が成り立つ。上記のような「整数」の演算のためには、無理数 u, v = (1±√5)/2 に含まれる √5 や 1/2 を除去しなければならないが、(1/2)ⁿ については、単に両辺を 2ⁿ 倍すれば消せるし、√5 についても、以下で見るように、この形の場合、偶数乗か奇数乗か、どちらか一方だけが残り、最終的には自然消滅する。

例えば:
　　『う』　(x + y)⁷ = x⁷ + 7x⁶y + 21x⁵y² + 35x⁴y³ + 35x³y⁴ + 21x²y⁵ + 7xy⁶ + y⁷
において y を (−y) に置き換えると…
　　(−y)² や (−y)⁴ などは、それぞれ (y)² や (y)⁴ と等しいが、
　　(−y) や (−y)³ や (−y)⁵ などは、それぞれ (y) や (y)³ や (y)⁵ と符号が逆なので
…次のように、yの奇数乗を含む項だけ、符号がマイナスに変わる:
　　『え』　(x − y)⁷ = x⁷ − 7x⁶y + 21x⁵y² − 35x⁴y³ + 35x³y⁴ − 21x²y⁵ + 7xy⁶ − y⁷
従って『う』と『え』の左辺同士・右辺同士を足し合わせると:
　　『お』　(x + y)⁷ + (x − y)⁷ = 2(x⁷ + 21x⁵y² + 35x³y⁴ + 7xy⁶)
y の偶数乗を含む項だけ残る。一方、足し合わせるのではなく、『う』から『え』を引き算すると:
　　『か』　(x + y)⁷ − (x − y)⁷ = 2(7x⁶y + 35x⁴y³ + 21x²y⁵ + y⁷)
今度は y の奇数乗を含む項だけが残る。

展開した式の各係数（両端以外）は、「一年生の夢」により 7 の倍数。『お』『か』で消えずに残った係数 21, 35, 7 も、依然として 7 の倍数。

Binet の式に当てはめる場合、Lucas 数列は簡単。例えば:
　　L₇ = u⁷ + v⁷ = (1 + √5)⁷/2⁷ − (1 − √5)⁷/2⁷
両辺を 2⁷ 倍して分母を払うと:
　　2⁷ L₇ = (1 + √5)⁷ + (1 − √5)⁷
この右辺は『お』で x = 1, y = √5 としたもの。√5 を y とすると:
　　2⁷ L₇ = 2(1 + 21y² + 35y⁴ + 7y⁶)
y の偶数乗だけが残る（これは √5 の偶数乗なので整数）。両辺を 2 で割って y² = 5, y⁴ = (y²)² = 5², y⁶ = (y²)³ = 5³ を代入すると:
　　『き』　2⁶ L₇ = 1 + 21⋅5 + 35⋅5² + 7⋅5³
これを普通に計算すると L₇ = 29 となるが、これは現実の Lucas 数列の第7項と一致。

Fibonacci 数列の例:
　　F₇ = (u⁷ − v⁷)/√5
両辺を √5 倍して^*2分母を払うと:
　　(√5) F₇ = u⁷ − v⁷ = (1+√5)⁷/2⁷ − (1−√5)⁷/2⁷
両辺を 2⁷ 倍して:
　　2⁷(√5) F₇ = (1+√5)⁷ − (1−√5)⁷
この右辺は『か』で x = 1, y = √5 としたもの:
　　2⁷(√5) F₇ = 2(7y + 35y³ + 21y⁵ + y⁷)　☆
今度は y の奇数乗だけが残った。両辺を (√5) つまり y で割ると^*3:
　　2⁷ F₇ = 2(7 + 35y² + 21y⁴ + y⁶)　☆☆
これで y の偶数乗だけになった。両辺を 2 で割って y² = 5 を代入すると:
　　『く』　2⁶ F₇ = 7 + 35⋅5 + 21⋅5² + 5³

*2 *3　とりあえず、このようにした方が分かりやすいが、*2 で両辺を √5 倍し、後から *3 で両辺を √5 で割るのは、無駄な回り道ともいえる。一般論としては、次のように考えた方が明快――「右辺を、分母が y = √5 の分数の形のままにしておく」と、☆において、「分子の各項に含まれる y の奇数乗（その奇数を 2m+1 としよう）」がその分母 y と約分されることで、☆☆のように、全部 y の偶数乗（すなわち y^2m）になる。y^2m = (√5)^2m = 5^m は整数。左端の項では、奇数 2m+1 とは 1 なので、m = 0 で 5^m = 1。

『く』の右辺を普通に計算すると 832。従って『く』の両辺を 2⁶ = 64 で割ると F₇ = 832/64 = 13。これは、現実の Fibonacci 数列の第7項と一致する。『く』右辺の最初の3項は、「一年生の夢」の名残で 7 の倍数（7 は素数なので）。だから『く』を mod 7 で考えると:
　　2⁶ F₇ ≡ 5³ (mod 7)
この 5³ (=125) の出所は y⁶ = (√5)⁶ = 5³ なので、こう考えることができる^*4:
　　2⁶ F₇ ≡ 5^6/2 (mod 7)　あるいは…
　　『け』　2⁷⁻¹ F₇ ≡ 5^(7−1)/2 (mod 7)

*4　整数 125 は y = √5 の 6 乗: Y = (√5)² = 5 をベースにすれば、Y の「6 の半分」乗、つまり 6/2 乗に等しい。

『け』左辺の係数 2⁷⁻¹ は、Fermat の小定理から ≡ 1 となり、mod 7 では無いのと同じこと。さらに『け』右辺の 5^(7−1)/2 は Euler の基準の形: mod 7 において 5 が平方剰余なら ≡ 1 になり非剰余なら ≡ −1 になる。この場合、実は非剰余なので^*5 ≡ −1。従って、『け』は次を含意する:
　　F₇ ≡ −1 (mod 7)
つまり F₇ は 7 の倍数より 1 小さい。F₇ = 13 は、まさにこの性質を持っている！

*5　意味: z² ≡ 5 (mod 7) を満たす整数 z が存在しない。実際 mod 7 では z ≡ 0, ±1, ±2, ±3 の7種類の可能性しかなく、どれを試しても平方は ≡ 5 にならない。

『き』も同様に処理可能: Lucas 数列の場合、Euler の基準が絡まず、単純に L₇ ≡ 1 (mod 7) となる。L₇ = 29 は、確かに 7 の倍数より 1 大きい。

【9】　【8】では p = 7 という具体例を考えた。今度は一般の素数 p を考えよう: p を 7 以上の（従って奇数の）任意の素数とし、y = √5 とすると、Binet の公式をこう書ける:
　　『こ』　(u^p − v^p)/y = F_p, u^p + v^p = L_p
ここで:
　　u^p = [(1 + y)/2]^p　従って　2^pu^p = (1 + y)^p　展開すると
　　『さ』　2^pu^p = 1 + (_pC₁)y + (_pC₂)y² + (_pC₃)y³ + (_pC₄)y⁴ + (_pC₅)y⁵ + … + (_pC_p−1)y^p−1 + y^p
同様に 2^pv^p = (1 − y)^p を展開すると:
　　『し』　2^pv^p = 1 − (_pC₁)y + (_pC₂)y² − (_pC₃)y³ + (_pC₄)y⁴ − (_pC₅)y⁵ + … + (_pC_p−1)y^p−1 − y^p

〔注〕　_pC_○ は二項係数（【6】参照）。理論的には、右辺の最初の項 1 の前に (_pC₀) があり、最後の項 ±y^p の前に (_pC_p) がある。これらの係数は 1 に等しいので、ここでは表記を省略。省略されていない係数は、どれも p の倍数に等しい（p が素数なので）。

『さ』と『し』を足し合わせると:
　　2^p(u^p + v^p) = 2[1 + (_pC₂)y² + (_pC₄)y⁴ + … + (_pC_p−1)y^p]
両辺を 2 で割ると:
　　『す』　2^p−1(u^p + v^p) = (_pC₂)y² + (_pC₄)y⁴ + … + (_pC_p−1)y^p−1

一方、『さ』から『し』を引くと:
　　2^p(u^p − v^p) = 2[(_pC₁)y + (_pC₃)y³ + (_pC₅)y⁵ + … + y^p]
両辺を 2y で割ると:
　　『せ』　2^p−1(u^p − v^p)/y = (_pC₁) + (_pC₃)y² + (_pC₅)y⁴ + … + y^p−1

〔注〕　右端の y^p−1 の係数は理論的には _pC_p だが、それは = 1 なので省略されている。

今、『す』『せ』の左辺に『こ』を代入し、右辺に y² = 5 を代入すると:
　　2^p−1 L_p = 1 + (_pC₂)5 + (_pC₄)5² + … + (_pC_p−1)5^(p−1)/2
　　2^p−1 F_p = (_pC₁) + (_pC₃)5 + (_pC₅)5² + … + 5^(p−1)/2
Fermat の小定理から 2^p−1 ≡ 1 (mod p)。しかも _pC₁ や _pC₂ などは全部 ≡ 0 (mod p) なので――なぜなら p が素数なので「一年生の夢」が発動――、上の二つの式は、mod p では、次のすごくシンプルな形になる！
　　L_p ≡ 1 (mod p)
　　F_p ≡ 5^(p−1)/2 (mod p)

最後の右辺は Euler の基準。すなわち Fibonacci 数列の第p項 F_p を mod p で考えた場合、5 が平方剰余か非剰余かに応じて、≡ 1 あるいは ≡ −1 になる。他方、Lucas 数列の第p項 L_p は、常に ≡ 1 に。

〔補足〕　素数 p に「7以上」と条件を付けている理由は、p = 5 を法とすると、Fibonacci 数列に関して、Euler の基準が使えないため。Lucas 数列に関しては、p は任意の素数でも構わない。

平方剰余の相互法則から、「5 が平方剰余か非剰余か」は、「p が mod 5 で平方剰余か非剰余か」と一致（5 は4k+1型の素数なので）。直接計算によると^*6、mod 5 において、10k±1型の素数は平方剰余、10k±3型の素数は非剰余。前者の型の素数は、10の倍数と 1 違うのだから、最下位桁が 1 か 9。後者の型の素数は、最下位桁が 3 か 7。このことから、Fibonacci 数列の素数番目の項（第7項以降。その素数を p とする）について、その項の値を p で割った余り r は、p の1の位が 1 or 9 なら r = 1 となり、p の1の位が 3 or 7 なら r = p−1 になる。

*6　mod 5 では 0 を別にすると、(±1)² ≡ 1 と (±2)² ≡ 4 が平方剰余で、2 と 3 が非剰余。つまり、①「5k+1型（11, 31, 41, …）＆5k+4型（19, 29, 59, …）の素数」（全て奇数）が平方剰余、②「5k+2型（7, 17, 37, …）＆5k+3型（3, 13, 23, …）の奇数の素数」が非剰余（素数 2 も5k+2型だが、奇数でないので、相互法則に従わない）。①を「10k±1型」、②を「10k±3型」と呼ぶことができる（この分類では、2 と 5 は、①にも②にも含まれない例外の素数）。平方剰余の相互法則によると、p = 5 のような4k+1型の素数については、p と q を入れ替えても判定結果は変わらない。つまり「mod p で q が平方剰余なら mod q でも p は平方剰余」「mod p で q が非剰余なら mod q でも p は非剰余」。要するに、2, 5 を除く任意の素数 q は、「①に属するか②に属するかに応じて、mod 5 で平方剰余・非剰余」であり、さらに「①に属するか②に属するかに応じて、mod q で 5 は平方剰余・非剰余」になる。

〔例1〕　末尾が 1 or 9 の場合（10k±1型素数）:
素数 p = 11 に対して F₁₁ = 89。この 89 は 11 の倍数より 1 大きい。
素数 p = 19 に対して F₁₉ = 4181。この 4181 は 19 の倍数より 1 大きい。
　（普通の検算）　22 × 20 = 440 なので 22 × 19 = 440 − 22 = 418。だから 220 × 19 = 4180 は19の倍数。
　（変な検算）　418は（4180も）19の倍数。なぜなら末尾の2倍「16」を上位2桁「41」に足すと「57」、これは19の倍数。（参考: 19の倍数の判定法）

〔例2〕　末尾が 3 or 7 の場合（10k±3型素数）:
素数 p = 13 に対して F₁₃ = 233。この 233 は 13 の倍数より 1 小さい。
　（変な検算）　234 は13の倍数。なぜなら末尾の4倍「16」を上位2桁「23」に足すと「39」、これは13の倍数。（参考: 13の倍数の判定法）
素数 p = 17 に対して F₁₇ = 1597。この 1597 は 17 の倍数より 1 小さい。
　（変な検算）　1598 は17の倍数。なぜなら末尾の5倍「40」を上位3桁「159」から引くと「119」、これは17の倍数。（参考: 17の倍数の判定法）

「分かってみれば当たり前」かもしれないが、軽妙ですてきな感じがする。実は「素数」番目の項に限らず「素数の2倍」番目の項 F_2p についても、同様の性質が成り立つ。（下に続く）

〔付記〕　本文で触れたように、13乗以上の二項係数は一部4桁になる。13乗の4桁係数 1287 と 1716 については「人に花・人七色」という語呂合わせで直接覚えられないこともない。14乗の4桁係数は4種類あり、そのうち三つは 1001, 2002, 3003（千夜一夜の2倍・3倍）という特徴的な数なので印象に残る。一番大きいもう一つの係数 3432（山陽サニー）は、上記 1716（人七色）の2倍に等しい（一般に、偶数乗の最大の係数は、一つ下の奇数乗の最大係数の2倍）。さらに大きい指数を考えると、16乗以上で5桁の係数、20乗以上で6桁の係数が現れる。――言うまでもなく、そのような個別の事実（個々の係数）をいちいち覚えるより、「どうやって任意の係数を求められるか？」という二項定理を理解した方が、はるかに役立つ。

2022-11-05　不思議っち☆フィボナッチ（第4話）　夢のもつれ

#数論　#フィボナッチ　#二項定理　#平方剰余

Fibonacci 数列は 1, 1 から始めて（あるいは 0, 1 から始めて）、直前の2項の和を次の項としたもの:
　　1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
最初の 1 を第1項、2番目の 1 を第2項、3番目の 2 を第3項…と呼び、それぞれ F₁, F₂, F₃, … で表す（もし 0, 1 から始めた場合には 0 を第0項 F₀ とする）。例えば F₇ = 13 は直前の2項 5, 8 の和。

n が 7 以上の素数（7, 11, 13, …）のとき、次のように、F_n の直前か直後のフィボナッチ数が n の倍数になる！

詳しく言うと、7 以上の素数 n が10の倍数と1違いのとき（つまり1の位が 1 or 9 のとき。言い換えれば10k±1型のとき）、F_n の直前のフィボナッチ数 F_n−1 がその n で割り切れる; 素数 n がそれ以外のとき（つまり1の位が 3 or 7 のとき。言い換えれば10k±3型のとき）、直後のフィボナッチ数 F_n+1 がその n で割り切れる。具体例を見た方が、意味が分かりやすい…

素数の世界は秘密がいっぱい

n	Fn	観察	Fn の値は…
5	5	n は例外の素数
6	8			7★の倍数+1
7★	13	n は 10k±3型素数		7★の倍数−1
8	21	21 = 3 × 7★		7★の倍数
9	34
10	55	55 = 5 × 11☆	11☆の倍数
11☆	89	n は 10k±1型素数	11☆の倍数+1
12	144		11☆の倍数+1	13★の倍数+1
13★	233	n は 10k±3型素数		13★の倍数−1
14	377	377 = 13★ × 29		13★の倍数
15	610
16	987			17★の倍数+1
17★	1597	n は 10k±3型素数		17★の倍数−1
18	2584	2584 = 8 × 17★ × 19☆	19☆の倍数	17★の倍数
19☆	4181	n は 10k±1型素数	19☆の倍数+1
20	6765		19☆の倍数+1

（n = 18 のように、n が「7で終わる素数」と「9で終わる素数」の双子素数で挟まれる場合、2種類の「倍数」が同時に適用され、F_n は n−1, n+1 の両方で割り切れる。）

【10】　例えば n = 7 の場合。第7項の次の（第8項の）フィボナッチ数――Binet の公式によれば…
　　『た』　F₈ = (u⁸ − v⁸) / y
…という数（具体的には 21）――が、7 で割り切れる仕組みを知りたい。前回同様 y = √5, u = (1 + y)/2, v = (1 − y)/2 は定数。『た』右辺の構成要素について:
　　u⁸ = (1 + y)⁸ / 2⁸
両辺を 2⁸ 倍して分母を払い、二項定理を使うと:
　　2⁸⋅u⁸ = 1 + (₈C₁)y + (₈C₂)y² + (₈C₃)y³ + (₈C₄)y⁴ + (₈C₅)y⁵ + … + (₈C₇)y⁷ + (₈C₈)y⁸
同様に（プラスとマイナスの符号については前回【8】参照）:
　　2⁸⋅v⁸ = 1 − (₈C₁)y + (₈C₂)y² − (₈C₃)y³ + (₈C₄)y⁴ − (₈C₅)y⁵ + … − (₈C₇)y⁷ + (₈C₈)y⁸
上から下を引くと:
　　『ち』　2⁸(u⁸ − v⁸) = 2(₈C₁)y + 2(₈C₃)y³ + 2(₈C₅)y⁵ + 2(₈C₇)y⁷
両辺を 2y で割ると:
　　『つ』　2⁷(u⁸ − v⁸) / y = (₈C₁) + (₈C₃)y² + (₈C₅)y⁴ + (₈C₇)y⁶

『つ』左辺は 2⁷ を無視すれば『た』右辺と同じ; F₈ の 2⁷ = 128 倍に当たる。 y² = 5, y⁴ = 5², y⁶ = 5³ なので、『つ』右辺は整数、それと等しい『つ』左辺も整数。分母に y = √5 があるものの、この分数の値は、無理数ではなく整数。

『つ』右辺の4種の二項係数は:
　　₈C₁ = (8)/(1) = 8, ₈C₃ = (8⋅7⋅6)/(1⋅2⋅3) = 56,
　　₈C₅ = (8⋅7⋅6⋅5⋅4)/(1⋅2⋅3⋅4⋅5) = 56, ₈C₇ = (8⋅7⋅6⋅5⋅4⋅3⋅2)/(1⋅2⋅3⋅4⋅5⋅6⋅7) = 8

〔検算〕　『た』から、『つ』左辺は 2⁷ F₈ = 128⋅21 = 2688。『つ』右辺は:
　　(8) + (56)5 + (56)25 + (8)125 = 2688　左辺と一致。

キーポイントとして、₈C₃ と ₈C₅ は（分子の素因数 7 が約分されずに残るので）7 の倍数。つまり、これらの係数は ≡ 0 (mod 7)。フェルマーの小定理から 2⁶ ≡ 1、その両辺を 2 倍して 2⁷ ≡ 2 なので、『つ』は次を含意する:
　　『て』　2F₈ ≡ 8 + 0⋅5 + 0⋅5² + 8⋅5³ ≡ 8 + 8⋅5^(7−1)/2 (mod 7)
…これは「一年生の夢」のバリエーション。

『て』右端の 5^(7−1)/2 の部分はオイラーの基準の形で、mod 5 で 7 が平方剰余か非剰余かに応じて ≡ 1 or −1 になる。ここでは（7以上の）10k±3型（5k±2型）素数を考えているので、非剰余。だから ≡ −1。従って『て』は、こうなる:
　　2F₈ ≡ 8 + 8(−1) ≡ 0 (mod 7)
両辺を 2 で割って:
　　F₈ ≡ 0 (mod 7)
これは F₈ が 7 で割り切れるという意味: それが確かめたいことだった！

【11】　一般に p を 7 以上の素数として【10】同様に進めると、『つ』に当たる一般式は:
　　2^p(u^p+1 − v^p+1) / y = (_p+1C₁) + (_p+1C₃)y² + (_p+1C₅)y⁴ + … + (_p+1C_p)y^p−1
そこから、『て』に当たる次の式を得る:
　　2F_p+1 ≡ (p+1) + 0 + 0 + … + 0 + (p+1)⋅5^(p−1)/2 (mod p)

右辺の両端以外の 0 (mod p) は、「一年生の夢」のバリエーション（言い換えると、これらの各項は p の倍数）。

要するに:
　　『と』　2F_p+1 ≡ (p+1) + (p+1)⋅5^(p−1)/2 (mod p)

オイラーの基準から、p が10k±3型素数なら 5^(p−1)/2 ≡ −1 (mod p) なので:
　　2F_p+1 ≡ (p+1) + (p+1)(−1) ≡ 0　つまり　F_p+1 ≡ 0 (mod p)
…となって、この場合 F_p+1 が p で割り切れる。□

〔10k±3型素数の例〕　p = 7 のとき F_p+1 = F₈ = 21 は p = 7 で割り切れる。p = 13 のとき F_p+1 = F₁₄ = 377 は p = 13 で割り切れる: 377 = 390 − 13 = 13 × 30 − 13 = 13 × 29。

【12】　一方 p が10k±1型素数なら、オイラーの基準から 5^(p−1)/2 ≡ 1 (mod p) なので、『と』はこうなる:
　　2F_p+1 ≡ (p+1) + (p+1) ≡ 2 (mod p)
両辺を2で割ると:
　　『な』　F_p+1 ≡ 1 (mod p)

前回の内容から、p が10k±1型素数なら:
　　『に』　F_p ≡ 1 (mod p)

フィボナッチ数列の性質上 F_p+1 = F_p + F_p−1 が成り立つ。つまり:
　　F_p−1 = F_p+1 − F_p
等しい整数（上記の左辺と右辺）を p で割った余りは、もちろん等しい。言い換えれば:
　　『ぬ』　F_p−1 ≡ F_p+1 − F_p (mod p)
『ぬ』に『な』『に』を代入すると…
　　F_p−1 ≡ 1 − 1 ≡ 0 (mod p)
…となって、p で割った余りが 0。要するに、この場合 F_p−1 が p で割り切れる。□

〔10k±1型素数の例〕　p = 11 のとき F_p+1 = F₁₂ ≡ 1 (mod 11)。実際 F₁₂ = 144 は 11 の倍数 11⋅13 = 143 より 1 大きい。一方、前回の内容から F_p = F₁₁ も ≡ 1 (mod 11)。実際 F₁₁ = 89 は 11 の倍数 88 より 1 大きい。フィボナッチ数列は F₁₀ + F₁₁ ≡ F₁₂ つまり F₁₀ + 1 ≡ 1 (mod 11) を満たすから、F₁₀ ≡ 0 (mod 11)。実際 F₁₀ = 55 は 11 の倍数。

他方、p が10k±3型素数の場合、【11】の結論 F_p+1 ≡ 0 と前回の結論 F_p ≡ −1 (mod p) を両方『ぬ』に代入すると、F_p−1 ≡ 0 − (−1) ≡ 1 (mod p)。

まとめると――
　　①　p が10k±1型素数なら: F_p−1 は p の倍数; F_p と F_p+1 は、どちらも p の倍数より 1 大きい。
　　②　p が10k±3型素数なら: F_p+1 は p の倍数; F_p は p の倍数より 1 小さく、F_p−1 は p の倍数より 1 大きい。

整数の話なのに無理数 y = √5 が絡むのは、少し違和感があるかもしれないけど、飛び込んでみたら、とんとん拍子に話が進んだ。（下に続く）

〔参考〕　上記の発想を応用して、逆に「p が10k−1型素数なら、5 は mod p の平方剰余」ということを証明できる――この逆コースは面白い（第五補充法則）。19世紀に Lagrange によって発見されたものの、その後、一般性の高い「平方剰余の相互法則」が確立されたため、個別のケースについての議論は必要なくなり、歴史に埋もれてしまった。現代の文献には載ってないので、かえって新鮮に感じられる。

2022-11-10　不思議っち☆フィボナッチ（第5話）　星のらせん階段

#数論　#フィボナッチ

Fibonacci 数列は奥が深い。それだけで本を一冊書けるどころか、Fibonacci 数列研究専門の季刊誌が発行されている！　ガチにディープ…

とりあえず、第1部のネタを完結させたい: p を 7 以上の素数として「p 番目のフィボナッチ数」や「2p 番目のフィボナッチ数」は、p を 5 で割った余りに応じて（言い換えれば p の1の位の数字によって）、p の倍数±1 になる。この観察について、核心部の証明は済んだ。

【13】　奇数の素数は、通常、1の位が 1, 3, 7, 9 のどれかになり、「5k±1型」と「5k±2型」に分類可能。p = 5 は例外。で、5番目のフィボナッチ数 F₅ = 5 は、5 の倍数。値が「5 の倍数になる」という性質は、F₁₀ = 55, F₁₅ = 610, F₂₀ = 6765 のように、「5の倍数」番目のフィボナッチ数全部に受け継がれている。次のように、簡単な算数で証明できる！

F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5 について、フィボナッチ数の定義から:
　　F₅ = F₃ + F₄
　　F₄ = F₂ + F₃
下を上に代入して:
　　F₅ = F₃ + (F₂ + F₃) = F₂ + 2F₃
そこにさらに F₃ = F₁ + F₂ を代入して:
　　F₅ = F₂ + 2(F₁ + F₂) = 2F₁ + 3F₂
そこにさらにさらに F₂ = F₀ + F₁ を代入すると…
　　F₅ = 2F₁ + 3(F₀ + F₁) = 3F₀ + 5F₁

F₀ から見て、5個先のフィボナッチ数 F₅ は、「自分の 3 倍」と「自分の次のフィボナッチ数 F₀ の 5 倍」の和。上の算数は、フィボナッチ数の定義（性質）だけに基づき、F₅ などの具体的な値とは無関係。だから、勝手に選んだ別の項、例えば…
　　F₆ = F₄ + F₅
　　F₅ = F₃ + F₄
…から始めても、番号が違うだけで計算自体は同じ。同様に進めて、
　　F₆ = 3F₁ + 5F₂　（5個先の値は、自分の3倍プラス次の項の2倍）
になるはず（ピンとこなければ、途中計算を書いて確かめてみよう）。事実 F₆ = 8 = 3 × 1 + 5 × 1。同様に:
　　F₇ = 13 = 3 × 1 + 5 × 2
より一般的に:
　　F_n+5 = 3F_n + 5F_n+1

キュートな結果が得られた！　5個先の項は「自分の3倍」と「次の項の5倍」の和。もし F_n 自身が 5 の倍数なら、F_n = 5k として（k は整数）、次の項 F_n+1 を C とすると:
　　5個先の項 = 3F_n + 5C = 3(5k) + 5C = 5(3k + C) = 5 の倍数

〔解説〕　5C はもちろん『5の倍数』。もし F_n が「5の倍数」なら、3F_n も「5の倍数」で、そのとき 3F_n + 5C は「5の倍数」プラス『5の倍数』で5の倍数。逆に F_n が5の倍数でなければ 3F_n + 5C も5の倍数ではない（なぜなら 5C の部分は「5の倍数」なので、3F_n + 5C が5で割り切れるかどうかは、3F_n が5で割り切れるかどうかで決まる。ところが、5の倍数でない F_n を3倍しても5の倍数にならないので、3F_n は5で割り切れない）。具体的に F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3 は5の倍数でないので、F₁, F₆, F₁₁, F₁₆, … は5の倍数ではなく、F₂, F₇, F₁₂, F₁₇, … も5の倍数ではない。F₃, F₈, … や F₄, F₉, … も同様。結局 F_n は、n が5の倍数なら（そしてそのときに限って）、5の倍数。

F₀ = 0 は 5 の倍数（0倍）なんだから、
　　F₅, F₁₀, F₁₅, F₂₀, …
が全部 5 の倍数になるってわけ。

〔例1〕　F₀ = 0 は 5 の倍数。F₁ = 1。だから…　F₅ = 3 × 0 + 5 × 1 = 0 + 5 = 5　も 5 の倍数。

〔例2〕　F₅ = 5 は 5 の倍数。F₆ = 8。だから…　F₁₀ = 3 × 5 + 5 × 8 = 15 + 40 = 55　も 5 の倍数。

〔例3〕　F₁₀ = 55 は 5 の倍数。F₁₁ = 89。だから…　F₁₅ = 3 × 55 + 5 × 89 = 165 + 445 = 610　も 5 の倍数。

【14】　けど、こう考えると「5個先」って間隔にこだわる必要もなく、「3個先」「4個先」「6個先」…なども同じように、出発点となる項の値 F_n と次の項の値 F_n+1 の式として、計算できるはず。そういう目でフィボナッチ数列を眺めると、下記のことが予想される。

Fibonacci 数列の最初の12項（@ は「3の倍数」番目）

n	1	2	3@	4	5	6@
Fn	1	1	2	3	5	8
n	7	8	9@	10	11	12@
Fn	13	21	34	55	89	144

☆3☆　F₃ = 2, F₆ = 8, F₉ = 34 のように「3の倍数」番目のフィボナッチ数は、偶数（2 の倍数）。表の @ の部分。

☆4☆　F₄ = 3, F₈ = 21, F₁₂ = 144 のように「4の倍数」番目のフィボナッチ数は 3 の倍数。

☆5☆　F₅ = 5, F₁₀ = 55 のように「5の倍数」番目のフィボナッチ数は 5 の倍数（たった今証明した）。

☆6☆　F₆ = 8, F₁₂ = 144 のように「6の倍数」番目のフィボナッチ数は 8 の倍数。

一般的に　F_n = ○, F_2n = △, F_3n = □, … のような場合、「nの倍数」番目のフィボナッチ数 ○, △, □, … は、それぞれ F_n = ○ の倍数になるのでは？

だとしたら、ちょ～美しい！　自然数 n がフィボナッチ数 F_n を響かせると、その F_n が作る倍数列の上に F_2n, F_3n, F_4n, … がきれいに乗っている。まるで倍音列ように…。星の渦巻き、倍数の波長のハーモニー、絡まり合う無限個のらせん階段。

☆3☆、☆4☆などについては、☆5☆同様の算数で簡単に証明できる。F_n = B, F_n+1 = C として、F_n+2 = F_n + F_n+1 = B + C に注意すると:
　　F_n+3 = F_n+1 + F_n+2 = C + (B + C) = B + 2C
　　　→　B (= F_n) が偶数のとき（そしてそのときに限って）3個先の項も偶数。
　　　　　一方、最初の3項のうち F₃ = 2 だけが偶数。
　　F_n+4 = F_n+2 + F_n+3 = (B + C) + (B + 2C) = 2B + 3C
　　　→　B が3の倍数のとき（そのときに限って）4個先も3の倍数。
　　　　　一方、最初の4項のうち F₄ = 3 だけが3の倍数。
　　F_n+5 = F_n+3 + F_n+4 = (B + 2C) + (2B + 3C) = 3B + 5C
　　　→　B が5の倍数のとき（そのときに限って）5個先も5の倍数。
　　　　　一方、最初の5項のうち F₅ = 5 だけが5の倍数。
　　F_n+6 = F_n+4 + F_n+5 = (2B + 3C) + (3B + 5C) = 5B + 8C
　　　→　B が8の倍数のとき（そのときに限って）6個先も8の倍数。
　　　　　一方、最初の6項のうち F₆ = 8 だけが8の倍数。
　　F_n+7 = F_n+5 + F_n+6 = (3B + 5C) + (5B + 8C) = 8B + 13C
　　　→　B が13の倍数のとき（そのときに限って）7個先も13の倍数。
　　　　　一方、最初の7項のうち F₇ = 13 だけが13の倍数。
　　etc.

上記各式の右端の B の係数 1, 2, 3, 5, 8, … は、それ自身フィボナッチ数列の第2項以降、つまり:
　　F₂, F₃, F₃, F₅, F₆, …
C の係数 2, 3, 5, 8, 13, … は、フィボナッチ数列の第3項以降、つまり:
　　F₃, F₃, F₅, F₆, F₇, …
この観察を整理すると、次の関係が予想されるだろう:
　　F_n+x = (F_x−1)B + (F_x)C　　【☆】

【☆】が x = 3, 4, 5, 6, 7 について成り立つのは、前記の直接計算から明らか。さらに、もし x = t（定数）と x = t+1 について【☆】が正しければ、x = t+2 についても自動的に【☆】が成り立つ――実際、仮定の話として、もし
　　F_n+t = (F_t−1)B + (F_t)C　　‥‥❶
　　F_n+t+1 = (F_t+1−1)B + (F_t+1)C = (F_t)B + (F_t+1)C　　‥‥❷
が成り立つとすると:
　　F_n+t+2 = F_n+t + F_n+t+1　　←フィボナッチ数列の性質
　　= [(F_t−1)B + (F_t)C] + [(F_t)B + (F_t+1)C]　　←仮定❶❷より
　　= (F_t−1 + F_t)B + (F_t + F_t+1)C　　←展開して同類項をくくった
　　= (F_t+1)B + (F_t+2)C　　←フィボナッチ数列の性質
つまり:
　　F_n+t+2 = (F_t+2−1)B + (F_t+2)C
これは【☆】において x = t+2 としたものに他ならない！

従って、帰納（きのう）法により、3 以上の任意の整数 x に対し【☆】は正しい。B と C の意味を思い出すと【☆】はこうなる:
　　F_n+x = (F_x−1)F_n + (F_x)F_n+1　　【☆☆】

この【☆☆】は、それ自体として有用であるばかりか、次の美しい定理とつながっている。

「星のらせんの定理」　x を 3 以上の整数とすると F_x, F_2x, F_3x, F_4x, … は、いずれも F_x の倍数: 言い換えると、y が x の倍数なら F_y は F_x の倍数。逆に F_y が F_x の倍数になるのは、y が x の倍数の場合に限られる。

〔例〕　x = 4 の場合、次の各項はいずれも F₄ = 3 の倍数: F₈ = 21, F₁₂ = 144 (= 3 × 48), F₁₆ = 987 (= 3 × 329)

証明　第一に、F_x が F_x の倍数（1倍）であることは言うまでもない。

第二に、【☆☆】で n = x とすると、【☆☆】の右辺第1項は (F_x−1)F_x つまり F_x の倍数になる。【☆☆】の右辺第2項はもともと F_x の倍数だから、このとき、それらの和である【☆☆】の右辺は F_x の倍数。それに等しい左辺 F_2x も F_x の倍数。

第三に、【☆☆】で n = 2x とすると、【☆☆】の右辺第1項は (F_x−1)F_2x になるが、たった今見たように F_2x は F_x の倍数なので、この項は F_x の倍数。【☆☆】の右辺第2項はもともと F_x の倍数だから、上記と同様に【☆☆】の左辺 F_3x も F_x の倍数。

以下同様に進めると、F_kx の形の項（k: 自然数）は全て F_x の倍数。

正式には帰納法の形で述べるべきかもしれないが、上記のロジックは明らかだろう。

次に逆を示す。まず F₁, F₂, F₃, …, F_x−1 がどれも F_x の倍数ではないことに注意する。実際、これらの数（以下、その任意の一つを F_r とする）は、F_x 未満の正の整数であり、F_x の 0 倍より大きく 1 倍未満。今、F_n が F_x の倍数ではないと仮定して、そのときには F_n+x も F_x の倍数ではないことを示そう。それが示されるなら、F_r から始めてこの事実を k 回繰り返し使うことにより、F_r+kx の形の任意の項（つまり番号が x で割り切れないフィボナッチ数）は、F_x の倍数ではないと結論される（x は 3 以上）。

〔例〕　F_x = F₆ = 8 について、r = 3 とすると F_r = F₃ = 2 は、もちろん F₆ の倍数ではない。上のことが証明されたあかつきには、F₃₊₆ = F₉ も F₆ の倍数ではなく、従って F₉₊₆ = F₃₊₆₊₆ = F₁₅ も F₆ の倍数ではなく、従って F₁₅₊₆ = F_3+6+6+6 = F₂₁ も F₆ の倍数ではなく…一般に F_3+6k は F₆ の倍数ではない。r として 1, 2, 3, 4, 5 のどれを選んでも、同じようにして F_r+6k は F₆ の倍数ではない; 要するに「6で割り切れない番号」の項 F_r+6k は、どれもこれも F₆ の倍数ではない――ということになる！

【☆☆】から:
　　F_n+x = (F_x−1)F_n + (F_x)F_n+1
この右辺第2項は F_x の倍数なので、右辺第1項 (F_x−1)F_n が F_x の倍数ではないことを示せば、証明は完成する（F_x の倍数ではない数と、F_x の倍数の和は、F_x の倍数ではない）。下記の理由から、それには F_x−1 と F_x が 2 以上の公約数を持たないこと（互いに素であること）を示せば十分。

〔理由〕　F_x の素因数分解を p₁p₂…p_s としよう（各素因数は必ずしも相異ならない）。今 F_n は F_x の倍数ではないと仮定しているので、F_n は、素因数として s 個の p たち全部を含むことはない: p たちの中には F_n の素因数ではないもの（もしくは F_n に含まれる個数が不足していて、F_n が F_x の倍数になることを妨げる素数）が、少なくとも一つ存在する――それを p_j としよう。ここで、もし F_x と F_x−1 が互いに素なら、F_x−1 は素因数として p₁, p₂, … を一つも含んでいないことになり、従って積 (F_x−1)F_n においても、素数 p_j の不足は解消されない――ゆえに、この積が F_x の倍数になることはない。

〔解説〕　例えば F_n = F₂₀ = 6765 = 3⋅5⋅11⋅41 は F_x = F₁₅ = 610 = 2⋅5⋅61 の倍数ではない。当然、F₁₅ の素因数の中には、F₂₀ に「素因数として含まれないもの」もしくは「含まれる個数が足りないもの」がある（2 と 61）――なぜなら、もしも F₁₅ の素因数の全部が不足なく F₂₀ に含まれていたら、F₂₀ は F₁₅ の倍数になるはずだが、事実はそうでないのだから。そのような「不足素因数」の一つが、上記 p_j である。けれど、もしも F_x−1 = F₁₄ が素因数として 2 と 61 を両方含んでいて「不足素因数」を補ってくれるのなら、F₂₀ 自体が F₁₅ の倍数でないにもかかわらず、不足が解消され積 (F₁₄)F₂₀ は F₁₅ = 2⋅5⋅61 の倍数になるかもしれない――それがあり得ないことを示せば（つまり「不足素因数」が補充されるという可能性を否定できれば）いい。ところが、もし F₁₄ と F₁₅ が互いに素だとすると、その場合 F₁₄ の素因数の中に F₁₅ の素因数（2 or 5 or 61）と共通のものは一つもないのだから、F₁₅ にあって F₂₀ には不足している素因数 p_j が F₁₄ から補充されるわけがない。すなわち、上記の可能性は否定される。同様に考えると、一般に「F_x−1 と F_x が互いに素」と断定できれば、それで十分。実は「フィボナッチ数列の隣同士の項は互いに素」ということは、次のように簡単に証明可能…。

もしも F_x−1 と F_x が互いに素でなく、2 以上の公約数 d を持つなら、どちらの数も d の倍数なので、それらの差
　　F_x − F_x−1 = F_x−2
も d の倍数。従って、同じ理由から
　　F_x−1 − F_x−2 = F_x−3
も d の倍数。同様に進めると、フィボナッチ数列の第1項から第 x 項までは、どの項も d の倍数になるはず。これはばかげている――現実には F₁ = 1 や F₂ = 1 が「2 以上の整数 d」の倍数のわけない。従って F_x と F_x−1 は、互いに素と結論される。□

〔注意〕　「星のらせんの定理」は x = 1 に対しても有効: 任意のフィボナッチ数 F_1k は F₁ = 1 の倍数であり、逆に F_y が F₁ の倍数になるとき（常にそうなる）、y は 1 の倍数（常にそうなる）。一方、x = 2 に関しては、任意の F_2k が F₂ = 1 の倍数であることは論をまたないが、この場合、逆に「F_y が F₂ = 1 の倍数になるのは y が 2 の倍数のときに限られる」とは言えない。そのため、逆も考える場合、この定理には「x が 3 以上」という付帯条件が必要（[1] p. 39 の Theorem III では、この条件が抜けている）。あるいは、次のように精密化できる: 「x, y を正の整数とする。y が x の倍数なら F_y は F_x の倍数。逆に F_y が F_x の倍数なら y は x の倍数または x = 2」

ところで【☆☆】自体は、x = 2 としても成り立つ。実際 F₁ = F₂ = 1 なので:
　　F_n+2 = (F₂₋₁)F_n + (F₂)F_n+1 = 1 × F_n + 1 × F_n+1 = F_n + F_n+1
これは F_n+2 = F_n + F_n+1 という意味だが、それはフィボナッチ数列の基本性質であり、もちろん正しい。

【☆☆】は x = 1 としても成り立つ。その場合、フィボナッチ数列の第0項 F₀ = 0 を使うことになる:
　　F_n+1 = (F₁₋₁)F_n + (F₁)F_n+1 = 0 × F_n + 1 × F_n+1 = F_n+1
これも F_n+1 = F_n+1 という当たり前の内容。

結局【☆☆】自体は、任意の正の整数 x について成り立つ。【☆☆】の n, x をあらためて a, b と書くと:
　　F_a+b = F_b−1F_a + F_bF_a+1
同じことだが、計算の順序を少し変えると:
　　F_a+b = F_a+1F_b + F_b−1F_a

この「加法定理」は初見ではゴチャゴチャした式に思えるが、ものすごいパワーを秘めている。第2部ではこれを別の角度から再び証明し、ツールとして活用する。

【15】　F_2p の件に話を戻そう。「素数の2倍」番目のフィボナッチ数について、例えば F₁₄ = 377 は 14 の倍数 14 × 27 = 378 より 1 小さい（これは p = 7 の例）。一般に:

定理（予想）　p が 7 以上の素数のとき、F_2p は 2p の倍数 ± 1 に等しい。複号については、p の1の位が 1 or 9 ならプラス、3 or 7 ならマイナス。

2p を p に置き換えたシンプル・バージョンは既に証明したので（【9】）、「2倍の番号のフィボナッチ数」の性質を考えれば道が開けそう。

「フィボナッチ数列で遊んでたら、たまたま気付いたこと」なので、この定理に名前や出典はないけれど、自分で見つけたものは、あまり価値のないようなことでも愛着が湧く（笑）。「それを拾って役立てようと、僕は思ったわけでもないが、月夜の晩に拾ったボタンは、どうしてそれが捨てられようか？」

第a項 F_a との関係で、2倍の番号の項、つまり 第2a項 F_2a を考えたい。Binet の式…
　　F_n = (uⁿ − vⁿ)/y, L_n = uⁿ + vⁿ
　　　ここで y = √5, u = (1 + y)/2, v = (1 − y)/2
…に n = 2a を入れると:
　　『は』　F_2a = (u^2a − v^2a)/y = (u^a + v^a)(u^a − v^a)/y = (L_a)(F_a)

〔2個目の等号の根拠〕　U = u^a, V = v^a と置くと u^2a − v^2a = U² − V² = (U + V)(U − V)

すなわち、Fibonacci 数列の第 2a 項は、Fibonacci 数列の第 a 項と Lucas 数列の第 a 項の積に等しい。

〔例〕　F₁₂ = 144 は F₆ = 8 と L₆ = 18 の積。

一方、Lucas 数列の第 p 項（ここでは p を 3 以上の素数とする）について:
　　L_p = u^p + v^p = (1 + y)^p/2^p + (1 − y)^p/2^p
両辺を 2^p 倍して分母を払い、二項定理を使うと^*7:
　　2^p L_p = (1 + py + _pC₂y² + … + _pC_p−1y^p−1 + y^p) + (1 − py + _pC₂y² − … + _pC_p−1y^p−1 − y^p)
y の奇数乗を含む項は、プラスとマイナスが打ち消し合い^*7、y の偶数乗を含む項が残る（p は奇数なので p−1 も偶数）:
　　2^p L_p = 2(1 + _pC₂y² + … + _pC_p−1y^p−1)
y = √5 の偶数乗は、その偶数を 2m とすると (√5)^2m = 5^m なので整数。上の式の両辺を 2 で割ると:
　　2^p−1 L_p = 1 + _pC₂y² + … + _pC_p−1y^p−1
全部の項が整数なので、両辺を mod p で考えることができる。すると:
　　『ひ』　L_p ≡ 1 (mod p)
なぜなら左辺にあった 2^p−1 は、フェルマーの小定理から ≡ 1 (mod p) 、「1倍」なので消滅; 右辺にあった第2項以降は、「一年生の夢」の原理から ≡ 0 (mod p) なので消滅。

*7　前々回の【5】以下（特に【8】）に p = 7 の場合の具体例が詳細に記されている。

すなわち、Lucas 数列の素数番目の項は、その素数の倍数より 1 大きい（直接確かめると p = 2 に対する L₂ = 3 もこの性質を持つので、「3 以上の」素数番目という条件を緩めて、単に「素数番目」といえる）。この命題は、次のように、観測事実と一致する（18 × 11 = 198）。

Lucas 数列の最初の12項（*は素数番目）

n	1	2*	3*	4	5*	6
Ln	1	3	4	7	11	18
n	7*	8	9	10	11*	12
Ln	29	47	76	123	199	322

〔参考〕　『ひ』の逆は成り立たない。つまり Lucas 数列の項が『ひ』の関係を満たすからといって、その項の番号が素数とは限らない。例えば 705 は明らかに 5 の倍数で素数ではないが、L₇₀₅ は 705 の倍数より 1 大きい（L₇₀₅ は 21691339… で始まる148桁の整数）。次を参照:
“Bruckman–Lucas pseudoprimes: n | (L_n−1), where n is composite and L_n = Lucas numbers”
https://oeis.org/A005845

p を 7 以上の素数とすると、F_p ≡ ±1 (mod p) が成り立つ（【9】）。複号については、前述の通り、p が5k±1型（別名10k±1型）ならプラス、5k±2型（素数 2 を度外視すれば10k±3型ともいえる）ならマイナス。この事実と『は』『ひ』を組み合わせると:
　　『ふ』　F_2p ≡ F_p L_p ≡ (±1)(1) ≡ ±1 (mod p)
これは証明したい定理（予想） F_2p ≡ ±1 (mod 2p) と非常に近い。後は mod を p から 2p に変えるだけ。そのためには、F_2p が奇数であることをいえばいいだろう。

〔例〕　7 の倍数より 1 小さい 6, 13, 20, 27, 34, … のうち、奇数のものは 14 の倍数より 1 小さい（偶数のものは 14 の倍数より 8 小さい）。つまり、考えている数が奇数であると断言できるなら、14 の倍数より 1 小さいことが確定し、定理の証明が完了する。

7 以上の任意の素数 p について、F_2p が必ず奇数であり、偶数ではないということ…。【14】で観察したように、n が 3 の倍数のとき F_n は偶数。そして 2p は――「7 以上の素数」と 2 の積なので―― 3 の倍数ではない。これらのことを整理すれば、話が完結する。（下に続く）

〔画像〕　Zürich Hauptbahnhof / Wikipedia ドイツ語版より。パブリックドメイン。

2022-11-12　不思議っち☆フィボナッチ（最終回）　星のコンペイトウ

#数論　#フィボナッチ

【16】　Fibonacci 数列 1, 1, 2; 3, 5, 8; 13, 21, 34; … の第1項と第2項は奇数。それらの和である第3項は、奇数プラス奇数なので、偶数。従って、第4項は、奇数プラス偶数で奇数。第5項も、偶数プラス奇数で奇数。それらの和である第6項は、奇数プラス奇数なので、また偶数。以下同様に「奇・奇・偶」「奇・奇・偶」…のループ。つまり:
　　『へ』　Fibonacci 数列の第□項 F_□ は、□ が 3 の倍数なら偶数、□ が 3 の倍数でなければ奇数。

さて p を7以上の素数とする。『ふ』から F_2p ≡ ±1 (mod p)、つまり F_2p は p の倍数 ±1 の形を持つ。複号については、p が10k±1型ならプラス、10k±3型ならマイナスだが、まずはプラスの場合に話を絞って F_2p を p の倍数 +1 とする。

p の倍数であるからには、何らかの整数 s を使って ps と書ける:
　　『ほ』　F_2p = ps + 1　　（ここで p は10k±1型の素数）
2p は、素数 p の 2 倍なので、3 では割り切れない（3 の倍数じゃない）: 性質『へ』から、F_2p は奇数。そのためには ps が偶数じゃなければならない（もしも ps が奇数だと、『ほ』の右辺は「奇数+1」で偶数になっちゃう）。だから s は偶数…。そこで s = 2t とでも置いて『ほ』に代入すると:
　　F_2p = p(2t) + 1 = (2p)t + 1
この数は、明らかに 2p の倍数より 1 大きい:
　　F_2p ≡ 1 (mod 2p)

〔例〕　p = 11 のとき F_2p = F₂₂ = 17711。ちなみに、この数は F₁₁ = 89 と L₁₁ = 199 の積に等しい（前回の【15】）。さて『ほ』以下に当てはめると、次のように s = 2t = 1610, t = 805 となる:
　　F₂₂ = 17711 = 11(2⋅805) + 1 = 22 × 805 + 1
　　すなわち　F₂₂ ≡ 1 (mod 22)

一方、複号でマイナスを選択して、『ほ』の代わりに…
　　『ぼ』　F_2p = ps − 1　　（ここで p は10k±3型の素数）
…を考えた場合も、符号以外は全く同様に進んで、こうなる:
　　F_2p = p(2t) − 1 = (2p)t − 1
　　F_2p ≡ −1 (mod 2p)

〔例〕　p = 7 のとき F_2p = F₁₄ = 377。ちなみに、この数は F₇ = 13 と L₇ = 29 の積に等しい。『ぼ』以下に当てはめると:
　　F₁₄ = 377 = 7(2⋅27) − 1 = 14 × 27 − 1
　　すなわち　F₁₄ ≡ −1 (mod 14)

以上をまとめると、p が7以上の素数のとき、F_2p は 2p の倍数 ±1 の形を持つ。符号がどちらになるかは、上述の通り。□

性質自体の意味は「簡単な算数」だが、それが成り立つ背後の仕組みは、それほどシンプルでもなかった。舞台裏では、Binet の式が中心となり、無理数の整数乗が活躍（無理数を掛け合わせて整数を表す…へんちくりんな魔法♪）。「一年生の夢」によって整数乗の二項展開が簡約され、オイラーの基準を通じて「5 が mod p の平方剰余か非剰余か」によって、上記の符号の違いが生じる（表面的には、素数 p の1の位の数字によって、振る舞いが変わる）。Fibonacci 数列と Lucas 数列の密接な関係から、F_p と F_2p の関係も明らかになった。

Fibonacci に慣れてる人にとっては、たわいもないことなんだろうけど、正直、最初は右も左も分からなかった…。

【17】　最後に「星のらせんの定理」の前半――「n の倍数番目のフィボナッチ数は、どれも F_n の倍数」という魅惑的な性質――について、[1] による別証明を紹介する。前回【14】後半で紹介したアプローチの方が簡潔だが（しかも同時に逆も証明できる）、以下の方法も面白い。

〔参考文献〕　[1] Verner E. Hoggatt, Jr.: Fibonacci and Lucas Numbers, pp. 37–39
https://www.fq.math.ca/fibonacci-lucas.html

直接 Binet の式を使って…
　　Fibonacci 数（整数）　F_an = (u^an − v^an)/y　が
　　Fibonacci 数（整数）　F_n = (uⁿ − vⁿ)/y　で割り切れること
…を示そう^*8。U = uⁿ, V = vⁿ と置くと、示すべき命題はこうなる:
　　『ま』　F_an = (U^a − V^a)/y　が　F_n = (U − V)/y　で割り切れる
次の恒等式^*9を利用する:
　　U^a − V^a = (U − V)(U^a + U^a−1V + U^a−2V² + … + U²V^a−2 + UV^a−1 + V^a)
その両辺を y で割れば:
　　『み』　(U^a − V^a)/y = (U − V)/y × 残りの因子　　ただし
　　残りの因子 = U^a + U^a−1V + U^a−2V² + … + U²V^a−2 + UV^a−1 + V^a
『み』左辺 = F_an、『み』右辺第1因子 = F_n なので（『ま』参照）、残りの因子が整数であることを示せば、F_an は F_n の倍数ということが確定する。

*8　an は自然数 n の a 倍（a: 自然数）。 y, u, v の意味は前回と同じ: y = √5, u = (1 + y)/2, v = (1 − y)/2。

*9　「xⁿ − yⁿ は x − y で割り切れる」参照。

残りの因子のうち、両端の2項の和…
　　『む』　U^a + V^a = (uⁿ)^a + (vⁿ)^a = u^an + v^an
…は、Lucas 数列の第an項 L_an に他ならない（Binet の式より）。それは、もちろん整数。

残りの因子が4項以上ある場合、残りの因子の左から2番目の項と右から2番目の項の和は、こうなる:
　　『め』　U^a−1V + UV^a−1 = UV(U^a−2 + V^a−2)
『め』では、左辺の2項の共通因数 UV をくくり出した。『め』右辺の丸かっこ内は、『む』と同様に Lucas 数列の項と等しくなる:
　　U^a−2 + V^a−2 = (uⁿ)^a−2 + (vⁿ)^a−2 = u^(a−2)n + v^(a−2)n = L_(a−2)n
一方、その丸かっこの前にある UV すなわち (u^a)(v^a) = (uv)^a は 1 or −1 に等しい。というのも…
　　『も』　uv = [(1 + y)/2][(1 − y)/2] = (1 + y)(1 − y) / (2⋅2) = (1 − y²)/4
　　= (1 − 5)/4 = −1　　← y = √5 だから y² = 5
…なので、(uv)^a = (−1)^a は a が偶数なら +1、a が奇数なら −1。結局、『め』の和は、とある Lucas 数の ±1 倍で、符号がどっちになるかはともかく、整数。

残りの因子が6項以上ある場合、残りの因子の左から3番目の項と右から3番目の項の和は、こうなる:
　　『や』　U^a−2V² + U²V^a−2 = U²V²(U^a−3 + V^a−3)
『む』『め』と同様に、丸かっこ内の U^a−3 + V^a−3 は、とある Lucas 数に等しい。UV = 1 or −1 なので、U²V² = (UV)² = 1。結局、『や』の和も、とある Lucas 数であり、整数。

以下同様に進めて、残りの因子が偶数個の項を持つ場合、左端と右端から順に一つずつペアにして考えると、各ペアの和は Lucas 数またはその −1 倍になり、整数。すなわち（それら全体の和である）残りの因子自体も、整数。一方、残りの因子が奇数個の項を持つ場合、このように両端から一つずつペアにすると（各ペアの和は整数）、ど真ん中の項が（ペアになる相手がないまま）残る。このケースについては、
　　「ど真ん中の項がそれ自身、整数であること」
を示せば、やはり「全体の和は整数」という結論になり、証明が完了する…。

残りの因子が奇数個の項なら、次のようなパターンになる。
　　3項の場合（a = 3）　　U² + UV + V²
　　5項の場合（a = 5）　　U⁴ + U³V + U²V² + UV³ + V⁴
　　7項の場合（a = 7）　　U⁶ + U⁵V + U⁴V² + U³V³ + U²V⁴ + UV⁵ + V⁶
　　えとせとら
U や V の右肩に乗る一番でかい指数は、一定の偶数――正確に言えば a−1。U については、左端から右に進むにつれて指数が1ずつ減り、V については、右端から左に進むにつれて指数が1ずつ減る…。だからど真ん中では、どちらの指数も a−1 のちょうど半分（中間地点なので）。どっちもちょうど半分なので、ど真ん中では U の指数と V の指数が等しくなる。 a−1 の半分を b とすると（a は奇数なので a−1 は偶数、b = (a−1)/2 は割り切れて整数）:
　　ど真ん中の項 = U^bV^b = (UV)^b
『め』以下で見たように UV = 1 or −1。ど真ん中の項は、UV = 1 の場合には (1)^b で常に 1 に等しく、UV = −1 の場合には (−1)^b で、この数は（b の偶・奇に応じて）1 か −1 に等しいが、いずれにしても整数。…これで証明が完了した。□

例えば F₂₁ = 10946 が F₇ = 13 で割り切れる仕組みは、次の通り（n = 7, a = 3）:
　　F₂₁ = [(u⁷)³ − (v⁷)³]/y = (U³ − V³)/y　　ここで U = u⁷, V = v⁷
　　つまり　F₂₁ = (U³ − V³)/y = (U − V)(U² + UV + V²)/y = (U − V)/y × 残りの因子
　　ただし　残りの因子 = U² + UV + V²
従って F₂₁ は、次の整数の「残りの因子」倍:
　　F₇ = (u⁷ − v⁷)/y = (U − V)/y
ところが:
　　残りの因子 = U² + UV + V²
　　 = (U² + V²) + UV　← 両端から1個ずつペアに。ど真ん中の項はペアにならない
　　 = [(u⁷)² + (v⁷)²] + (uv)⁷ = L₁₄ + (−1)⁷　← uv = −1（『も』参照）
　　 = 843 − 1 = 842

実際、10946 = 13 × 842。あるいは、同じことだが、F₂₁ = F₇(L₁₄ − 1)。

星のらせんのフィボナッチ。不思議なコンペイトウ…カリッ☆

（第1部・完）

---

2022-11-13　フィボナッチ数列の加法定理　F_a+b = ？

#数論　#フィボナッチ

Fibonacci 数列の a 番目の項（例えば a = 3 として F₃ = 2）を考え、b 番目の項（例えば b = 7 として F₇ = 13）を考えるとき、a+b 番目の項 F_a+b ――今の例では a+b = 10 なので F₁₀ = 55 という項――は F_a, F_b とどういう関係にあるのだろうか。

Fibonacci 数列の最初の16項

n	1	2	3	4	5	6	7	8
Fn	1	1	2	3☆	5	8★	13	21
n	9	10	11	12	13	14	15	16
Fn	34	55	89	144	233	377	610	987

F_a の次の項を ☆ とする（上の例では ☆ = F₄ = 3）。F_b の一つ手前の項を ★ とする（上の例では ★ = F₆ = 8）。すると
　　F_a+b = ☆F_b + ★F_a
が成り立つ！　言い換えれば:
　　F_a+b = F_a+1F_b + F_b−1F_a　　‥‥①

〔例1〕　a = 3, b = 7:
　　F₁₀ = F₃₊₇ = F₄F₇ + F₆F₃
　　 = 3 × 13 + 8 × 2 = 39 + 16 = 55

〔例2〕　a = 7, b = 3 だって a+b = 10 になる。そういうふうに、ひっくり返したらどうなるのだろう。
　　F₁₀ = F₇₊₃ = F₈F₃ + F₂F₇ = 21 × 2 + 1 × 13 = 55
おおっ、ちゃんと同じになる！！！　a+b = 10 になる a, b は他にもいっぱいあるし、別に和が10でなくても好きな a, b で構わない。自分でいろいろ試してみよう！

①については「不思議っち☆フィボナッチ（第5話）」【14】で既に証明したが、次回、別の角度から再考する。

①はすてきだけど、何かちょっとゴチャゴチャしてるよね。実はもっときれいな式も、成り立つ。次のように Lucas（ルュカ）数列とペアで考えると――
　　F_a+b = (F_aL_b + L_aF_b)/2　　‥‥②

Lucas 数列の最初の16項

n	1	2	3	4	5	6	7	8
Ln	1	3	4	7	11	18	29	47
n	9	10	11	12	13	14	15	16
Ln	76	123	199	322	521	843	1364	2207

〔例3〕　a = 3, b = 7 に②を適用:
　　F₁₀ = (F₃L₇ + L₃F₇)/2 = (2 × 29 + 4 × 13)/2 = (58 + 52)/2 = 55

何の役に立つのか分からないけど、①も②も面白い。何の役にも立たないからこそ、純粋に面白い…というべきかもしれない。（下に続く）

2022-11-14　フィボナッチ数列の加法定理（その2）　①の証明

#数論　#フィボナッチ　#心の魔法

セキュリティーのやけに厳重な高層ビルがあるとする。各階ごとに通行証が必要なのだ。5階に行きたければ、5階の通行証。13階に行きたければ、13階の通行証。めんどくせー！

だがもし「ある階の通行証と、次の階の通行証を提示すれば、自動的にそのまた次の階の通行証をもらえる」というシステムだとすればどうだろう。例えば「5階の通行証」と「6階の通行証」を提示すれば、自動的に「7階の通行証」をもらえる…。

このシステムには、明らかに抜け穴がある！　何とかして「1階の通行証」と「2階の通行証」さえ手に入れれば、それを提示して「3階の通行証」をもらえるし、既に持ってる「2階の通行証」と今もらった「3階の通行証」を提示して「4階の通行証」をもらえるし…というふうに、無限ループ的に、どの階にも自由に行けることになる。

フィボナッチ数列に対する再帰（さいき）法――現代の教科書的用語でいえば帰納（きのう）法――は、このトリックを利用する。それには、次の三つのことを達成すればいい:

1. 1階の通行証をゲット
2. 2階の通行証をゲット
3. 「ある階と次の階の通行証があれば、そのまた次の階の通行証も手に入る」ことを示す

前回、次の性質を観察した: a+b 番目のフィボナッチ数 F_a+b は、a 番目のフィボナッチ数 F_a と b 番目のフィボナッチ数 F_b を使って、
　　F_a+b = ☆F_b + ★F_a
と書くことができる。ここで ☆ は F_a の次の項、★ は F_b の手前の項。要するに:
　　『ア』　F_a+b = F_a+1F_b + F_b−1F_a

今 a を任意の定数として、b = 1 とすると、『ア』はこうなる:
　　『イ』　F_a+1 = F_a+1F₁ + F_1-1F_a = F_a+1
　　（なぜなら F₁ = 1, F_1-1 = F₀ = 0）
『イ』は F_a+1 = F_a+1 という当たり前の内容。「1階への通行証」ゲットだぜ～ｗ

引き続き a を任意の定数として、今度は b = 2 とすると、『ア』はこうなる:
　　F_a+2 = F_a+1F₂ + F₂₋₁F_a = F_a+1 + F_a
　　（なぜなら F₂ = 1, F₂₋₁ = F₁ = 1）
これは「F_a と F_a+1 を足すと F_a+2 になる」というフィボナッチ数列の性質そのもの。こりゃまた当たり前。「2階への通行証」ゲットだぜ～。簡単過ぎて、張り合いがないぞ。

後は3番目のことを証明すればいい。今度は b = 1 や b = 2 ではなく、漠然と b = x をとある正の整数としよう。このとき、『ア』はこうなるのだが…
　　『ウ』　F_a+x = F_a+1F_x + F_x−1F_a
これは「x 階の通行証」を持ってる、って意味。同様に「x+1 階の通行証」も持ってる…ってことを式で書くと（『ア』に b = x+1 を代入）:
　　F_a+(x+1) = F_a+1F_x+1 + F_(x+1)−1F_a　つまり
　　『エ』　F_a+x+1 = F_a+1F_x+1 + F_xF_a
さらに「x+2 階の通行証」も与えられた…ってことも式で書くと（『ア』に b = x+2 を代入）:
　　F_a+(x+2) = F_a+1F_x+2 + F_(x+2)−1F_a　つまり
　　『オ』　F_a+x+2 = F_a+1F_x+2 + F_x+1F_a
『ウ』と『エ』が事実なら『オ』が成り立つ――ということを示せば、それはすなわち、
　　「x 階の通行証」と「x+1 階の通行証」があれば、自動的に「x+2 階の通行証」が手に入る
という意味になって、証明が完了する。「『ウ』と『エ』が事実なら」は単なる仮定なので、仮定上の議論として、『ウ』と『エ』はすでに成り立っているとして構わない！

フィボナッチ数列では、各項は直前の2項の和なので、F_a+x と F_a+x+1 を足すと、F_a+x+2 になる（分かりにくければ a+x を n と置いてみよう）。そういう目で『ウ』『エ』『オ』を眺めると『ウ』の左辺と『エ』の左辺の和が『オ』の左辺に等しいことに気付く…。むむ、これは（ピキーン）！　等しいもの同士の和はもちろん等しいので、等式『ウ』『エ』について、左辺同士の和と、右辺同士の和は等しい:
　　F_a+x + F_a+x+1 = F_a+1F_x + F_x−1F_a + F_a+1F_x+1 + F_xF_a
なんかゴチャゴチャして難しそうだが、この左辺が F_a+x+2 に等しいことは、上記の通り。右辺については、次のように F_a と F_a+1 が共通因数になっている:
　　F_a+x+2 = F_a+1F_x + F_x−1F_a + F_a+1F_x+1 + F_xF_a
並び替えて整理すると:
　　F_a+x+2 = F_a+1F_x + F_a+1F_x+1 + F_x−1F_a + F_xF_a
　　F_a+x+2 = F_a+1(F_x + F_x+1) + F_a(F_x−1 + F_x)
フィボナッチ数列の性質上、一つ目の丸かっこ内の F_x + F_x+1 は F_x+2 に等しい; 二つ目の丸かっこ内の F_x−1 + F_x は F_x+1 に等しい。
つまり…
　　F_a+x+2 = F_a+1(F_x+2) + F_a(F_x+1)
…となって『オ』が成り立つ。

証明が完了した！

誤解のないように確認しておくと、今われわれは、『オ』そのものを証明したわけではない: 単に仮定の話として…
　　もし『ウ』と『エ』が成り立つなら、そのときには『オ』も成り立つ
…ということを証明したに過ぎない。でも、それで十分。この「仮定上の話」が事実であることと、それプラス、実際に「1階の通行証」と「2階の通行証」をゲットしていることから、合わせ技として、任意の階への通行証が手に入る。

〔解説〕　「『ウ』＆『エ』が成り立つなら『オ』も成り立つ」は、仮定上の話に過ぎない。けれど、仮定上の話とはいえ、「『ウ』＆『エ』が成り立つなら」という仮定が満たされるなら、『オ』が成り立つのは動かぬ事実。そして x = 1 つまり F_a+1 & F_a+2 について、実際に『ウ』＆『エ』が成り立つことを事前に別の話として、直接証明しているのだから、この「仮定上の話」の仮定は、少なくとも F_a+1 & F_a+2 については真実であり、だから『オ』によって F_a+3 についても、加法定理①（つまり『ア』）が成り立つ。――すると F_a+1 & F_a+2 & F_a+3 について①が証明されたことになる。その結果、前記の「仮定上の話」は x = 2 つまり F_a+2 & F_a+3 についても真実であり、だから『オ』によって F_a+4 についても、①が成り立つ。――以下同様に無限ループが発生して、結局、x がどんな正の整数だとしても F_a+x について①が成り立つ。つまり任意の F_a+b について、①が成り立つ。

何やら変な理屈のようで、最初は頭が痛くなるかもしれないが、分かってみると別に大したことでもない。

でも「分かってみると」といわれても…

どうすれば「分かってみる」ことができるの？

それが一番肝心なことなのに、学校では教えてくれない…。考え方としては、どんな場合でも、とりあえず「私は今からこれが分かるようになる」と、思ってみよう。「もしかしたら分かるかも…」、いや「分かって当たり前」と思ってみる（思ってみるだけなら、カンタンでしょ）。そういう気持ちで取り組むと、心に余裕が生まれ、物事はちょっとだけ易しくなる。その「ちょっと」の差が、大きな違いになる（逆に「私には無理」「私はばかだから、理解できるわけない」みたいな考え方をすると、本当にそうなってしまうので注意）。

式①については、「不思議っち☆フィボナッチ（第5話）」【14】でも【☆】として、帰納法を使って証明している。いろんな角度から考えると、参考になるかも…

ともあれ、「フィボナッチ数列の加法定理」①が証明された。分からなかったことが分かるようになるのは、うれしい！

でも②の証明は、ちょっと難しそうだ…。いや、きっと何とかなるだろう。（下に続く）

2022-11-17　フィボナッチ数列の加法定理（その3）　F₅₀を筆算しよう

#数論　#フィボナッチ

その2では、F_a+b = F_a+1F_b + F_b−1F_a を証明した。次のように整理すると、分かりやすいかも…

便宜上、Fibonacci 数列の第x項と第y項の積を f(x, y) で表すことにする:
　　f(x, y) = F_xF_y
このとき、例えば F₄₊₇ を計算するには、足し算されている 4, 7 のうち、どちらか一方だけ（どっちでもOK）に 1 プラスしたペアを f に入れて
　　f(5, 7)
を考え、次にその両方の数字から 1 を引いた
　　f(4, 6)
を考え、この二つを足し合わせればいい:
　　F₄₊₇ = f(5, 7) + f(4, 6) = F₅F₇ + F₄F₆
　　= 5 × 13 + 3 × 8 = 65 + 24 = 89
これはもちろん F₁₁ = 89 と一致する。

Fibonacci 数列の最初の16項

n	1	2	3	4	5	6	7	8
Fn	1	1	2	3	5	8	13	21
n	9	10	11	12	13	14	15	16
Fn	34	55	89	144	233	377	610	987

もし 4, 7 の 7 の側に 1 プラスすると:
　　F₄₊₇ = f(4, 8) + f(3, 7) = F₄F₈ + F₃F₇
　　= 3 × 21 + 2 × 13 = 63 + 26 = 89

一般に、こうなる。
　　『カ』　F_a+b = f(a+1, b) + f(a, b−1) = F_a+1F_b + F_aF_b−1
内容的には、既に証明した式の右辺第2項の、掛け算の順序を変えただけ。

特に、a と b がどちらも同じ整数（a = n, b = n とする）の場合:
　　『キ』　F_2n = F_n+n = F_n+1F_n + F_nF_n−1 = F_n(F_n+1 + F_n−1)
Fibonacci 数列の性質上
　　『ク』　F_n+1 = F_n−1 + F_n
なので、それを『キ』の右辺に代入すると:
　　『ケ』　F_2n = F_n((F_n−1 + F_n) + F_n−1) = F_n(2F_n−1 + F_n)
ところで『ク』を変形すると F_n−1 = F_n+1 − F_n となる。それを『キ』に代入して、こう書くこともできる:
　　『コ』　F_2n = F_n(F_n+1 + (F_n+1 − F_n)) = F_n(2F_n+1 − F_n)
さらに『ク』を F_n = F_n+1 − F_n−1 と変形して『キ』に代入すると:
　　『サ』　F_2n = (F_n+1 − F_n−1)(F_n+1 + F_n−1) = (F_n+1)² − (F_n−1)²

『ケ』『コ』によると、Fibonacci 数列の第n項と、その前（またはその次）の項が分かるなら、第2n項を一気に計算できる！

〔例〕　n = 5 のとき『ケ』を使うと F₁₀ = F₅(2F₄ + F₅) = 5(2 × 3 + 5) = 55
『コ』を使うと F₁₀ = F₅(2F₆ − F₅) = 5(2 × 8 − 5) = 55
ちなみに『サ』を使うと F₁₀ = (F₆)² − (F₄)² = 8² − 3² = 55　←あまり役立たないかもしれないが、きれい

さて、『カ』で a = n, b = n+1 とすると、面白いことになる:
　　F_n+(n+1) = f(n+1, n+1) + f(n, n)　すなわち
　　『シ』　F_2n+1 = (F_n)² + (F_n+1)²

なかなかいかす式だ…。第n項と第n+1項が分かるなら、第2n+1項も一気に計算でき、しかもそれは、第n項の平方と第n+1項の平方の和に等しい！

〔例〕　n = 5 のとき F₁₁ = (F₅)² + (F₆)² = 5² + 8² = 25 + 64 = 89
［F₁₁ の 11 は n = 5 の2倍プラス1］
n = 6 のとき F₁₃ = (F₆)² + (F₇)² = 8² + 13² = 64 + 169 = 233
これは面白い！

同様の発想から、『カ』で a = n−1, b = n とすると:
　　F_(n−1)+n = f(n, n) + f(n−1, n−1)　すなわち
　　『ス』　F_2n−1 = (F_n)² + (F_n−1)²

『シ』との対称性が美しい！　第n項と第n−1項が分かるなら、第2n−1項も一気に計算でき、しかもそれは、第n項の平方と第n−1項の平方の和に等しい。

〔例〕　n = 5 のとき F₉ = (F₅)² + (F₄)² = 5² + 3² = 25 + 9 = 34
［F₉ の 9 は n = 5 の2倍マイナス1］
n = 6 のとき F₁₃ = (F₆)² + (F₅)² = 8² + 5² = 64 + 25 = 89

これらを使って、Fibonacci 数列の第50項 F₅₀ を求めてみよう！

作戦会議…。やり方はいろいろありそうだが、とりあえず単純に n = 25 の F₂₅ を求めて、F_2n = F₅₀ としましょうか…。『ケ』 or 『コ』を使うには、F₂₅ だけではなく、F₂₄ or F₂₆ が必要。24 の方が簡単そう。よし、F₂₄ と F₂₅ を求めよう。それには F₁₂ と F₁₃ に『コ』『シ』を適用すればいい。――再び『コ』『シ』により、それは F₆ と F₇ に帰着され、それがさらに F₃ と F₄ に帰着される。

Fibonacci 数列の開始部分は 1, 1, 2, 3, 5 だから F₃ = 2 で F₄ = 3。これを出発点とすると、まず…

『コ』から　F₆ = F₃(2F₄ − F₃) = 2(2 × 3 − 2) = 2 × 4 = 8
『シ』から　F₇ = (F₃)² + (F₄)² = 2² + 3² = 4 + 9 = 13

今得られた結果に、再び『コ』『シ』を適用:

『コ』から　F₁₂ = F₆(2F₇ − F₆) = 8(2 × 13 − 8) = 8 × 18 = 144
『シ』から　F₁₃ = (F₆)² + (F₇)² = 8² + 13² = 64 + 169 = 233

ちゃんと上の表と合ってる。作戦の方針に間違いはないようだ。ここから先は数がでかくなりそうだが、気合を入れて慎重に前進しよう。

『コ』から　F₂₄ = F₁₂(2F₁₃ − F₁₂) = 144(2 × 233 − 144) = 144(466 − 144) = 144 × 322

忙しい現代人は、ここで電卓を取り出したくなるかもしれない。だが、修行の道は厳しいのだ。工夫して暗算する:
F₂₄ = 144 × 322 = 144 × 300 + 144 × 20 + 144 × 2 = (150 − 6) × 300 + 2880 + 288
= 45000 − 1800 + (3000 − 120) + 288 = 45000 + 3000 − 1920 + 288
= 48000 − 2000 + 80 + 288 = 46000 + 368 = 46368
［もちろん普通に筆算してもいい］

F₂₄ は F₈ = 21 の倍数なので（星のらせん階段）、3 でも 7 でも割り切れるはず。上で得た数値 46368 が、3 の倍数かどうかは、「3の倍数を無視した桁の和」すなわち 4+6+3+6+8 が「3の倍数」かどうかを見ればいい。46368 が 7 で割り切れるかどうかは、頭の中で筆算の割り算をしてみよう。数秒の検算の手間を惜しんではならない。

一方『シ』から　F₂₅ = (F₁₂)² + (F₁₃)² = 144² + 233²
= (14400 + 5760 + 576) + (46600 + 6990 + 699) = 20736 + 54289 = 75025

「5の倍数」番目の Fibonacci 数は5の倍数なので、上の結果は合ってる感じ（少なくとも、明らかな間違いではない）。

いよいよ F₅₀ を…。今までと同じ再帰だと F₄₈ と F₄₉ を求める計算になるが、今度はそれとは違う。『ケ』の出番。

『ケ』から　F₅₀ = F₂₅(2F₂₄ + F₂₅) = 75025(2 × 46368 + 75025) = 75025(92736 + 75025) = 75025 × 167761

これは筆算するしかないな…。ひっくり返して6桁×5桁にした方が簡単そうだが、このまま5桁×6桁でやると、実質5桁×1桁の掛け算2回で済む（下記 A は75025をコピーするだけ、B と C はそれぞれコピペで再利用できる）。ただしその後の足し算が少し面倒かな？　まあ、やってみましょう。

        75 025 A = 75025 x 1
     4 501 50  B = 75025 x 6
    52 517 5   C = 75025 x 7
   525 175     C
 4 501 50      B
 7 502 5       A
==============
         1 025
     2 268
 1 584
11
==============
12 586 269 025　【？】

5の倍数なので、少なくとも「明らかな間違い」ではないが、確信が持てない。そこで、F₄₈ と F₄₉ を求めて、足し算してみましょう。

『コ』から　F₄₈ = F₂₄(2F₂₅ − F₂₄) = 中略 = 4807526976
『シ』から　F₄₉ = (F₂₄)² + (F₂₅)² = 中略 = 7778742049
F₅₀ = F₄₈ + F₄₉ = 4807526976 + 7778742049 = 12586269025
【？】と一致した。このステップに、計算ミスはないようだ。問題は、その土台となってる F₂₄ と F₂₅ の値が正しいかどうかだが、数列の定義に従って直接計算すると、これらもOK。

〔参考〕　さらなるチェックとして、F₅₀ は F₁₀ = 55 の倍数だから、11 の倍数になるはず。11 の倍数かどうかを見るには、「奇数番目の桁の和」と「偶数番目の桁の和」の差が 11 の倍数になるかどうかを見ればいい。12586269025 の場合、奇数番目・偶数番目どちらの桁の和も 23、それらの差 0 は 11 の倍数だから、数値自体も 11 の倍数。

結論として:
　　F₅₀ = 125億8626万9025
「いーニャンコ、ハロー二郎、くれニャンコ」

工夫すれば、もっと楽な方法もあるのかな…？

結果だけ書くとサクサクやってるみたいだけど、実際にはコンピューターのせいで（？）計算力が低下してて、何度も計算ミスをしながら、検算で気付いてやり直し、ようやくこの値を得た。「コンピューターにやらせれば一瞬なのに、なぜわざわざ筆算するの？」という意見もあるかもしれないが、たまには筆算もしないとね！

加法定理①で遊ぶのは、とりあえずこのくらいにして、次は Lucas 数列を使う②の研究に進みたい。その後で、再び①に戻り「Binet の式からの（帰納法を使わない）直接証明」も試みたい。（下に続く）

〔注意〕　関数 f は、説明の便宜上のもので、一般的に使われる記法ではない。

〔参考文献〕　式『コ』『ス』は Wikipedia に記載されている（導出法は異なる）:
https://en.wikipedia.org/wiki/Fibonacci_number
『サ』は Воробьев: Числа Фибоначчи の16ページに記載されている:
https://math.ru/lib/book/plm/v06.djvu

2022-11-21　フィボナッチ数列の加法定理（その4）　②の証明

#数論　#フィボナッチ

Fibonacci 数列の第10項 F₁₀ = 55 は、なぜか 1 + 2 + 3 + … + 10 = 55 に等しい。しかも対応する Lucas 数が L₁₀ = 123 なのが面白い！

F₁₂ が 12² = 144 に等しいことも、印象に残る。これらは周期性のない「偶然」だが…

Fibonacci 数列と Lucas 数列の最初の16項

n	1	2	3	4	5	6	7	8
Fn	1	1	2	3	5	8	13	21
Ln	1	3	4	7	11	18	29	47
n	9	10	11	12	13	14	15	16
Fn	34	55	89	144	233	377	610	987
Ln	76	123	199	322	521	843	1364	2207

Fibonacci 数列の加法定理①によると、a+b 番目の Fibonacci 数は f(a+1, b) と f(a, b−1) の和。ただし f(x, y) = F_xF_y とする。この性質の応用は F₅₀ の実際の計算にも役立ったが、出発点になる式は、若干ゴチャゴチャしている。

Lucas 数列と組み合わせて g(x, y) = F_xL_y とするなら、同じ第 a+b 項は g(x, y) と g(y, x) の和の半分（言い換えれば平均）。

〔例〕　F₁₀₊₂ = (F₁₀L₂ + F₂L₁₀)/2 = (55 × 3 + 1 × 123)/2 = (165 + 123)/2 = 144

具体的な計算に便利かはともかく、①よりきれいな式だ。理論的研究には役立つかも…

①の証明をまねて、最初に帰納法を使って②（上記の計算法）を証明したい（その後で、帰納法を使わずに直接証明する）。割り算は邪魔くさいので、あらかじめ②の両辺を2倍して、次の形にしておく:
　　『タ』　2F_a+b = F_aL_b + F_bL_a

【1】　第一に b = 1 とすると、L_b = 1, F_b = 1 なので『タ』はこうなる:
　　『チ』　2F_a+1 = F_a + L_a
この式によると、とあるフィボナッチ数 F_a と対応するルュカ数 L_a の和は、一つ後のフィボナッチ数 F_a+1 の2倍。例えば F₃ = 2 と L₃ = 4 の和 6 は次のフィボナッチ数 F₄ = 3 の2倍だし、F₄ = 3 と L₄ = 7 の和 10 は次のフィボナッチ数 F₅ = 5 の2倍。もっと露骨に言えば、n = 1, 2, 3, … に対して F_n + L_n は「フィボナッチ数列（ただし第2項からスタート）の2倍」に等しい:
　　2, 4, 6, 10, 16, 26, …　　←フィボナッチ数列 1, 2, 3, 5, 8, 13, … の各項を2倍したものと同じ

さて n = 3, 4, 5, … に対して F_n も L_n も、それぞれ直前の2項の和が各項の値になり、その振る舞いは最初の2項（F₁ = 1, F₂ = 1; L₁ = 1, L₂ = 3）によって決まる――最初の2項が決まれば、第3項やそれ以降の値は確定的。
　　F₃ = F₁ + F₂, F₄ = F₂ + F₃, etc.
　　L₃ = L₁ + L₂, L₄ = L₂ + L₃, etc.
このような2種類の数列について、対応する項同士の和 F_n + L_n も確定的で、「直前の2項の和」という性質を持つ:
　　F₃ + L₃ = (F₁ + L₁) + (F₂ + L₂),
　　F₄ + L₄ = (F₂ + L₂) + (F₃ + L₃), etc.
他方、フィボナッチ数列の各項の2倍は、もちろん確定的な値を持ち、それぞれ（3番目以降の項なら）直前の2項の和という性質を持つ。例えば:
　　F₃ = F₁ + F₂　だから　2F₃ = 2F₁ + 2F₂
すると『チ』は、最初の2項（a = 1, 2）について左辺と右辺が一致するなら、全部の項が確定的に一致。現実にも…
　　a = 1 のとき 2F₂ = F₁ + L₁　つまり　2 × 1 = 1 + 1
　　a = 2 のとき 2F₃ = F₂ + L₂　つまり　2 × 2 = 1 + 3
…は事実なので、『チ』は任意の正の整数 a に対して、正しい。

【2】　第ニに b = 2 とすると、L_b = 3, F_b = 1 なので『タ』はこうなる:
　　『ツ』　2F_a+2 = 3F_a + L_a
この式によると、とあるフィボナッチ数 F_a の次の次のフィボナッチ数 F_a+2 の2倍は、「もともとのフィボナッチ数 F_a の3倍」と「対応するルュカ数 L_a」の和に等しい。例えば a = 3 なら 3F₃ + L₃ = 3 × 2 + 4 = 10 だが、これは F₅ = 5 の2倍。フィボナッチ数列の各項を3倍した数列は、依然として「各項は直前の2項の和」という性質を持つし、その値に L_a を足したものも（L_a 自体が「各項は直前の2項の和」という性質を持つので）、同じ性質を持つ。だから『チ』同様、『ツ』も、最初の2項 a = 1, 2 について左辺と右辺が一致するなら、全部の項について一致する。現実にも…
　　a = 1 のとき 2F₃ = 3F₁ + L₁　つまり　2 × 2 = 3 × 1 + 1
　　a = 2 のとき 2F₄ = 3F₂ + L₂　つまり　2 × 3 = 3 × 1 + 3
…は事実なので、『ツ』も任意の正の整数 a に対して、正しい。

【3】　第三に b = x を任意の正の整数として、「もし
　　『テ』　2F_a+x = F_aL_x + F_xL_a
　　『ト』　2F_a+x+1 = F_aL_x+1 + F_x+1L_a
が成り立つなら、
　　『ナ』　2F_a+x+2 = F_aL_x+2 + F_x+2L_a
も成り立つ」ことを示せば、帰納法による証明が完成する。そして、示すべきことが成り立つのは、①の証明と同様に考えれば、ほぼ一目瞭然: 『テ』と『ト』の左辺同士の和が『ナ』の左辺、右辺同士の和が『ナ』の右辺。実際、『テ』と『ト』の右辺同士の和について、第1項同士の和は
　　F_a(L_x + L_x+1) = F_a(L_x+2)
だし、第2項同士の和は
　　(F_x + F_x+1)L_a = (L_x+2)L_a
となる。両方の項を併せれば、『ナ』の右辺と一致。□

【4】　以上の証明法は重要な観察を含んでいて一度はやる価値があるのだろうが、どうもまだるっこい。『タ』の
　　2F_a+b = F_aL_b + F_bL_a　（☆）
は比較的シンプルな式なので、帰納法なんていうからめ手ではなく Binet の式を使って直接計算した方が楽では…？

今 y = √5, u = (1 + y)/2, v = (1 − y)/2 として（☆）を Binet の式で表現すると:
　　2(u^a+b − v^a+b)/y = (u^a − v^a)/y × (u^b + v^b) + (u^b − v^b)/y × (u^a + v^a)
両辺を y 倍して分母を払うと:
　　『ニ』　2(u^a+b − v^a+b) = (u^a − v^a)(u^b + v^b) + (u^b − v^b)(u^a + v^a)
この右辺を展開すると8個の項が出てくる:
　　『ニ』の右辺第1項 = (u^au^b + u^av^b − v^au^b − v^av^b)
　　『ニ』の右辺第2項 = (u^bu^a + u^bv^a − v^bu^a − v^bv^a)
『ニ』の右辺は上と下の和だが、丸かっこ内の第2・第3項は上下の和が合計ゼロで、都合よく打ち消し合う:
　　『ニ』の右辺 = (u^au^b − v^av^b) + (u^bu^a − v^bv^a) = 2(u^a+b − v^a+b)
…これは『ニ』の左辺に等しい。証明完了。□

こっちの方が簡潔で気持ちいいかも（お好みで）。

【5】　ところで Lucas 数列の「第0項」は何だろうか？　Fibonacci の場合、無邪気に「第0項だから 0 でしょ」って感じで
　　0, 1, 1, 2, 3, 5, 8, 13, …
としても、右から3番目にある「1」は直前の「0」と「1」の和になって、数列の性質が保たれる。だけど Lucas 数列の場合、
　　□, 1, 3, 4, 7, 11, 18, 29, …
の □ が 0 だとすると、「0 + 1 = 3」となり、つじつまが合わない。□ + 1 = 3 になってほしいんだから、□ = 2 だろう:
　　2, 1, 3, 4, 7, 11, 18, 29, …
すなわち Lucas 数列の「第0項」は L₀ = 2 ―― 第0項から考えると、この数列は一方的に増加せず、いったん減ってから増加に転じる！

この「第0項」を活用すると、b = 1, 2 の代わりに b = 0, 1 から帰納法の証明をスタートできる。b = 1 のケースは【1】で扱ったので、要するに【2】をやめて、代わりに b = 0 のケースを考えればいい。『タ』の
　　2F_a+b = F_aL_b + F_bL_a
は、b = 0 のとき 2F_a+0 = 2F_a + 0 となる（なぜなら L₀ = 2, F₀ = 0）。この式は 2F_a = 2F_a という意味なので、直ちに明らか。【2】のまだるっこい議論は不要に。Binet の式を使った直接証明ほどではないにせよ、いくらかスッキリ。

ここから、どこに行きましょか？　次は何して遊ぶ？

今回の経験からすると、加法定理①も、帰納法を使わず Binet の式から直接行けるはず。小さなことだが、気になる道…

それと「n の倍数番目の Fibonacci 数は、F_n の倍数」という、ちょ～美しい性質（「星のらせん」）。この性質について、Hardy & Wright では、上記『タ』を使った証明が紹介されているが、その証明法は必ずしも最適ではなく、①経由で同じことをやった方が簡単になるようだ。

2022-11-23　シャア専用フィボナッチ公式　通常の3倍ｗ

#数論　#フィボナッチ

以前「第2n項」関連の公式を繰り返し使い、11桁ある F₅₀ の筆算という苦行をした。今回は「第3n項」を軸とする別のショートカットを試みたい。フィボナッチ数列の隣り合う2項を B = F_n, C = F_n+1 とすると:
　　『ヌ』　F_3n+1 = B²(3C − B) + C³
　　『ネ』　F_3n+2 = C²(3B + C) + B³

B = F₅ = 5, C = F₆ = 8 を代入すると（n = 5）:
　　F₁₆ = 25 × 19 + 8³ = 475 + 512 = 987
　　F₁₇ = 64 × 23 + 5³ = 1472 + 125 = 1597
これらをあらためて B, C として『ネ』を使うと（n = 16）:
　　F₅₀ = 1597²(3 × 987 + 1597) + 987³ = 12586269025

ものすごい勢いで F₅₀ に到達した。ラマヌジャンもびっくり！

『ヌ』『ネ』は、加法定理で a = 2n として b = n+1 or n+2 としただけ。『シ』『コ』から…
　　F_2n+1 = (F_n)² + (F_n+1)² = B² + C²
　　F_2n = F_n(2F_n+1 − F_n) = 2BC − B²
…なので、次のようにして『ヌ』を得る:
　　F_3n+1 = F_2n+1F_n+1 + F_2nF_n
　　= (B² + C²)C + (2BC − B²)B
　　= B²C + C³ + 2B²C − B³ = 3B²C − B³ + C³

一方 F_n+2 = F_n + F_n+1 = B + C なので、次のように『ネ』を得る:
　　F_3n+2 = F_2n+1F_n+2 + F_2nF_n+1
　　= (B² + C²)(B + C) + (2BC − B²)C
　　= B³ + B²C + BC² + C³ + 2BC² − B²C = 3BC² + B³ + C³

これで F_3n+1 と F_3n+2 への近道ができる。こうなると、もっと基本的な F_3n への道も欲しい。実は同様の方法で F_3n の式も作れるものの、単純にやると F_n−1, F_n, F_n+1 の3項に依存する形になる――それはそれでいいのだが、もっと少ない情報から F_3n を構成できないか？

別のアプローチと組み合わせると、F_n だけを知って一撃で F_3n を求めることができるという…。その探求のためには、それなりの準備をしなければなるまい。帰納戦士フィボナッチ、次回「カッシーニの隙間をたたけ！」　土星の輪の隙間で、君は生き延びることができるか？ｗ

（下に続く）

2022-11-25　カッシーニの隙間をたたけ！　古典パズルを越えて

#数論　#フィボナッチ　#パズル

画像は見飽きたパズルかもしれない。一辺が8の正方形（面積64）を4個に分割、パーツを並び替えると 5 × 13 の長方形状（面積65）になる――なぜ面積が増えるのか？

変形合体なんて、おもちゃ屋のCMなんです。お子さまにはそれが分からんのですよ。

上の作図は正直に、長方形の対角線付近に「隙間」ができることを明示している（クリックで拡大）――並び替えた結果は「ぴったり長方形」にならず、細い穴が残る。穴の分、面積は65より小さく、もちろんパーツの合計64に等しい。でも、素知らぬ顔で長方形の対角線を普通に引いて、「面積が増えた！」と主張すると、無邪気な人なら面白がってくれるかも…

『不思議の国のアリス』の作者は、このパズルで、少女友達たちを楽しませた（からかった？）らしい。長方形において、三角形パーツ（画像の黄緑）の斜辺の傾きは 3:8 = 0.375、台形（画像の黄色）の斜めの部分の傾きは 2:5 = 0.4 なので、これらが一直線上にないことは明白。長方形の対角線とぴったりフィットするためには、傾きが 5:13 でなければならないが、どちらの傾きも 5/13 と等しくない。

われわれは、不正直な作図それ自体には興味がないけれど、関係する長さ 3, 5, 8, 13 が、フィボナッチ数列
　　1, 1, 2, 3, 5, 8, 13, 21, 34, …
の一部であることに注目したい。すなわち、一辺がフィボナッチ数 F_n の正方形を考えると、その面積 (F_n)² は、直前・直後のフィボナッチ数の積 F_n−1F_n+1 に非常に近いようだ。

〔例1〕　古典パズルでは n = 6, F₆ = 8。その平方 64 は、F₅F₇ = 5 × 13 = 65 と1違い。

〔例2〕　n = 7, F₇ = 13 とすると、その平方 169 は、F₆F₈ = 8 × 21 = 168 と1違い。

〔例3〕　n = 8, F₈ = 21 とすると、その平方 441 は、F₇F₉ = 13 × 34 = 442 と1違い。この大きさでパズルを再構成すれば、さらに隙間が目立たなくなり、トリック性が高まるかもしれない。

【1】　Fibonacci 数列のとある項を選び（第n項とする）、その平方を「正方形」と呼び、その項の前後の項の積を「長方形」と呼ぶと、「正方形」と「長方形」には、ほんの少しの「面積の差」――実は、ちょうど 1 の「隙間」――がある。n が偶数なら、古典パズルで見たように「長方形」の方が 1 大きい。n が奇数なら、上の例2のように、「長方形」の方が 1 小さい。要するに:

Cassini の恒等式　F_n−1F_n+1 = (F_n)² ± 1　　複号はnの偶・奇に応じて正・負

この恒等式の一つの証明法は Binet の式に基づく。 u = (1 + √5)/2, v = (1 − √5)/2 とすると、まず:
　　『ハ』　u + v = 2/2 = 1
　　『ヒ』　uv = (1 − 5)/4 = −1
　　『フ』　u² + v² = (1 + 2√5 + 5 + 1 − 2√5 + 5)/4 = 3

〔参考〕　『ハ』『ヒ』は、いわゆる「解と係数の関係」。u, v は x² − x − 1 = 0 の解なので:
　　(x − u)(x − v) = 0　つまり　x² − (u + v)x + (uv) = 0
この最後の式と最初の2次方程式の1次の係数を比較すれば『ハ』、定数項を比較すれば『ヒ』。『フ』の形は、こう計算される:
　　u² + v² = (u + v)² − 2uv = (1)² − 2(−1)　なぜなら『ハ』『ヒ』
面倒くさければ、普通に直接計算しても、もちろん結果は同じ。

Binet の式から、Cassini の恒等式の左辺は:
　　F_n−1F_n+1 = (uⁿ⁻¹ − vⁿ⁻¹)(uⁿ⁺¹ − vⁿ⁺¹) / 5　　分子を展開して
　　F_n−1F_n+1 = (u²ⁿ − uⁿ⁻¹vⁿ⁺¹ − uⁿ⁺¹vⁿ⁻¹ + v²ⁿ) / 5
この分子の第2・第3項は、次のように、合計 ±3 に等しい。

−(uⁿ⁻¹vⁿ⁺¹ + uⁿ⁺¹vⁿ⁻¹) = −(uⁿ⁻¹vⁿ⁻¹v² + uⁿ⁻¹u²vⁿ⁻¹) = −(uⁿ⁻¹vⁿ⁻¹)(v² + u²)
= (−1)(uv)ⁿ⁻¹(u² + v²) = (−1)(−1)ⁿ⁻¹(3) = (−1)ⁿ × 3　なぜなら『ヒ』『フ』

従って　F_n−1F_n+1 = (u²ⁿ + 3(−1)ⁿ + v²ⁿ) / 5　　‥‥❶

一方、再び Binet の式と『ヒ』を使うと:
　　(F_n)² = (uⁿ − vⁿ)² / 5 = (u²ⁿ − 2uⁿvⁿ + v²ⁿ) / 5
　　(F_n)² = (uⁿ − 2(uv)ⁿ + vⁿ) / 5 = (u²ⁿ − 2(−1)ⁿ + v²ⁿ) / 5　　‥‥❷

n が偶数なら (−1)ⁿ = 1 なので❶の分子は❷の分子より 5 大きく、分母の 5 を考慮すると❶は❷より 1 大きい。n が奇数なら符号が逆になり、❶は❷より 1 小さい。すなわち Cassini の恒等式が成り立つ。□

最初の古典パズルの理論的背景が、一つ明らかになった。

【2】　以下では Cassini の恒等式を F_3n の計算に応用する。加法定理『カ』で a = n, b = 2n と置くと:
　　F_3n = F_n+2n = F_n+1F_2n + F_nF_2n−1
『ケ』から F_2n = 2F_n−1F_n + (F_n)²。『ス』から F_2n−1 = (F_n−1)² + (F_n)²。これらを上の式に代入:
　　F_3n = F_n+2n = F_n+1[2F_n−1F_n + (F_n)²] + F_n[(F_n−1)² + (F_n)²]
　　展開して　F_3n = 2F_n−1F_nF_n+1 + (F_n)²F_n+1 + (F_n−1)²F_n + (F_n)³
この右辺第2項において F_n+1 = F_n−1 + F_n なので:
　　F_3n = 2F_n−1F_nF_n+1 + (F_n)²(F_n−1 + F_n) + (F_n−1)²F_n + (F_n)³
　　整理すると　F_3n = 2F_n−1F_nF_n+1 + (F_n−1F_n)(F_n−1 + F_n) + 2(F_n)³
この右辺第2項に再び F_n+1 = F_n−1 + F_n を適用すると:
　　『ヘ』　F_3n = 3F_n−1F_nF_n+1 + 2(F_n)³

今、『ヘ』の右辺第1項を 3F_n(F_n−1F_n+1) と見て Cassini の恒等式を使うと:
　　F_3n = 3F_n[(F_n)² ± 1] + 2(F_n)³　すなわち
　　『ホ』　F_3n = 5(F_n)³ ± 3F_n　　複号はnの偶・奇に対応

〔例4〕　n = 4 のとき F₄ = 3: F₁₂ = 5 × 3³ + 3 × 3 = 5 × 27 + 9 = 144
あるいは『ヘ』を使って　F₁₂ = 3(2 × 3 × 5) + 2 × 3³ = 90 + 54 = 144

〔例5〕　n = 5 のとき F₅ = 5: F₁₅ = 5 × 5³ − 3 × 5 = 5 × 125 − 15 = 610
あるいは『ヘ』を使って　F₁₅ = 3(3 × 5 × 8) + 2 × 5³ = 360 + 250 = 610

追記（2022年12月1日）　『ホ』は John H. Halton の一般恒等式・85番であることが判明した（導出法は異なる）。ただし Certain particular cases have been known for a long time と記されているので、Halton 自身が発見したわけではないのかもしれない:
“On a General Fibonacci Identity,” The Fibonacci Quarterly, vol. 3, no. 1 (Feb 1965), p. 41
https://www.fq.math.ca/3-1.html

【3】　『ホ』を使うと、F_n の値さえ分かれば F_3n の値を計算できる: F_n の値を「自分」と呼ぶと、F_3n は「自分の立方の5倍に、自分の3倍をプラス・マイナス」するだけ（自分が偶数番目の項ならプラス、奇数番目の項ならマイナス）。例えば F₁₁ = 89 という情報だけに基づき、次のように F₃₃ が得られる:
　　F₃₃ = 89³ × 5 − 89 × 3 = 704969 × 5 − 267 = 3524578
この数を再び「自分」とすれば:
　　F₉₉ = 3524578³ × 5 − 3524578 × 3 = 218922995834555169026

この方法では「番号が 3 の倍数」に限定されてしまうが、前回の『ヌ』『ネ』を使えば、それ以外の番号でも問題ない。簡潔化のため F_n, F_n+1 をそれぞれ B, C とすると:
　　F_3n = 5B³ ± 3B = B(5B² ± 3)
　　F_3n+1 = C³ − B³ + 3B²C = B²(3C − B) + C³
　　F_3n+2 = C³ + B³ + 3BC² = C²(3B + C) + B³

〔例6〕　n = 11 のとき B = F₁₁ = 89, C = F₁₂ = 144 から F_3n+1 = F₃₄ を求める:
　　F₃₄ = 89²(3 × 144 − 89) + 144³ = 7921 × 343 + 2985984 = 5702887
偶然か必然か丸かっこ内は 343 = 7³ なので、次の印象的な関係が成り立つ:
　　F₃₄ = 12⁶ + 7³ × 89²

〔例7〕　n = 33 のとき B = F₃₃ = 3524578, C = F₃₄ = 5702887 から F_3n+1 = F₁₀₀ を求める:
　　F₁₀₀ = 3524578²(3 × 5702887 − 3524578) + 5702887³
　　 = 12422650078084 × 13584083 + 185474538438612378103
　　 = 3垓5422京4848兆1792億6191万5075　　垓（がい）は1兆の1億倍
　　「三つ子よ夫婦　しばしば人泣く　風呂で人食い　これ何個」
丸かっこ内の値 13584083 は 238³ = 13481272 と 239³ = 13651919 の間にあり、立方数ではない。例6の現象は「偶然」だったようだ。

このアルゴリズムを使うと、通常の計算（「直前の2項の和が次の項」という定義に基づく）の3倍のスピードで、大きな Fibonacci 数に到達できる。赤い彗星の公式！

第五補充法則との関連でチラッとフィボナッチ数列のことを考えてみたら、脱線しまくって少々マニアックになってきた。ついでに Cassini の恒等式の Lucas 数列バージョンを確立しておくと、後々役立つかもしれない。（下に続く）

2022-11-27　土星の輪っかとフィボナッチ　知られざる Lucas の隙間

#数論　#フィボナッチ

Fibonacci 数列 1, 1, 2, 3, 5, 8, 13, … のある項（例えば第4項 F₄ = 3）の平方は、その前後の項の積（2 × 5）と1違い。

偶数番目の項を選べば、平方の方が 1 小さい。奇数番目の項を選べば、平方の方が 1 大きい。

この「ずれ」の規則は、しばしば Cassini の恒等式と呼ばれる（詳細は前回）――17世紀のイタリアに生まれた Cassini は、土星の衛星や、土星の輪の隙間の発見者として有名だが、数学の研究もしていたらしい。

Lucas 数列 1, 3, 4, 7, 11, 18, 29, … にも、同様の現象があるだろうか？

例えば第4項 L₄ = 7 を平方すると 49。前後の項の積は 4 × 11 = 44。平方の方が 5 大きい。

第5項 L₅ = 11 を平方すると 121。前後の項の積は 7 × 18 = 126。平方の方が 5 小さい。

第2項 L₂ = 3 を平方すると 9。前後の項の積は 1 × 4 = 4。平方の方が 5 大きい。

第3項 L₃ = 4 を平方すると 16。前後の項の積は 3 × 7 = 21。平方の方が 5 小さい。

どうやら ±5 の「ずれ」があるようだ…。ただし Fibonacci 数列の場合とプラス・マイナスが逆で、偶数番目の項を選ぶと、平方の方が 5 大きい。

何の役に立つのかはともかく、純粋に好奇心をくすぐる現象だ！　Lucas 数列の第 n 項 L_n について、その平方 (L_n)² が前後の項の積 L_n−1L_n+1 の ±5 ということは、常に成り立つのか。それとも、たまたま数列の最初の方がそうなってるだけか…。

【1】　Binet の式…
　　L_n = uⁿ + vⁿ
　　　ただし u = (1 + √5)/2, v = (1 − √5)/2
…を使って、検討してみよう。以下では、
　　uv = −1　なぜなら uv = (1 + √5)(1 − √5)/4 = (1 − 5)/4
　　u² + v² = 3　なぜなら左辺 = (1 + 2√5 + 5)(1 − 2√5 + 5)/4 = (6 + 6)/4
という関係をいちいち断らずに使う（前回の『ハ』『ヒ』『フ』参照）。

L_n の平方は:
　　(L_n)² = (uⁿ + vⁿ)² = u²ⁿ + 2uⁿvⁿ + v²ⁿ
　　 = u²ⁿ + 2(uv)ⁿ + v²ⁿ = u²ⁿ + 2(−1)ⁿ + v²ⁿ　　‥‥❸

一方、前後の項の積は:
　　L_n−1L_n+1 = (uⁿ⁻¹ + vⁿ⁻¹)(uⁿ⁺¹ + vⁿ⁺¹)
　　 = u²ⁿ + uⁿ⁻¹vⁿ⁺¹ + uⁿ⁺¹vⁿ⁻¹ + v²ⁿ
右辺の第2・第3項をまとめると…
　　uⁿ⁻¹vⁿ⁻¹(v² + u²) = (uv)ⁿ⁻¹(u² + v²) = (−1)ⁿ⁻¹(3) = −3(−1)ⁿ
…なので^*10:
　　L_n−1L_n+1 = u²ⁿ − 3(−1)ⁿ + v²ⁿ　　‥‥❹

*10　ある数を 1 倍、つまり (−1)(−1) 倍しても値は変わらない:
　　(−1)ⁿ⁻¹(3) × (−1)(−1) = (−1)ⁿ⁻¹(−1) × (3)(−1) = (−1)ⁿ × (−3)

n が偶数なら (−1)ⁿ = 1 となり、❸は❹より 5 大きい。n が奇数なら符号が逆になり、❸は❹より 5 小さい。一般にそうなることが確かめられた！

“Lucassini” の恒等式　(L_n)² = L_n−1L_n+1 ± 5　　複号は n の偶・奇に対応

〔注意〕　「ある項の平方を、直前・直後の項の積を引いたもの」を Cassini の隙間のサイズと呼び δ で表すと、Fibonacci 数列では偶数番目の項では δ が正、奇数番目の項では δ が負になるが、Lucas 数列では逆に偶数番目の項では δ が負、奇数番目の項では δ が正。Fibonacci は 1, 1, 2, 3 と始まり Lucas は 1, 3, 4, 7 と始まるのだから、このことは簡単に確かめられる（1 × 2 − 1² = 1, 1 × 3 − 2² = −1; 1 × 4 − 3² = −5, 3 × 7 − 4² = 5）。念のため、明示的に対比させると:
　　F_n−1F_n+1 − (F_n)² = ±1 = (−1)ⁿ
　　L_n−1L_n+1 − (L_n)² = ∓5 = −5(−1)ⁿ = 5(−1)ⁿ⁻¹

【2】　Binet の式によると:
　　(F_n)² = (uⁿ − vⁿ)² / 5　分母を払って
　　5(F_n)² = u²ⁿ − 2uⁿvⁿ + v²ⁿ
　　 = u²ⁿ − 2(uv)ⁿ + v²ⁿ = u²ⁿ − 2(−1)ⁿ + v²ⁿ

これを❸と見比べると、(L_n)² は 5(F_n)² と ±4 の関係にあることが読み取れる。

Lucas–Fibonacci の Pell 風シャーベット

n	1	2	3	4	5	6	7	8
x = Ln	1	3	4	7	11	18	29	47
x2	1	9	16	49	121	324	841	2209
y = Fn	1	1	2	3	5	8	13	21
y2	1	1	4	9	25	64	169	441
5y2	5	5	20	45	125	320	845	2205
x2 − 5y2	−4	4	−4	4	−4	4	−4	4

〔偶数項の例〕　L₄ = 7 の平方 49 は、F₄ = 3 の平方の5倍 45 より 4 大きい。

〔奇数項の例〕　L₃ = 4 の平方 16 は、F₃ = 2 の平方の5倍 20 より 4 小さい。

Pell 風の恒等式　(L_n)² − 5(F_n)² = ±4　　複号は n の偶・奇に対応

それ自体としても美しいが、次の重大な事実が含意される。(I) もし与えられた数 y が Fibonacci 数なら、5y² + 4 または 5y² − 4 は平方数（その平方数を x² とすると、自然数 x は、y に対応する Lucas 数）。この条件に反する y は Fibonacci 数ではない。

(II) もし与えられた数 x が Lucas 数なら、x² ± 4 の一方は 5 の倍数で、それを 5 で割った商は平方数（その平方数を y² とすると、自然数 y は x に対応する Fibonacci 数）。この条件に反する x は Lucas 数ではない。

x が5の倍数なら、平方数うんぬん以前に x² ± 4 は5で割り切れないので、この推論が正しいとすると「Lucas 数列には、5の倍数が含まれない」と結論される。普通と違う方法で大きな Fibonacci 数や Lucas 数を求めた場合に、(I)(II) は検算法として使えるかもしれない。

(I)(II) の逆が成り立つか（例えば「5y² ± 4 の一方が平方数になるのは y が Fibonacci 数の場合に限られる」と言い切れるか^*11）を議論するのは時期尚早だが、大ざっぱな話として、5y² ± 4 が平方数になることは珍しく、Fibonacci 数は、この珍しい性質を持つ: L_n を x、F_n を y と置くと、上記の恒等式は（拡張）Pell 方程式 x² − 5y² = ±4 に当たり、右辺が ±4 という基本的な値なので、全部の解が Binet の式を満たすとしても不思議はないだろう。

〔注意〕　1, 1, 2, 3, 5, 8, … という数列を見ると「Fibonacci 数は結構、存在密度が高い」という錯覚が生じるかもしれない（1～10の範囲だけでも5種類あるので）。けれど、前回の例7から明らかなように、Fibonacci 数は、20桁以内の範囲（1～9999京）に100個未満しかない――「かなり珍しい数」といえる。比較として、素数は1～1000までで既に168個もある。

*11　この件については下記参照:
The Fibonacci Quarterly, vol. 10, no. 4 (Oct 1972), pp. 417−419
https://fq.math.ca/10-4.html

2022-11-30　フィボナッチ数の3乗　加法定理の直接証明

#数論　#フィボナッチ

次の関係は美しい:
　　　　　　F_2n = C² − A²
　　『マ』　F_3n = C³ + B³ − A³
　　ただし A = F_n−1, B = F_n, C = F_n+1

〔例〕　F₃ = 2, F₄ = 3, F₅ = 5 を使って:
　　F₈ = 5² − 2² = 25 − 4 = 21
　　F₁₂ = 5³ + 3³ − 2³ = 125 + 27 − 8 = 144

最初の式については既に証明した（『サ』）。『マ』について:
　　F_2n+n = F_2nF_n+1 + F_2n−1F_n = (C² − A²)C + (B² + A²)B　　←『ス』を使った
　　= C³ + B³ − A²(C − B) = C³ + B³ − A³
　　なぜなら　C − B = F_n+1 − F_n = F_n−1 = A

F_3n の実際の計算には赤い彗星『ホ』の 5B³ ± 3B が便利だが、美しさでは『マ』が一番だろう。『ヘ』の 3ABC + 2B³ もきれいだけど…。

これで F_4n が連続するフィボナッチ数4個の4乗の和・差になってくれたら素晴らしいけど、n = 4 のケースを考えると、F₁₆ = 987 を次の数4個の和・差で表すのは無理だろう:
　　(F₂)⁴ = 1⁴ = 1, (F₃)⁴ = 2⁴ = 16, (F₄)⁴ = 3⁴ = 81,
　　(F₅)⁴ = 5⁴ = 625, (F₆)⁴ = 8⁴ = 4096　←でか過ぎる

この種の式をあれこれ加法定理① F_a+b = F_a+1F_b + F_aF_b−1 から導出したが、土台となる加法定理①それ自体の証明は、帰納法によるものだった（第1部【14】、第2部その2）。加法定理②については Binet 形式を使う証明の方がシンプルだった。①も Binet 形式で直接証明しておこう。

いつものように u = (1 + √5)/2, v = (1 − √5)/2 とすると:
　　F_a+1F_b = (u^a+1 − v^a+1)/√5 × (u^b − v^b)/√5 = (u^a+b+1 − u^a+1v^b − u^bv^a+1 + v^a+b+1)/5
　　F_aF_b−1 = (u^a − v^a)/√5 × (u^b−1 − v^b−1)/√5 = (u^a+b−1 − u^av^b−1 − u^b−1v^a + v^a+b−1)/5

上と下を足し算したとき右端の分子・計8項が勝手に打ち消し合い簡約されれば一番楽だが、上記8項は、てんでんばらばらのように見える。でも uv = −1 だった――この式の両辺に v⁻¹ を掛ければ u = −v⁻¹ となるし、それを −1 倍すれば −u = v⁻¹ つまり v⁻¹ = −u となる^*12。同様に u⁻¹ を掛ければ、v = −u⁻¹ つまり u⁻¹ = −v となる。これらを使い、分子の指数部分の邪魔な ±1 を解消しよう。例えば…
　　u^a+b+1 = (u^a+b)(u¹) = (u^a+b)(u)　とか
　　u^a+b−1 = (u^a+b)(u⁻¹) = (u^a+b)(−v)
…となる。つまり上記の分数は:
　　F_a+1F_b = [u^a+b(u) − u^av^b(u) − u^bv^a(v) + v^a+b(v)] / 5
　　F_aF_b−1 = [u^a+b(−v) − u^av^b(−u) − u^bv^a(−v) + v^a+b(−u)] / 5
上と下を足し合わせると、角かっこ内の第2・第3項同士は打ち消し合う:
　　F_a+1F_b + F_aF_b−1 = [u^a+b(u−v) + v^a+b(v−u)] / 5
　　= [u^a+b(u−v) − v^a+b(u−v)] / 5
u, v の定義から u − v = √5 なので、上の式は:
　　= (u^a+b√5 − v^a+b√5) / 5
分子・分母を √5 で約分して:
　　= (u^a+b − v^a+b) / √5 = F_a+b
証明したかった式が得られた。□

*12　確認の意味で、念のため直接計算すると　v⁻¹ = [(1 − √5)/2]⁻¹ = 2/(1 − √5)
= [2(1 + √5)] / [(1 − √5)(1 + √5)] = 2(1 + √5) / (1 − 5) = −(1 + √5)/2 = −u

2022-12-02　フィボナッチ数の4乗・5乗など　Hunter–Carlitz の恒等式

#数論　#フィボナッチ　#二項定理

前回、フィボナッチ数の3乗を3個並べて F_3n を表す美しい式を得たが、同時に「フィボナッチ数の4乗を使って F_4n を同様に表すことはできない」という悲しい事実を観察した。「フィボナッチ数の4乗」を使って、何か面白いことをできないか…。不思議な偶然によりわれわれは、次のパズルと出会った。それは、1960年代の古雑誌の片隅に掲載されていた。

フィボナッチ数の4乗は、次の関係を満たす:
　　『ミ』　A⁴ + B⁴ + C⁴ = 2(2B² ± 1)²
　　ここで A = F_n−1, B = F_n, C = F_n+1　複号は n の偶・奇に対応

例えば A, B, C として F₃ = 2, F₄ = 3, F₅ = 5 を使うと、『ミ』の左辺は:
　　2⁴ + 3⁴ + 5⁴ = 16 + 81 + 625 = 722
『ミ』の右辺は同じ値を持つ:
　　2(2 × 3² + 1)² = 2 × 19² = 2 × 361 = 722

別の例。A, B, C として F₄ = 3, F₅ = 5, F₆ = 8 を使うと:
　　3⁴ + 5⁴ + 8⁴ = 81 + 625 + 4096 = 4802
　　2(2 × 5² − 1)² = 2 × 49² = 2 × 2401 = 4802

【1】　恒等式『ミ』は、1966年にカナダの J. A. H. Hunter [1] によって記された。「これが成り立つことを証明しろ」というパズル。――Fibonacci 数列の話題で「n の偶・奇に対応する ±1」とくれば、Cassini の恒等式
　　AC − B² = ±1
が関係しているのだろう。『ミ』の丸かっこ内の式にこれを代入すると:
　　2B² ± 1 = 2B² + (AC − B²) = B² + AC
　　 = B² + A(A + B) = A² + AB + B²
なぜならフィボナッチ数列の基本性質として C = A + B。

従って『ミ』をこう書き換えられる:
　　『ム』　A⁴ + B⁴ + C⁴ = 2(A² + AB + B²)²　　言い換えれば
　　『メ』　A⁴ + B⁴ + (A + B)⁴ = 2(A² + AB + B²)²

『メ』が成り立つことは以下の単純計算で確かめられるので、それと同内容の『ミ』も成り立つ。三項式 x + y + z の平方の展開については、「公式」として暗記していなくても普通に分配法則を使えば…
　　(x + y + z)² = (x + y + z)(x + y + z)
　　= x(x + y + z) + y(x + y + z) + z(x + y + z)
　　= (x² + xy + xz) + (y² + xy + yz) + (z² + xz + yz)
要するに:
　　『モ』　(x + y + z)² = x² + y² + z² + 2xy + 2xz + 2yz

さて (A + B)⁴ = A⁴ + 4A³B + 6A²B² + 4AB³ + B⁴ なので^*13、『メ』の左辺は
　　『ヤ』　2A⁴ + 4A³B + 6A²B² + 4AB³ + 2B⁴
に等しい。

*13　この展開（の二項係数 1, 4, 6, 4, 1）を覚えていると便利だが、覚えていなくても、パスカルの三角形や二項定理を使えばいい。別の方法として、
　　(A + B)⁴ = [(A + B)²]² = (A² + 2AB + B²)²
を求めればいいのだから、『モ』で x = A², y = 2AB, z = B² とすると:
　　(A + B)⁴ = (A²)² + (2AB)² + (B²)² + 2(A²)(2AB) + 2(A²)(B²) + 2(2AB)(B²)
　　= A⁴ + 4A²B² + B⁴ + 4A³B + 2A²B² + 4AB³
　　= A⁴ + 4A³B + 6A²B² + 4AB³ + B⁴

『メ』の右辺の丸かっこ内の2乗が、『ヤ』の半分…
　　『ユ』　A⁴ + 2A³B + 3A²B² + 2AB³ + B⁴
…に等しいことを示せば証明完了。『モ』で x = A², y = AB, z = B² とすると:
　　(A² + AB + B²)² = (A²)² + (AB)² + (B²)² + 2(A²)(AB) + 2(A²)(B²) + 2(AB)(B²)
これは確かに『ユ』に等しい。□

【2】　パズルそのものは浅い内容（ただの計算問題）だが、少し掘り下げて検討してみよう。『メ』は、Fibonacci 数列と無関係に、単に両辺を展開すれば成り立つ恒等式。式変形を逆にたどると、『メ』から『ム』に行くとき A + B = C の関係を使うが、これは「ある項は直前の2項の和」という漠然とした性質。この性質を持つ数列なら、Fibonacci 数列でなくても同じ変形が可能（例えば Lucas 数列でも構わない）。『ム』から『ミ』に行くとき、
　　『ヨ』　A² + AB + B² = B² + A(A + B) = B² + AC
　　= 2B² + (AC − B²) = 2B² + (±1)
という変形の AC − B² = ±1 は、その数列の「Cassini の隙間」のサイズ（ある項の平方を前後の項の積から引いたもの）。例えば A, B, C が Lucas 数列の連続する3項なら ±1 の代わりに ∓5 が現れ、『ミ』の Lucas バージョンはこうなるだろう:
　　A⁴ + B⁴ + C⁴ = 2(2B² ∓ 5)²

〔例〕　A, B, C として L₂ = 3, L₃ = 4, L₄ = 7 を使うと:
　　A⁴ + B⁴ + C⁴ = 3⁴ + 4⁴ + 7⁴ = 81 + 256 + 2401 = 2738
　　2(2B² + 5)² = 2 × 37² = 2 × 1369 = 2738　　計画通りｗ！
A, B, C として L₃ = 4, L₄ = 7, L₅ = 11 を使うと:
　　4⁴ + 7⁴ + 11⁴ = 256 + 2401 + 14641 = 17298
　　2(2B² − 5)² = 2(2 × 49 − 5)² = 2 × 8649 = 17298

でたらめに作った Fibonacci 風数列、例えば
　　2, 5, 7, 12, 19, 31, …
において、「Cassini の隙間」のサイズを実測すると、偶数項で 2 × 7 − 5² = −11、奇数項で 5 × 12 − 7² = 11。従って、この「でたらめ数列」の連続する3項は、次の関係を満たすはず:
　　A⁴ + B⁴ + C⁴ = 2(2B² ∓ 11)²

〔検証〕　2⁴ + 5⁴ + 7⁴ = 16 + 625 + 2401 = 3042
　　2(2B² − 11)² = 2 × 39² = 2 × 1521 = 3042
5⁴ + 7⁴ + 12⁴ = 625 + 2401 + 20736 = 23762
　　2(2B² + 11)² = 2(2 × 49 + 11)² = 2 × 109² = 2 × 11881 = 23762

【3】　土台となった恒等式『メ』は、直接 Fibonacci 数列と関係しているわけではないが、因子 A² + AB + B² が『ヨ』によって Cassini の恒等式（あるいはそれを一般化したもの）と結び付く。何であれ A, B, C についての式がこの因子を持てば、Fibonacci 的な解釈が可能。米国の L. Carlitz [2][3] は1969年、次のような一連の恒等式を考察した。任意の x, y について:
　　(x + y)⁵ − x⁵ − y⁵ = 5xy(x + y)(x² + xy + y²)
が成り立ち、従って y = A, x = B, x + y = C を Fibonacci 数列の隣り合う3項とすると、次が成り立つ:
　　C⁵ − B⁵ − A⁵ = 5ABC(A² + AB + B²) = 5ABC(2B² ± 1)　なぜなら『ヨ』
Fibonacci 数の5乗に関する恒等式だ！

〔例〕　5⁵ − 3⁵ − 2⁵ = 3125 − 243 − 32 = 2850
　　5(2⋅3⋅5)(2 × 3² + 1) = 5 × 30 × 19 = 2850

同様に、代数的な恒等式…
　　(x + y)⁷ − x⁷ − y⁷ = 7xy(x + y)(x² + xy + y²)²
…を Fibonacci 数列の世界に適用すると、こうなる:
　　C⁷ − B⁷ − A⁷ = 7ABC(2B² ± 1)²

〔例〕　5⁷ − 3⁷ − 2⁷ = 78125 − 2187 − 128 = 75810
　　7(2⋅3⋅5)(2 × 3² + 1)² = 7 × 30 × 19² = 75810

一般に (x + y)^m の二項展開から両端の項を除去した式、すなわち
　　(x + y)^m − x^m − y^m
は、どんな因子を持つか。m が 3 以上の素数のとき、この式が mxy(x + y) で割り切れることは、比較的容易に示される。このことを Fibonacci 的に解釈すると、C^m − B^m − A^m は因子 mABC を持つ。のみならず m が 5 以上の素数のとき（少なくとも m = 5 or 7 のとき）、この式が x² + xy + y² で割り切れることを確かめられる。前述の通り、Fibonacci の文脈では因子 2B² ± 1 に当たる。

他方 m = 3 のとき:
　　(x + y)³ − x³ − y³ = 3x²y + 3xy² = 3xy(x + y)
　　Fibonacci 形式で書くと　C³ − B³ − A³ = 3ABC

〔例〕　5³ − 3³ − 2³ = 125 − 27 − 8 = 90
　　3(2⋅3⋅5) = 3 × 30 = 90

この式は C = A + B にのみ依存し「Cassini の隙間」が絡まないため、直ちに任意の Fibonacci 風数列に適用可能。

〔例〕　Lucas 数列 1, 3, 4, 7, 11, … において:
　　7³ − 4³ − 3³ = 343 − 64 − 27 = 252
　　3(3⋅4⋅7) = 3 × 84 = 252
あるいは 11³ − 7³ − 4³ = 1331 − 343 − 64 = 924
　　3(4⋅7⋅11) = 3 × 308 = 924

m = 5 or 7 の式も Cassini の恒等式に依存しない形式なら（例えば 2B² ± 1 の代わりに B² + AC を使えば）、任意の Fibonacci 風数列に適用可能。

【4】　以上を整理して、次の「きれいなだけで何の役にも立たない（？）定理」を得る。

定理　好きに選んだ数を2個書いて、「直前の2項の和」として第3項以降を次々と定義したとする。このような任意の数列において、隣り合う3項 A, B, C は次の関係を満たす:
　　C⁴ + B⁴ + A⁴ = 2r²
　　(C³ − B³ − A³)/3 = q
　　(C⁵ − B⁵ − A⁵)/5 = qr
　　(C⁷ − B⁷ − A⁷)/7 = qr²
ただし q = ABC, r = 2B² + δ = B² + AC = C² − AB。ここで δ は「Cassini の隙間」のサイズ: Fibonacci 数列の場合、B が偶数番目の項なら δ = 1、奇数番目の項なら δ = −1。

〔付記〕　q, r を A, B の対称式として表現できる: q = AB(A + B), r = A² + AB + B² = (A + B)² − AB。一方、定理各式の左辺も、二項定理により A, B について対称的で、原理的には AB と A + B によって表現可能だろうが、「正確に q と r だけで表現可能」という点は、自明ではない。Fibonacci 数列の問題というより、二項展開に関連する問題だろう。

証明　『ヨ』から 2B² + δ = B² + AC = A² + AB + B²。この右辺は次の値に等しい:
　　A² + 2AB + B² − AB = (A + B)² − AB = C² − AB
定理の第2式は【3】の通り。第1式は Hunter の恒等式、第3・第4式は Carlitz の恒等式に当たる。□

例えば A = F₆ = 8, B = F₇ = 13, C = F₈ = 21 の場合:
　　2B² + δ = 2 × 13² − 1 = 2 × 169 − 1 = 337
　　B² + AC = 13² + 8 × 21 = 169 + 168 = 337
　　A² + AB + B² = 8² + 8 × 13 + 13² = 64 + 104 + 169 = 337
　　C² − AB = 21² − 8 × 13 = 441 − 104 = 337
どの方法で計算するにせよ、この値が r = 337 となる。 q = 8⋅13⋅21 = 2184 と組み合わせて:
　　21⁴ + 13⁴ + 8⁴ = 227138 = 2 × 337²
　　(21³ − 13³ − 8³)/3 = 2184
　　(21⁵ − 13⁵ − 8⁵)/5 = 736008 = 2184 × 337
　　(21⁷ − 13⁷ − 8⁷)/7 = 248034696 = 2184 × 337²

あるいは、今日は12月2日だから…という行き当たりばったりの理由で A = 12, B = 2, C = A + B = 14 として q = ABC = 336, r = B² + AC = 172 を使うと:
　　14⁴ + 2⁴ + 12⁴ = 59168 = 2 × 172²
　　(14³ − 2³ − 12³)/3 = 336
　　(14⁵ − 2⁵ − 12⁵)/5 = 57792 = 336 × 172
　　(14⁷ − 2⁷ − 12⁷)/7 = 9940224 = 336 × 172²

定理の内容は A + B = C という単純計算を複雑に言い換えているだけだが、「なぜそのような言い換えが可能なのか」ということが問題の核心だろう。次の素数 m = 11 に対する (C^m − B^m − A^m)/m の形を検討してみると、面白いかもしれない。

〔参考文献〕
[1] J. A. H. Hunter: “H-79”, The Fibonacci Quarterly, vol. 4, no. 1 (Feb 1966), p. 57
https://www.fq.math.ca/4-1.html
[2] L. Carlitz: “H-112”, Fib. Quart., vol. 7, no. 1 (Feb 1969), pp. 61–62
https://www.fq.math.ca/7-1.html
[3] L. Carlitz & J. A. H. Hunter: “Sums of Powers of Fibonacci and Lucas Numbers”, Fib. Quart., vol. 7, no. 5 (Dec 1969), pp. 467–473
https://www.fq.math.ca/7-5.html

2022-12-06　ビネの公式の一般化　第2部・最終回

#数論　#フィボナッチ

前回、「フィボナッチ風」の例として、でたらめに選んだ 2, 5, 7, 12, … や「12月2日だから」という適当な理由で作った 12, 2, 14, 16, … を考えた。こういう任意の Fibonacci 風数列
　　X₁, X₂, X₃, X₄, …　（X₁ + X₂ = X₃, X₂ + X₃ = X₄, etc.）
に関しても δ = X_n+1X_n−1 − (X_n)² は n の偶・奇に応じて一定になる。この事実を無証明のまま暗黙に使ってしまったが、そのギャップを埋め、美しい式を紹介したい。

【1】　Binet の公式の導出の【4】を思い出そう。第 n 項 X_n は cuⁿ + dvⁿ の形を持つ（c, d: 定数）。これを使って、まず X_n+1X_n−1 を計算すると:
　　X_n+1X_n−1 = (cuⁿ⁺¹ + dvⁿ⁺¹)(cuⁿ⁻¹ + dvⁿ⁻¹)
　　 = cuⁿ⁺¹cuⁿ⁻¹ + cuⁿ⁺¹dvⁿ⁻¹ + dvⁿ⁺¹cuⁿ⁻¹ + dvⁿ⁺¹dvⁿ⁻¹
ちょっぴりゴチャゴチャするが、普通に展開しただけ。係数 c, d などをアルファベット順に整理すると:
　　 = c²uⁿ⁺¹uⁿ⁻¹ + cduⁿ⁺¹vⁿ⁻¹ + cduⁿ⁻¹vⁿ⁺¹ + d²vⁿ⁺¹vⁿ⁻¹
両端の2項はさらに整理可能。真ん中の2項については、共通因子 cduⁿ⁻¹vⁿ⁻¹ でくくるのが好手:
　　 = c²u²ⁿ + cduⁿ⁻¹vⁿ⁻¹(u² + v²) + d²v²ⁿ = c²u²ⁿ − 3cd(−1)ⁿ + d²v²ⁿ　　‥‥①

最後の等号が成り立つ根拠は、u, v の和や積の性質。①左辺第2項は、こうなる:
　　cduⁿ⁻¹vⁿ⁻¹(u² + v²) = cd(uv)ⁿ⁻¹(3) = 3cd(−1)ⁿ⁻¹ = −3cd(−1)ⁿ
　　ここで　(−1)ⁿ⁻¹ = (−1)ⁿ⁻¹ × 1 = (−1)ⁿ⁻¹ × (−1)(−1) = (−1)[(−1)ⁿ⁻¹ × (−1)]

次に X_n を同様に計算すると:
　　X_n = (cuⁿ + dvⁿ)² = c²u²ⁿ + 2cduⁿvⁿ + d²v²ⁿ = c²u²ⁿ + 2cd(−1)ⁿ + d²v²ⁿ　　‥‥②

この二つの式から、
　　『ラ』　δ = X_n+1X_n−1 − (X_n)² = ① − ② = −5cd(−1)ⁿ
は、確かに n の偶・奇にのみ依存する定数: 絶対値 |5cd| で符号は n の偶・奇による。

Fibonacci 数列では c = 1/√5, d = −1/√5 だから −5cd = 1 であり、Cassini の恒等式の通り δ = ±1。 Lucas 数列では c = d = 1 だから、“Lucassini” の恒等式の通り δ = ∓5 となる。―― c, d 経由で計算するまでもなく、δ の値を「実測」で決定しても差し支えない（どの項で測っても一定であることは、上記により証明されている）: 例えば Lucas 数列 1, 3, 4, … では偶数項において δ = 1 × 4 − 3² = −5、従って奇数項において δ = +5。

ところで一般の場合に、定数 c, d は、どのような値になるのだろうか。

【2】　前記「フィボナッチ風」でたらめ数列 2, 5, 7, 12, … の一般項は？

Binet の式の導出のときもそうだったが、第0項 3 (= 5 − 2) を活用すると計算が楽になる:
　　n = 0　⇒　X₀ = cu⁰ + dv⁰ = c + d = 3　　‥‥③
　　n = 1　⇒　X₁ = cu¹ + dv¹ = cu + dv = 2　　‥‥④
③から d = 3 − c、これを④に代入して cu + (3 − c)v = c(u − v) + 3v = 2、ここで
　　u = (1 + √5)/2, v = (1 − √5)/2, u − v = √5
なので c(u − v) + 3v = c√5 + 3v = 2、つまり:
　　c = (2 − 3v)/√5 = [2 − 3(1 − √5)/2] / √5 = (3√5/2 − 1/2) / √5
　　d = 3 − c = 3√5 / √5 − (3√5/2 − 1/2) / √5 = (3√5/2 + 1/2) / √5
　　cd = [(3√5/2)² − (1/2)²] / 5 = (45/4 − 1/4) / 5 = (44/4) / 5 = 11/5
これを『ラ』に入れれば δ = ∓11 となり、前回の「実測」と一致。『ラ』に間違いはないようだ！

この場合 c の式の 2 は X₁ で 3 は X₀。d = 3 − c は X₁ − c。さらに c の式と d の式の右端の分子を比べると、「無理部」（√5 の係数）がどちらも 3/2 で等しく、「有理部」はそれぞれ −1/2 と 1/2 で、絶対値が同じ・符号が反対。―― X₀, X₁ の具体的な値によらず、定数 c, d の値はいつもこのようなパターンになる。事実、X₀ = A, X₁ = B を任意の2整数として、上記と同様に計算すると:
　　c = (B − Av)/√5 = [B − A(1 − √5)/2] / √5 = (A√5/2 − (B − A/2)) / √5
　　d = A − c = A√5 / √5 − (A√5/2 − (B − A/2)) / √5 = (A√5/2 + (B − A/2)) / √5
今、d の式の両辺を −1 倍すると:
　　−d = (−A√5/2 − (B − A/2)) / √5
この分子について c の式の右端と見比べると、今度は「有理部」が等しく「無理部」の符号だけが逆。これは u = (1 + √5)/2 と v = (1 − √5)/2 の関係と同じ。実際、c = (B − Av)/√5 の v を u に置き換えると…
　　(B − Au)/√5 = [B − A(1 + √5)/2] / √5 = (−A√5/2 + (B − A/2)) / √5 = −d

すなわち、直前の2項の和が次の項という「フィボナッチ的性質」を持つ任意の数列（第0項を A、第1項を B とする）について、第 n 項 X_n を Binet 風に cuⁿ + dvⁿ と書いた場合、係数 c, d の値は A, B によって簡潔に記述可能。d の代わりに −d を使えば、次の美しい式を得る。

Binet の公式の一般化　X₀ = A, X₁ = B の Fibonacci 型数列の一般項は:
　　X_n = cuⁿ + dvⁿ = cuⁿ − (−d)vⁿ = [(B − Av)uⁿ − (B − Au)vⁿ] / √5

特に、元祖 Fibonacci 数列（A = 0, B = 1）の場合、c = B − Av = 1, d = B − Au = 1 だから、右辺の2カ所の丸かっこ内は 1 となり、狭義の Binet の公式と一致。同様に元祖 Lucas 数列（A = 2, B = 1）の場合、c = B − Av = √5, d = B − Au = −√5（従って −d = √5）だから、これらの係数は分母と約分されて消滅: 結果は、見慣れた公式 L_n = uⁿ + vⁿ になる。

この型の全ての数列において、第0項の u 倍ないし v 倍を第1項から引いたものが、c ないし −d の正体だったのだ。

実際の計算にはあまり役立ちそうにもないけど、今まで2種類の公式だと思っていたもの（そしてそれを含むさらに広い範囲）がクリアに一望できる。眺めの良い尾根道だ！

「でたらめ」数列 2, 5, 7, 12, … の場合（第0項 A = 3）、一般項は次の通り:
　　X_n = [(2 − 3v)uⁿ − (2 − 3u)vⁿ] / √5

「12月2日」数列 12, 2, 14, 16, … の場合（第0項 A = −10）、一般項は:
　　X_n = [(12 + 10v)uⁿ − (12 + 10u)vⁿ] / √5

【3】　「でたらめ」数列は、ただの例として本当にでたらめに選んだのだが、調べてみると数学的にいろいろな意味があるばかりか^*14、タタール出身の作曲家 София Губайдулина（ソフィヤ・グバィドゥリナ）は、この数列を作品に利用しているという！　数学的な一つの意味として、Fibonacci 数列の第2項以降 1, 2, 3, 5, … と Lucas 数列 1, 3, 4, 7, … の項ごとの和 F_n+1 + L_n に当たる。

「12月2日」数列の方は、いくらなんでも意味がないだろう――と思いきや、こっちは「mod 41 の原始根 7 のべき」と関連している^*15。恐るべしフィボナッチ。どこにでも忍び込む！

Πυθαγόρας は「万物は数である」と言ったそうだが、「万物は Fibonacci である」と言うべきかもしれない。ピタゴラスにとっての“正しい”数は有理数――無理数の存在は悩みの種だったようだ。だが木の枝や葉序、花、巻き貝などから明らかなように、自然はフィボナッチ数列を好む。そこには √5 という無理数が潜んでいる。高木も言う: 「無理数でも、虚数でも遠慮なく取り扱うことができるような雰囲気の中において、整数論が自由に発展することができた」と。われわれは有理数と無理数を平等視し、実数と虚数を平等視する。自然と不自然、生と死、価値と無価値、世俗と超越――それは人の思いに過ぎない。

バルトークとフィボナッチ数列の関係も、よく聞く話だ。ジョーク記事「確信犯」たちの「開発動機」でも、バルトークが「巻き貝がフィボナッチ数列だからやった」などと発言している。実際問題、リズムや音程にフィボナッチ的な要素があったとして、意図的にやってるのかどうかは必ずしも明らかではない。1, 2, 3, 5, 8 は別に珍しいパターンではなく、たまたまそうなっている場所を見つけて「フィボナッチ数列を使っている」と主張することは、こじつけともいえる。とはいえ直観的には、バルトークは確かにフィボナッチっぽい。

*14　Evangelist(s) 数列と呼ばれることがある。
https://oeis.org/A001060

*15　https://oeis.org/A070424

「直前の2項の和として各項を定義する」ということを「広い意味での Fibonacci」と呼ぶなら、今回の結果はその広い意味での一般公式だが、例えば「直前の2項の和の2倍」を各項とすれば、さらなる拡張が考えられる。「一般化された Fibonacci 数列」の概念は、文脈によって意味が異なる。ある項を B、その直前の項を A として、B の次の項を C = αA + βB によって定義することもできる（α, β: 定数）。その観点では、今回の「拡張」は、実は α = β = 1 の「最も単純で限定的な例」に過ぎない（この全景を見渡すのにふさわしい視座は、行列の観点かもしれない）。「直前の2項の和の2倍」を各項とするのは α = β = 2 のケースに当たり、第3部ではその森を探検するであろう。

「独りで山や谷をさまようときは一木一石にも心を惹かれないものはないのである」

興来（きた）りて遠近無く、去らんと欲して芳菲（ほうひ）を惜しむ。花の香りのフィボナッチ。

（第2部・完）

---