フィボナッチ数をバラバラに
—
線形再帰数列と
2
項係数、チェビシェフ多項式
安田正實（千葉大学名誉教授） フィボナッチ数列は2項係数の斜めの和として表されることがよく知られている。こ こではそれに関連して、ルーカス数列、ペリン数列など線形再帰数列を2項係数の和 として表す。チェビシェフ多項式の複素数値の巡回性に対する値が関わりをもつこと がわかる。1
はじめに
チェビシェフという人物は、wikipediAからの引用では”Pafnuty Lvovich Chebyshev、1821年5月16日（ユリ
ウス暦5月4日） - 1894年12月8日（ユリウス暦11月26日））は、ロシアの数学者。”といわれる。ラテン文字
ではChebychev、Chebyshov、Tchebycheff、Tschebyscheff など。数学用語に用いられる用語では、チェビシェフ フィルタ、チェビシェフ関数、チェビシェフ多項式、チェビシェフの不等式、チェビシェフの和の不等式、チェビ シェフ方程式、チェビシェフ距離がある。(参照：https://ja.wikipedia.org/wiki/のチェビシェフ多項式の項 目から。wikipediaA) 三角関数との関連から、入試問題、数学オリンピック問題(1960年）などに もよく出題され、 cosπ 7 + cos 3π 7 + cos 5π 7 = 1 2 は典型的なx = cos θとおいて、θ = π 7 から作られるcos(3θ), cos(4θ)の多 項式が満たす、つまりチェビシェフ多項式の関係式を3次式と4次式の関係 を方程式として解いて求めさせている。さらにとくに再帰関係式もよく知 られている。ここではその再帰関係式（cos(nθ)をnの漸化式とする）問題 として、漸化式は同じであるが、初期値の違いで2種類ある。さらにもう2 個を文献[6]で第1種から第4種までの定義は述べている。ここではこれに 基づくが、数学辞典[5]での第2種の定義とは異なることに注意されたい。
2
２つの
Chebyshev
多項式
第1, 2種Ｃｈｅｂｙｓｈｅｖ多項式は、それぞれ (n≥ 1)として (初期値の違いに注意！！) { T0(x) = 1, T1(x) = x, Tn+1(x) = 2x Tn(x)− Tn−1(x). (2.1) { U0(x) = 1, U1(x) = 2x, Un+1(x) = 2x Un(x)− Un−1(x). (2.2) で定める。つぎの関係もよく知られている。 Tn(x) = ω(x)n+ ω(x)n ω(x)· ω(x) , Tn(cos θ) = cos(nθ) (2.3) Un(x) = ω(x)n+1− ω(x)n+1 ω(x)− ω(x) , Un(cos θ) = sin(n + 1)θ sin(θ) (2.4) ただしω(x) = x +√x2− 1, ω(x) = x −√x2− 1とする。ω(x)· ω(x) = 1, ω(x) − ω(x) = 2√x2− 1が成り立つ。 これらは三角法の加法定理から得られる。しかし複素数をもちいると不思議なことに、Lucas数列とFibonacci数列が計算できる。Fibonacci Quartery誌の多くの論文で述べられている。 Ln= 2 inTn(−i/2) (2.5) Fn = inUn(−i/2) (2.6) しかも(2.4), (2.6)式から、分子がゼロとなる値、すなわち根が得られるから、それをもちいて、多項式を積の形に 表して Fn= [(n−1)/2]∏ k=1 ( 1 + 4 cos2kπ n ) (2.7) となり、具体的にn = 7, 10では、 F7= ( 1 + 4 cos2π 7 ) ( 1 + 4 cos22π 7 ) ( 1 + 4 cos23π 7 ) = 29− 32 { cosπ 7 + sin π 14 − sin 3π 14 } F10= ( 1 + 45 + √ 5 8 ) ( 1 +(1 + √ 5)2 4 ) ( 1 + 45− √ 5 8 ) ( 1 +(−1 + √ 5)2 4 ) などで、あの2次環Z(√5)はどこに行った！、複素2次環Z(√−5)とは大違い！？ 2016年8月大阪にて発表したTEXによる beamer pdf , 参考文献などをhttp://www. math.s.chiba-u.ac.jp/~yasuda/ippansug/fibo.htmlに掲載しています。
ここでの発表の主旨は、三角関数でのオイラー公式eiθ = cos θ + i sin θのn乗を計算することで
(1) フィボナッチ数、ルーカス数(リュカ数)を2項係数の値 ( n r ) ; n, r で表すことができ、
(2) さらに、ペリン数(OEIS; perrin, A001608):
(3) またある線形三項関係式(OEIS: A050443)についても表現されることを示す。
参考文献：
[1] W.A.Webb/E.A.Parberry; Divisibility Properties of Fibonacci Polynomials, FQ 7,(1969). [2] N.Garnier/O.Ramar´e; Fibonacci numbers and trigonometric identities, FQ 40 (2008). [3] Fibonacci Quartaryに掲載の論文Hoggatt/Long:FQ12 (1974), Cahill/D’Errico/Spencer:FQ41(2003), Ismal:FQ44(2006), Garnier/Ramar´e:FQ46/47(2008). [4] E.W.Weisstein; Chebyshev Ploynomial of th First Kind, A Wolfram Web Resource. [5]日本数学会編集「岩波数学辞典」岩波書店(1985)。[6] J.C.Mason/D.C.Handscomb; Chebyshev Polynomials,Chapman& Hall/CRC 2003. [7] S. R. Finch; Mathematical Constants, Cambridge, 2003, Section 1.2.2. [8] D. Fomin; On the properties of a certain recursive sequence, Mathematics and Informatics Quarterly, 3 (1993), 50-53. [9] R. Perrin; Query 1484, L’Intermé diaire des Mathé maticiens, 6 (1899), 76. [10] Clifford A. Pickover; A Passion for Mathematics, Wiley, 2005; p. 70. [11] M. Schroeder; Number Theory, 3rd ed., Springer, 1997. [12] N. J. A. Sloane; A Handbook of Integer Sequences, Academic Press, 1973. [13] N. J. A. Sloane and Simon Plouffe; The Encyclopedia of Integer Sequences, Academic Press, 1995. [14] I. Stewart; Math. Rec., Scientific American, #6, 1996 p 103. [15] American Mathematical Monthly 107 (2000) 281-282 (Solution of Problem 10655). [16] Minton, Gregory T.; Linear recurrence sequences satisfying congruence conditions. Proc. Amer. Math. Soc. 142 (2014), no. 7, 2337–2352. MR3195758. [17] David Wells; Prime Numbers, the Most Mysterious Figures in Math, John Wiley & Sons, 2005.
3
数式処理のお助け
Mathematicaの数列生成のための命令：Fibonacci[n], LucasL[n], ChebyshevT[n,x], ChebyshevU[n,x],
にもとづいて、数値例を挙げてみる。ただし過信は禁物であることを別の機会に述べよう。Fibonacci多項式は研究 誌FQではお馴染みであるが、チェビシェフ多項式の2種類は、日本数学会編集の数学辞典とFQでの定義も違いが あり、研究誌の中でも違いがあることに注意されたい。
3.1
Fibonacci
多項式
Fibonacci多項式 Fn(x, y) = x Fn−1(x, y) + y Fn−2(x, y)の表: F0(x, y) = 0, F1(x, y) = 1 で定める。 n Fn(x, y) Factored Fn(x, y) 0 0 = 0 1 1 = 1 2 x = x 3 x2+ y = x2+ y 4 x3+ 2xy = x(x2+ 2y) 5 x4+ 3x2y + y2 = x4+ 3x2y + y2 6 x5+ 4x3y + 3xy2 = x(x2+ y) (x2+ 3y) 7 x6+ 5x4y + 6x2y2+ y3 = x6+ 5x4y + 6x2y2+ y3 8 x7+ 6x5y + 10x3y2+ 4xy3 = x(x2+ 2y) (x4+ 4x2y + 2y2) 9 x8+ 7x6y + 15x4y2+ 10x2y3+ y4 =(x2+ y) (x6+ 6x4y + 9x2y2+ y3) 10 x9+ 8x7y + 21x5y2+ 20x3y3+ 5xy4 = x(x4+ 3x2y + y2) (x4+ 5x2y + 5y2) 11 x10+ 9x8y + 28x6y2+ 35x4y3+ 15x2y4+ y5 = x10+ 9x8y + 28x6y2+ 35x4y3+ 15x2y4+ y5 12 x11+ 10x9y + 36x7y2+ 56x5y3+ 35x3y4+ 6xy5 = x(x2+ y) (x2+ 2y) (x2+ 3y) (x4+ 4x2y + y2) このFn(1, 1) = Fnとなり、一般形と考えられるし、また見通しがよくなることもあります。いわゆるパスカル三 角形の斜めの和をとると、よく知られているようにフィボナッチ数が表れてきます。{Fn(x, y); n = 1, 2,· · · } の多項式をこのように表にしてみると、二項係数の値が斜めの系列でその和がフィ ボナッチ数を表すことが分かり、x3 + 3x2y + 3xy2+ y3 x=1,y=1 = 1 + 3 + 3 + 1 = 2 3 なども明白である。 フィボナッチ数列が、2 項係数とは ( n r ) = ( n n− r ) , ( n r ) + ( n r + 1 ) = ( n + 1 r + 1 ) , ( n r ) = 0 (n < r)であっ て、たとえば、表にある斜め（左上から右下）への線を、逆に対称性から、左上から右下へとみると、係数パ ラメータの和が一定の値になることがわかる。F6 = 3 + 4 + 1 = ( 3 1 ) + ( 4 3 ) + ( 5 5 ) = ( 3 2 ) + ( 4 1 ) + ( 5 0 ) や F7 = 1 + 6 + 5 + 1 = ( 3 0 ) + ( 4 2 ) + ( 5 4 ) + ( 6 6 ) = ( 3 3 ) + ( 4 2 ) + ( 5 1 ) + ( 6 0 ) であり、2 項係数の和 ( n r ) + ( n r + 1 ) = ( n + 1 r + 1 ) の関係式から、フィボナッチ数列の再帰関係： F5= 1 +3 +1 = 5 F6= 3 +4 +1 = 8 F7= 1 +6 +5 +1 = 13 となっている。これからフィボナッチ数列は2項係数の和で表されることが示唆されている。
3.2
第
1
種チェビシェフ多項式
第1種チェビシェフ多項式: Tn(x) = 2x Tn−1(x)− Tn−2(x), T0(x) = 1, T1(x) = x: n Tn(x) 0 1 1 x 2 −1 + 2x2 3 −3x + 4x3 4 1− 8x2+ 8x4 5 5x− 20x3+ 16x5 6 −1 + 18x2− 48x4+ 32x6 7 −7x + 56x3− 112x5+ 64x7 8 1− 32x2+ 160x4− 256x6+ 128x8 9 9x− 120x3+ 432x5− 576x7+ 256x9 10 −1 + 50x2− 400x4+ 1120x6− 1280x8+ 512x10 11 −11x + 220x3− 1232x5+ 2816x7− 2816x9+ 1024x113.3
第
2
種チェビシェフ多項式
第２種チェビシェフ多項式l: Un(x) = 2x Un−1(x)− Un−2(x), U0(x) = 1, U1(x) = 2x: n Un(x) Factered Un(x) 0 1 = 1 1 2x = 2x 2 −1 + 4x2 = (−1 + 2x)(1 + 2x) 3 −4x + 8x3 = 4x(−1 + 2x2) 4 1− 12x2+ 16x4 =(−1 − 2x + 4x2) (−1 + 2x + 4x2) 5 6x− 32x3+ 32x5 = 2x(−1 + 2x)(1 + 2x)(−3 + 4x2) 6 −1 + 24x2− 80x4+ 64x6 = (1− 4x − 4x2+ 8x3) ( −1 − 4x + 4x2+ 8x3) 7 −8x + 80x3− 192x5+ 128x7 = 8x(−1 + 2x2) (1− 8x2+ 8x4) 8 1− 40x2+ 240x4− 448x6+ 256x8 = (−1 + 2x)(1 + 2x)(−1 − 6x + 8x3) ( 1− 6x + 8x3) 9 10x− 160x3+ 672x5− 1024x7+ 512x9 = 2x(−1 − 2x + 4x2) ( −1 + 2x + 4x2) (5− 20x2+ 16x4) 10 −1 + 60x2− 560x4+ 1792x6− 2304x8+ 1024x10 = (−1 + 6x + 12x2− 32x3− 16x4+ 32x5) ( 1 + 6x− 12x2− 32x3+ 16x4+ 32x5) 11 −12x + 280x3− 1792x5+ 4608x7− 5120x9+ 2048x11 = 4x(−1 + 2x)(1 + 2x)(−1 + 2x2) ( −3 + 4x2) (1− 16x2+ 16x4)3.4
多項式の複素数の代入で数列の生成
•第1種チェビシェフ多項式から、Lucas数を計算する： Ln = 2∗ I∧n∗ ChebyshevT[n, −I/2], I = √ −1 (3.1) L1= 1 = 2∗ I∧n∗ ChebyshevT[0, −I/2] L2= 3 = 2∗ I∧n∗ ChebyshevT[1, −I/2] L3= 4 = 2∗ I∧n∗ ChebyshevT[2, −I/2] L4= 7 = 2∗ I∧n∗ ChebyshevT[3, −I/2] L5= 11 = 2∗ I∧n∗ ChebyshevT[5, −I/2] · · · · · · · •第2種チェビシェフ多項式からFibonacci数を計算する： Fn+1= I∧n∗ ChebyshevU[n, −I/2], I = √ −1 (3.2) F2= 1 = I∧1∗ ChebyshevU[1, −I/2] F3= 2 = I∧2∗ ChebyshevU[2, −I/2] F4= 3 = I∧3∗ ChebyshevU[3, −I/2] F5= 5 = I∧4∗ ChebyshevU[4, −I/2] F6= 8 = I∧5∗ ChebyshevU[5, −I/2] F7= 13 = I∧6∗ ChebyshevU[6, −I/2] · · · · · · · 上の関係式は既に述べたFQの論文で与えられている。つぎはこの関係を三角法の倍角公式等をもちいて、展開し て得られます。3.5
三角法の倍角公式
つぎにこの関係から、発展させてPerrin数、OEIS:A050443について調べてみます。その準備のために、まずフィ
ボナッチ数とルーカス数を2項係数で表すことから考えていきます。三角法の倍角公式が重要な働きをしています。
当然かもしれませんが
cos(nθ) + i sin(nθ) = (cos θ + i sin θ)n = ei n θ
は2項展開の式ですから、2項係数がその仲介役を引き受けてくれています。 cos(nθ) = ( n 0 ) cosnθ− ( n 2 ) cosn−2θ sin2θ + ( n 4 ) cosn−4θ sin4θ− ( n 6 ) cosn−6θ sin6θ− · · · sin(nθ) = ( n 1 ) cosn−1θ sin θ− ( n 3 ) cosn−3θ sin3θ + ( n 5 ) cosn−5θ sin5θ− · · · 倍角の公式からはUn(x) = Un(cos θ) = sin(n + 1)θ sin θ :
sin(n + 2)θ = 2 cos θ sin(n + 1)θ− sin(nθ) (3.3)
∴ sin(n + 2)θ sin θ = 2 cos θ sin(n + 1)θ sin θ − sin(nθ) sin θ ⇔ Un+1(x) = 2x Un(x)− Un−1(x) すなわち第2種のチェビシェフの多項式が示されます。また式(3.3)の関係は
sin(n + 1)θ = sin(nθ) cos θ + cos(nθ) sin θ sin(n− 1)θ = sin(nθ) cos θ − cos(nθ) sin θ sin(n + 1)θ + sin(n− 1)θ = 2 sin(nθ) cos θ
であるから。同様にTn(x) = Tn(cos θ) = cos(nθ) :
cos(n + 1)θ = 2 cos θ cos(nθ)− cos(n − 1)θ (3.4)
⇔ Tn+1(x) = 2x Tn(x)− Tn−1(x) なぜなら(n + 1)θ = nθ + θ, (n− 1)θ = nθ − θの形に対する加法定理から
cos(n + 1)θ = cos(nθ) cos θ− sin(nθ) sin θ cos(n− 1)θ = cos(nθ) cos θ + sin(nθ) sin θ cos(n + 1)θ + cos(n− 1)θ = 2 cos(nθ) cos θ
であるから、これから第1種のチェビシェフの多項式が得られました。
これらの関係からは、倍角の公式において、sin2θ = 1− cos2θ, sin4θ = 1−
( 2 1 ) cos2θ + ( 2 2 ) cos4θ, sin6θ = 1− ( 3 1 ) cos2θ + ( 3 2 ) cos4θ− ( 3 3 ) cos6θ, · · · から2項係数をもちいて、チェビシェフ多項式を表すことができ ます。 第1種チェビシェフ多項式では (i) T2(x) = 2x2− 1 = {( 2 0 ) + ( 2 2 )( 1 1 )} x2− ( 2 2 )( 1 0 ) (ii) T3(x) = 4x3− 3x = {( 3 0 ) + ( 3 2 )( 1 1 )} x3− ( 3 2 )( 1 0 ) x
(iii) T4(x) = 8x4− 8x2+ 1 = {( 4 0 ) + ( 4 2 )( 1 1 ) + ( 4 4 )( 2 2 )} x4− {( 4 2 )( 1 0 ) + ( 4 4 )( 2 1 )} x2+ ( 4 4 )( 2 0 ) (iv) T5(x) = 16x5− 20x3+ 5x = {( 5 0 ) + ( 5 2 )( 1 1 ) + ( 5 4 )( 2 2 )} x5− {( 5 2 )( 1 0 ) + ( 5 4 )( 2 1 )} x3+ ( 5 4 )( 2 0 ) x (v) T6(x) = 32x6− 48x4+ 18x2− 1 = {( 6 0 ) + ( 6 2 )( 1 1 ) + ( 6 4 )( 2 2 ) + ( 6 6 )( 3 3 )} x6 +(−1) {( 6 2 )( 1 0 ) + ( 6 4 )( 2 1 ) + ( 6 6 )( 3 2 )} x4 + {( 6 4 )( 2 0 ) + ( 6 6 )( 3 1 )} x2 +(−1) {( 6 6 )( 3 0 )} x0 つぎに第2種チェビシェフ多項式を求めます。 Un(cos θ) = sin(n + 1)θ sin θ = ( n + 1 1 ) cosnθ− ( n + 1 3 ) cosn−2θ sin2θ + ( n + 1 5 ) cosn−4θ sin4θ− · · ·
ここで前と同様に、sin2θ = 1−cos2θ, sin4θ = 1−
( 2 1 ) cos2θ + ( 2 2 ) cos4θ, sin6θ = 1− ( 3 1 ) cos2θ + ( 3 2 ) cos4θ− ( 3 3 ) cos6θ,· · · から2項係数をもちい、変数x = cos θとおいて (i) U2(x) = 4x2− 1 = {( 3 1 ) + ( 3 3 )( 1 1 )} x2− ( 3 3 )( 1 0 ) (ii) U3(x) = 8x3− 4x = {( 4 1 ) + ( 4 3 )( 1 1 )} x3− ( 4 3 )( 1 0 ) x (iii) U4(x) = 16x4− 12x2+ 1 = {( 5 1 ) + ( 5 3 )( 1 1 ) + ( 5 5 )( 2 2 )} x4− {( 5 3 )( 1 0 ) + ( 5 5 )( 2 1 )} x2+ ( 5 5 )( 2 0 ) (iv) U5(x) = 32x5− 32x3+ 6x = {( 6 1 ) + ( 6 3 )( 1 1 ) + ( 6 5 )( 2 2 )} x5− {( 6 3 )( 1 0 ) + ( 6 5 )( 2 1 )} x3+ ( 6 5 )( 2 0 ) x (v) U6(x) = 64x6− 80x4+ 24x2− 1 = {( 7 1 ) + ( 7 3 )( 1 1 ) + ( 7 5 )( 2 2 ) + ( 7 7 )( 3 3 )} x6 +(−1) {( 7 3 )( 1 0 ) + ( 7 5 )( 2 1 ) + ( 7 7 )( 3 2 )} x4 + {( 7 5 )( 2 0 ) + ( 7 7 )( 3 1 )} x2 +(−1) {( 7 7 )( 3 0 )} x0
これらの観察から、つぎの関係式が(3.1), (3.2) の意図するものである。たとえば、 •ルーカス数と第1種チェビシェフ多項式：n = 7の場合 L7= 29 = {( 7 0 ) + ( 7 2 )( 1 1 ) + ( 7 4 )( 2 2 ) + ( 7 6 )( 3 3 )} /26 + {( 7 2 )( 1 0 ) + ( 7 4 )( 2 1 ) + ( 7 6 )( 3 2 )} /24 + {( 7 4 )( 2 0 ) + ( 7 6 )( 3 1 )} /22 + {( 7 6 )( 3 0 )} /20 (3.5) なぜならば T7(x) = 64x7− 112x5+ 56x3− 7x = {( 7 0 ) + ( 7 2 )( 1 1 ) + ( 7 4 )( 2 2 ) + ( 7 6 )( 3 3 )} x7 +(−1) {( 7 2 )( 1 0 ) + ( 7 4 )( 2 1 ) + ( 7 6 )( 3 2 )} x5 + {( 7 4 )( 2 0 ) + ( 7 6 )( 3 1 )} x3 +(−1) {( 7 6 )( 3 0 )} x1 したがってx =−i/2を代入すれば L7= 29 = 2∗ i7∗ T7(−i/2) = 64/26+ 112/24+ 56/22+ 7 = 1 + 7 + 14 + 7 = {( 7 0 ) + ( 7 2 )( 1 1 ) + ( 7 4 )( 2 2 ) + ( 7 6 )( 3 3 )} /26 + {( 7 2 )( 1 0 ) + ( 7 4 )( 2 1 ) + ( 7 6 )( 3 2 )} /24 + {( 7 4 )( 2 0 ) + ( 7 6 )( 3 1 )} /22 + {( 7 6 )( 3 0 )} /20 •フィボナッチ数と第２種チェビシェフ多項式：n = 8の場合 F8= 21 = {( 8 1 ) + ( 8 3 )( 1 1 ) + ( 8 5 )( 2 2 ) + ( 8 7 )( 3 3 )} /27 + {( 8 3 )( 1 0 ) + ( 8 5 )( 2 1 ) + ( 8 7 )( 3 2 )} /25 + {( 8 5 )( 2 0 ) + ( 8 7 )( 3 1 )} /23 + {( 8 7 )( 3 0 )} /2 = ( 7 0 ) + ( 6 1 ) + ( 5 2 ) + ( 4 3 ) (3.6)
なぜならば、 U7(x) = 128x7− 192x5+ 80x3− 8x = {( 8 1 ) + ( 8 3 )( 1 1 ) + ( 8 5 )( 2 2 ) + ( 8 7 )( 3 3 )} x7 +(−1) {( 8 3 )( 1 0 ) + ( 8 5 )( 2 1 ) + ( 8 7 )( 3 2 )} x5 + {( 8 5 )( 2 0 ) + ( 8 7 )( 3 1 )} x3 +(−1) {( 8 7 )( 3 0 )} x1 であるから、x =−i/2を代入して F8= 21 = i7∗ U7(−i/2) = 128/27+ 192/25+ 80/23+ 8/2 = 1 + 6 + 10 + 4 = {( 8 1 ) + ( 8 3 )( 1 1 ) + ( 8 5 )( 2 2 ) + ( 8 7 )( 3 3 )} /27 + {( 8 3 )( 1 0 ) + ( 8 5 )( 2 1 ) + ( 8 7 )( 3 2 )} /25 + {( 8 5 )( 2 0 ) + ( 8 7 )( 3 1 )} /23 + {( 8 7 )( 3 0 )} /2 となり、2項係数の関係はさらに ( 8 1 ) + ( 8 3 )( 1 1 ) + ( 8 5 )( 2 2 ) + ( 8 7 )( 3 3 ) = 27 ( 7 0 ) ( 8 3 )( 1 0 ) + ( 8 5 )( 2 1 ) + ( 8 7 )( 3 2 ) = 25 ( 6 1 ) ( 8 5 )( 2 0 ) + ( 8 7 )( 3 1 ) = 23 ( 5 2 ) ( 8 7 )( 3 0 ) = 21 ( 4 3 ) が成り立つから、フィボナッチ数と第2種チェビシェフ多項式の合性はよくて、式(3.6)が示されました。 一般式も同様に得られるのは明らか。このようにフィボナッチ数、ルーカス数を2項係数の積和で表す関係式が得 られました。ルーカス数は簡潔とはいいがたいのですが、複素数iの周期性をつかい、プラスマイナスの符号を調整 されていて、すべて正の和の形となっています。
3.6
３斜め要素からの行列式で
少し脇道になりますが、３斜め要素からのn次正方行列Mnにおける行列式Dnを展開すると列または行の余因 数展開から、行列式Dn= det Mn は Dn = det a b 0 0 · · · 0 c a b 0 · · · 0 0 c a b · · · 0 0 0 c a · · · 0 · · · · 0 0 0 c a b 0 0 0 0 c a = det 1 √−1 0 0 · · · 0 √ −1 1 √−1 0 · · · 0 0 √−1 1 √−1 · · · 0 0 0 √−1 1 · · · 0 · · · · · · · · · · · · · · · · · · 0 0 0 √−1 1 √−1 0 0 0 0 √−1 1 ですから、 Dn= a Dn−1− bc Dn−2= Dn−1+ Dn−2 (3.7) が得られます。この関係式から、a = x, b = c =√(−1)y とおけば、フィボナッチ多項式が得られ、x = 1, y =−1 とおくことでフィボナッチ数列が得られます。複素数が再帰関係式との結びつきをもたらしています[Cahill etc. FQ41(2003)]。 ならば、トリボナッチは？としてみましたが、上手くいきませんでした。3.7
ルーカス数
(Lucas)
Fibonacci の場合には、第2種チェビシェフ多項式をもちいた展開式が2項係数の積和とまとめることができて、 さらに簡潔、単純な2項係数の和となりました。しかしルーカス数では、第1種チェビシェフ多項式からの展開式を 2項係数との積和とはなりますが、2項係数に分数をかけて重みをつけます。 定理1 Lm = {( m 0 ) + ( m 2 )( 1 1 ) + ( m 4 )( 2 2 ) + ( m 6 )( 3 3 ) +· · · · } /2m−1 + {( m 2 )( 1 0 ) + ( m 4 )( 2 1 ) + ( m 6 )( 3 2 ) +· · · · } /2m−3 + {( m 4 )( 2 0 ) + ( m 6 )( 3 1 ) +· · · · } /2m−5 + {( m 6 )( 3 0 ) +· · · · } /2m−7 +· · · · = ∑ {(k,j):k+j=m} ( k j ) m k (3.8)3.8
ペリン数列（
Perrin
）
Perrin数列(OEIS:A001608)の再帰関係はa(n) = a(n− 2) + a(n − 3) with a(0) = 3, a(1) = 0, a(2) = 2. (3.9) OEIS:A050443数列の再帰関係は
a(0) = 4, a(1) = 0, a(2) = 0, a(3) = 3; thereafter a(n) = a(n− 3) + a(n − 4). (3.10)
で定義します。 上のコミックスでの1コマ、2コマ目がフィボナッチ数列で、4コマ目がペリン数列です。既に述べた3.1節でフィ ボナッチ数列を２項係数で表しました。それを一般式で表せば、つぎの式となります。 定理2 Fm+1 = ∑ {(n,r);n+r=m} ( n r ) (3.11) 例えば、 1. m = 6のとき: {(n, r) : 6 = n + r, n ≥ r} = {(6, 0), (5, 1), (4, 2), (3, 3)}ですから、
( 6 0 ) + ( 5 1 ) + ( 4 2 ) + ( 3 3 ) = 1 + 5 + 6 + 1 = 13 = F7 2. m = 7のとき: {(n, r) : 7 = n + r, n ≥ r} = {(7, 0), (6, 1), (5, 2), (4, 3)}ですから、 ( 7 0 ) + ( 6 1 ) + ( 5 2 ) + ( 4 3 ) = 1 + 6 + 10 + 4 = 21 = F8 3. m = 8のとき: {(n, r) : 8 = n + r, n ≥ r} = {(8, 0), (7, 1), (6, 2), (5, 3), (4, 4)}で、 ( 8 0 ) + ( 7 1 ) + ( 6 2 ) + ( 5 3 ) + ( 4 4 ) = 1 + 7 + 15 + 10 + 1 = 34 = F9 [注意] 2項係数 ( α r ) は 非負整数r = 0, 1, 2,· · · に対して定めて, r < 0では ( α r ) = (α)r r! = 0とする。またn < r では ( n r ) = 0 となる。 【ペリン数列】 Pn = Pn−2+ Pn−3; P0= 3, P1= 0, P2= 2 n : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Pn : 3 0 2 3 2 5 5 7 10 12 17 22 29 39 51 68 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 90 119 158 209 277 367 486 644 853 1130 1497 1983 2627 3480 4610 ペリン数列はフィボナッチ数と異なり、トビの項を考慮するから、多少、和のインデックスが複雑になるが、基本 的には、項の拾い上げであり、線形式の整数点を通るような具体式を定めればよい。 定理3 mを与えられた自然数とするとき、 Pm= ∑ {(n,r):2n+r=m} ( n r ) m n (3.12) 例題：以前に挙げているペリン数列の表ではP30までしかありませんから、続きのP31, P32, P33, P34まで計算して から確認します。和の条件は{(n, r) : 2n + r = m}ですから、2項係数がゼロになる場合; n < r は必要ありません。 1. m = 31のとき：集合は{(n, r) : 31 = 2n + r, n ≥ r} = {(15, 1), (14, 3), (13, 5), (12, 7), (11, 9)}で、計算 式は {( 15 1 ) 31 15 + ( 14 3 ) 31 14 + ( 13 5 ) 31 13 + ( 12 7 ) 31 12 + ( 11 9 ) 31 11 } = 31{1 + 26 + 99 + 66 + 5} = 31 · 197 = 6107 = P31 2. m = 32 = 2·16のとき：集合は{(n, r) : 32 = 2n+r, n ≥ r} = {(16, 0), (15, 2), (14, 4), (13, 6), (12, 8), (11, 10)} で、 計算式は {( 16 0 ) 32 16 + ( 15 2 ) 32 15 + ( 14 4 ) 32 14 + ( 13 6 ) 32 13 + ( 12 8 ) 32 12 + ( 11 10 ) 32 11 } = 32{1/16 + 7 + 143/2 + 132 + 165/4 + 1} = 32·4045 16 = 8090 = P32 3. m = 33のとき：{(n, r) : 33 = 2n + r, n ≥ r} = {(16, 1), (15, 3), (14, 5), (13, 7), (12, 9), (11, 11)}で、 {( 16 1 ) 33 16 + ( 15 3 ) 33 15+ ( 14 5 ) 33 14 + ( 13 7 ) 33 13 + ( 12 9 ) 33 12 + ( 11 11 ) 33 11 } = 33{1 + 91/3 + 143 + 132 + 55/3 + 1/11} = 33·10717 33 = 10717 = P33
4. m = 34 = 2 · 17 の と き： こ の 17 は 素 数 で す 。 集 合 は {(n, r) : 34 = 2n + r, n ≥ r} = {(17, 0), (16, 2), (15, 4), (14, 6), (13, 8), (12, 10)}ですから、 {( 17 0 ) 34 17 + ( 16 2 ) 34 16+ ( 15 4 ) 34 15 + ( 14 6 ) 34 14 + ( 13 8 ) 34 13 + ( 12 10 ) 34 10 } = 34{1/17 + 15/2 + 91 + 429/2 + 90 + 11/2} = 34·14197 34 = 14197 = P34 ペリン数の素因数分解もおもしろいのですよ。 P31 = 6107 = 31· 197, P32= 8090 = 2· 5 · 809, P33= 10717 = 7· 1531, P34 = 14197 = 1· 14197(34/2 = 17は素数の反映?),· · ·
3.9
A050443
数列
OEIS：A050443数列はa(0) = 4, a(1) = 0, a(2) = 0, a(3) = 3; a(n) = a(n− 3) + a(n − 4)
で定義されています。いままでのフィボナッチ数列が F (0) = 0, F (1) = 1; F (n) = F (n− 1) + F (n − 2) ⇐⇒ F (n) = ∑ {(k,j);k+j=n−1} ( k j ) ルーカス数列が L(0) = 2, L(1) = 1; L(n) = L(n− 1) + L(n − 2) ⇐⇒ L(n) = ∑ {(k,j);k+j=n} ( k j ) n k つぎのペリン数列が P (0) = 3, P (1) = 0, P (2) = 2; P (n) = P (n− 2) + P (n − 3) ⇐⇒ ∑ {(k,j);2k+j=n} ( k j ) n k でした。この一般項Qn= a(n)を2項係数ではつぎのようになります。 定理4 Qm= ∑ {(k,j);3k+j=m} ( k j ) m k ルーカス数列での和の条件式2k + j = m を 3k + j = mに変えてみるとこんな数列が出来ました。 k : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 · · · Qk: 4 0 0 3 4 0 3 7 4 3 10 11 7 13 21 18 20 · · · すこし具体的に計算してみます。 n (i, j) : 3i + j = n ( i j ) n i 3 ; (1, 0) ( 1 0 ) 3 1 = 3 4 ; (1, 1) ( 1 1 ) 4 1 = 4 5 ; (1, 2) ( 1 2 ) 5 1 = 0 6 ; (1, 3), (2, 0) ( 1 3 ) 6 1 + ( 2 0 ) 6 2 = 3 7 ; (1, 4), (2, 1) ( 1 4 ) 7 1 + ( 2 1 ) 7 2 = 7 8 ; (1, 5), (2, 2) ( 1 5 ) 8 1 + ( 2 2 ) 8 2 = 4 n (i, j) : 3i + j = n ( i j ) n i 9 ; (3, 0) ( 3 0 ) 9 3 = 3 10 ; (3, 1) ( 3 1 ) 10 3 = 10 11 ; (3, 2) ( 3 2 ) 11 3 = 11 12 ; (3, 3), (4, 0) ( 3 3 ) 12 3 + ( 4 0 ) 12 4 = 7 13 ; (4, 1) ( 4 1 ) 13 4 = 13 14 ; (4, 2) ( 4 2 ) 14 4 = 21 紙の余白がなくなった！
