ルーカス数の bisection と連分数
安田 正實
Febuary 13 (Sat), 2016 at Sasebo
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
1/
26
Outline
Content
1
はじめに
難問題ベスト
黄金比から始めると
2
連分数からのアプローチ
3
生成母関数
2 次関数の分割：最適値との関係式
4
連分数を登場させる
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
2/
26
はじめに
難問題ベスト
きっかけは
フィボナッチ数に纏わる話は、アマチュア数学（造語）では最も人気が
高いもののひとつではなかろうか？
前回（秋田県立大での研究会）にも、ガロアの５次式やＭＡＡ
(MathAmerAssoc) ロゴにある黄金比が関わりを見出せることの話をさせ
てもらった。
ここでは一般大衆向けに書かれた「数学難問 BEST100」小野田博一（Ｐ
ＨＰエディターズ 2015 年）にある「連分数と黄金比」(Ａ６０) の話を紹
介する。
オリジナルはどこか、と探せば、結果はＯＥＩＳ (R)（Online
Encyclopedia of Integer Sequences）であった。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
3/
26
はじめに
難問題ベスト
Contents
黄金比
fibonacci 数
Lucas 数
べき乗の展開式
連分数
生成母関数
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
4/
26
はじめに
難問題ベスト
Contents
黄金比
fibonacci 数
Lucas 数
べき乗の展開式
連分数
生成母関数
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
4/
26
はじめに
難問題ベスト
Contents
黄金比
fibonacci 数
Lucas 数
べき乗の展開式
連分数
生成母関数
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
4/
26
はじめに
難問題ベスト
Contents
黄金比
fibonacci 数
Lucas 数
べき乗の展開式
連分数
生成母関数
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
4/
26
はじめに
黄金比から始めると
黄金比の値は
ϕ=
√
1+ 5
2 ;
1
ϕ=1+
1+
ψ=
ϕ2 = ϕ + 1;
√
1− 5
2 ;
安田 正實
1
ϕ
= [ 1; 1 ]
1
1+
ϕ=1+
1
1+
..
.
ψ = 1 − ϕ = − ϕ1
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
5/
26
はじめに
黄金比から始めると
黄金比の値は
ϕ=
√
1+ 5
2 ;
1
ϕ=1+
1+
ψ=
ϕ2 = ϕ + 1;
√
1− 5
2 ;
安田 正實
1
ϕ
= [ 1; 1 ]
1
1+
ϕ=1+
1
1+
..
.
ψ = 1 − ϕ = − ϕ1
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
5/
26
はじめに
黄金比から始めると
黄金比の値は
ϕ=
√
1+ 5
2 ;
1
ϕ=1+
1+
ψ=
ϕ2 = ϕ + 1;
√
1− 5
2 ;
安田 正實
1
ϕ
= [ 1; 1 ]
1
1+
ϕ=1+
1
1+
..
.
ψ = 1 − ϕ = − ϕ1
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
5/
26
はじめに
黄金比から始めると
黄金比のべき乗値は
例の本に付け加えて、べき乗を繰り返すと、
(
)
1
1
2
ϕ =ϕ+1= 1+
+1=2+
ϕ
ϕ
√
(
√ )
√
4+2 5
ϕ3 = 2ϕ + 1 = 2 + 5 =
= 4 + −2 + 5
2
1
1
√ = 4 + 3 = [4; 4]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F3 ϕ2 + F2 ϕ = F3 (ϕ + 1) + F2 ϕ = F4 ϕ + F3
2
(
√
√ )
(
)−1
−11
+
5
11
+
5
5
5
2
5
√
ϕ =
= 11 +
= 11 +
2
2
11 + 5 5
1
= 11 + 5 = [ 11 ; 11 ]
ϕ
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
6/
26
はじめに
黄金比から始めると
黄金比のべき乗値は
例の本に付け加えて、べき乗を繰り返すと、
(
)
1
1
2
ϕ =ϕ+1= 1+
+1=2+
ϕ
ϕ
√
(
√ )
√
4+2 5
ϕ3 = 2ϕ + 1 = 2 + 5 =
= 4 + −2 + 5
2
1
1
√ = 4 + 3 = [4; 4]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F3 ϕ2 + F2 ϕ = F3 (ϕ + 1) + F2 ϕ = F4 ϕ + F3
2
(
√
√ )
(
)−1
−11
+
5
11
+
5
5
5
2
5
√
ϕ =
= 11 +
= 11 +
2
2
11 + 5 5
1
= 11 + 5 = [ 11 ; 11 ]
ϕ
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
6/
26
はじめに
黄金比から始めると
黄金比のべき乗値は
例の本に付け加えて、べき乗を繰り返すと、
(
)
1
1
2
ϕ =ϕ+1= 1+
+1=2+
ϕ
ϕ
√
(
√ )
√
4+2 5
ϕ3 = 2ϕ + 1 = 2 + 5 =
= 4 + −2 + 5
2
1
1
√ = 4 + 3 = [4; 4]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F3 ϕ2 + F2 ϕ = F3 (ϕ + 1) + F2 ϕ = F4 ϕ + F3
2
(
√
√ )
(
)−1
−11
+
5
11
+
5
5
5
2
5
√
ϕ =
= 11 +
= 11 +
2
2
11 + 5 5
1
= 11 + 5 = [ 11 ; 11 ]
ϕ
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
6/
26
はじめに
黄金比から始めると
黄金比のべき乗値は
例の本に付け加えて、べき乗を繰り返すと、
(
)
1
1
2
ϕ =ϕ+1= 1+
+1=2+
ϕ
ϕ
√
(
√ )
√
4+2 5
ϕ3 = 2ϕ + 1 = 2 + 5 =
= 4 + −2 + 5
2
1
1
√ = 4 + 3 = [4; 4]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F3 ϕ2 + F2 ϕ = F3 (ϕ + 1) + F2 ϕ = F4 ϕ + F3
2
(
√
√ )
(
)−1
−11
+
5
11
+
5
5
5
2
5
√
ϕ =
= 11 +
= 11 +
2
2
11 + 5 5
1
= 11 + 5 = [ 11 ; 11 ]
ϕ
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
6/
26
はじめに
ここで Fibonacci 数と
n ; 0, 1, 2, 3,
Fn ; 0, 1, 1, 2,
4,
3,
5,
5,
Lucas 数を並べると
n ; 0, 1, 2, 3,
Ln ; 2, 1, 3, 4,
4,
7,
5,
11,
6,
8,
6,
18,
黄金比から始めると
7,
13,
7,
29,
8,
21,
8,
47,
9,
34,
9,
76,
10
55
10
123
これらをもちいて、先の関係式で表れた数字を表してみると
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
7/
26
はじめに
黄金比から始めると
まとめると以下のように続けられる：
1
2
3
4
5
ϕ2 = ϕ + 1 = F1 ϕ + F0
(
√ )
√
1
+
5
ϕ3 = 2 + 5 = 2
+ 1 = F3 ϕ + F2
2
1
1
√ = L3 + 3 = [ L3 ; L3 ]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F4 ϕ + F3
2 √
1
11 + 5 5
= F5 ϕ + F4 = L5 + 5 = [ L5 ; L5 ]
ϕ5 =
2
ϕ
√
6
ϕ = 9 + 4 5 = F6 ϕ + F5
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
8/
26
はじめに
黄金比から始めると
まとめると以下のように続けられる：
1
2
3
4
5
ϕ2 = ϕ + 1 = F1 ϕ + F0
(
√ )
√
1
+
5
ϕ3 = 2 + 5 = 2
+ 1 = F3 ϕ + F2
2
1
1
√ = L3 + 3 = [ L3 ; L3 ]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F4 ϕ + F3
2 √
1
11 + 5 5
= F5 ϕ + F4 = L5 + 5 = [ L5 ; L5 ]
ϕ5 =
2
ϕ
√
6
ϕ = 9 + 4 5 = F6 ϕ + F5
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
8/
26
はじめに
黄金比から始めると
まとめると以下のように続けられる：
1
2
3
4
5
ϕ2 = ϕ + 1 = F1 ϕ + F0
(
√ )
√
1
+
5
ϕ3 = 2 + 5 = 2
+ 1 = F3 ϕ + F2
2
1
1
√ = L3 + 3 = [ L3 ; L3 ]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F4 ϕ + F3
2 √
1
11 + 5 5
= F5 ϕ + F4 = L5 + 5 = [ L5 ; L5 ]
ϕ5 =
2
ϕ
√
6
ϕ = 9 + 4 5 = F6 ϕ + F5
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
8/
26
はじめに
黄金比から始めると
まとめると以下のように続けられる：
1
2
3
4
5
ϕ2 = ϕ + 1 = F1 ϕ + F0
(
√ )
√
1
+
5
ϕ3 = 2 + 5 = 2
+ 1 = F3 ϕ + F2
2
1
1
√ = L3 + 3 = [ L3 ; L3 ]
=4+
ϕ
2+ 5
√
7+3 5
ϕ4 =
= F4 ϕ + F3
2 √
1
11 + 5 5
= F5 ϕ + F4 = L5 + 5 = [ L5 ; L5 ]
ϕ5 =
2
ϕ
√
6
ϕ = 9 + 4 5 = F6 ϕ + F5
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
8/
26
はじめに
黄金比から始めると
繰り返しを確かめると、数式処理ソフトの利用から奇数形
(2n + 1 = 3, 5, 7, · · · )
√
29 + 13 5
1
7
ϕ =
= 11 + 5 = [ 29 ; 29 ] = [ L7 ; L7 ]
2
ϕ
√
√
76 + 34 5
9
ϕ = 38 + 17 5 =
= [ 76 ; 76 ] = [ L9 ; L9 ]
2
√
199 + 89 5
ϕ11 =
= [ L11 ; L11 ]
2 √
521 + 233 5
ϕ13 =
= [ L13 ; L13 ]
2
√
√
1364
+
610
5
ϕ15 = 682 + 305 5 =
= [ L15 ; L15 ]
2
·········
以上をまとめると、
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
9/
26
はじめに
黄金比から始めると
繰り返しを確かめると、数式処理ソフトの利用から奇数形
(2n + 1 = 3, 5, 7, · · · )
√
29 + 13 5
1
7
ϕ =
= 11 + 5 = [ 29 ; 29 ] = [ L7 ; L7 ]
2
ϕ
√
√
76 + 34 5
9
ϕ = 38 + 17 5 =
= [ 76 ; 76 ] = [ L9 ; L9 ]
2
√
199 + 89 5
ϕ11 =
= [ L11 ; L11 ]
2 √
521 + 233 5
ϕ13 =
= [ L13 ; L13 ]
2
√
√
1364
+
610
5
ϕ15 = 682 + 305 5 =
= [ L15 ; L15 ]
2
·········
以上をまとめると、
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
9/
26
はじめに
黄金比から始めると
Theorem 2.1
黄金比のべき乗値 (Wells 1986) は
ϕn = Fn ϕ + Fn−1
n = 1, 2, 3 · · ·
Theorem 2.2
奇数のべき乗では
ϕ2n+1 = F2n+1 ϕ + F2n = [ L2n+1 ; L2n+1 ]
このように奇数の場合には（循環）連分数で表現される。リュカ数の奇
数をもちいるから、Bisection of Lucas sequence; a(n) = L(2*n+1 ) とよ
ぶ (OEIS A002878) の理由と考えている。
黄金比は無理数であるから、当然このように「循環」連分数で表される。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
10 /
26
連分数からのアプローチ
連分数から
もし黄金比ではなく、フィボナッチ数による分数形ではどうなるだろう
か？その準備として、連分数から考える。
いままでは、黄金比からのアプローチをしている。つまり有理数からで
はなく、極限をとった無理数からの表現であった。正確に OEIS
（A002878）の結果を述べるには、有理数の場合、つまり、分数
pn
, n = 1, 2, · · ·
qn
の有限数列の形から述べたものである。
したがって連分数をもちいた表現を考える。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
11 /
26
連分数からのアプローチ
連分数の形
連分数 [c0 ; c1 , c2 , · · · cn ] とは
[c0 ; c1 , c2 , · · · cn ] = c0 +
1
[c1 ; c2 , · · · cn ]
と定める。いま
pn = cn pn−1 + pn−2 n = 2, 3, · · · ,
p0 = c0
qn = cn qn−1 + qn−2 n = 2, 3, · · · ,
q0 = 1
および
と定めると
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
12 /
26
連分数からのアプローチ
分数の表現
pn
= [c0 ; c1 , c2 , · · · cn ]
qn
あるいは行列をもちいて
)(
)
(
)
(
pn pn−1
pn−1 pn−2
cn 1
=
qn qn−1
n−2
(qn−1 )q(
)1 0(
c0 1
c1 1
c
=
··· n
1 0
1 0
1
1
0
)
と表されることに注意する。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
13 /
26
連分数からのアプローチ
正確に OEIS（A002878）の結果を述べるには、有理数つまり、分数
pn
, n = 1, 2, · · · の有限数列から記す。
qn
Theorem 3.1
{Fn ; n = 1, 2, · · · } を F0 = 0, F1 = 1 としたフィボナッチ数をするとき、
F(2n+1)∗(k+1)
= [L2n+1 ; L2n+1 , L2n+1 , · · · , L2n+1 ] k = 1, 2, 3, · · ·
F(2n+1)∗k
ここで連分数のカッコ [x1; x2, · · · , xk] 内の要素数は k 個とする。
たとえば、(B.Cloitre, 2003)
(
)
F12
144
F3∗4
72
1
=
=
=
=4+
= [4; 4, 4]
F3∗3
F9
34
17
4 + 14
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
14 /
26
生成母関数
「数学難問」には、生成母関数の結果も述べている。
Theorem 4.1
z2
z +1
− 3z + 1
=
1
z
=
L1
z
+
4
z2
+
L3
z2
→ ϕ2n+1
安田 正實
+
11
z3
+
L5
z3
+
29
z4
+
L7
z4
+
76
z5
+
L9
z5
+ ···
+ ···
(k → ∞)
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
15 /
26
生成母関数
この左辺の多項式は
√
√
3+ 5
3− 5
z − 3z + 1 = (z −
)(z −
)
2
2
2
と因数分解できる。
これから、黄金比 ϕ =
ϕ+1=
分母は
ϕ2
=
√
1+ 5
とその双対比 ϕ
2 √
√
2
3+ 5
3− 5
から、
2 , ϕ =
2
=
√
1− 5
2
の値から、
2
z 2 − 3z + 1 = (z − ϕ2 )(z − ϕ )
√
√
√
√
= ( z − ϕ)( z + ϕ)( z − ϕ)( z + ϕ)
という関係も成り立つのでもう少しわかりやすい形にも変形できるかも
知れない。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
16 /
26
生成母関数
また
1
1 ϕ2 ϕ4 ϕ6
+ 2 + 3 + 4 + ···
=
z − ϕ2
z
z
z
z
ϕ2n+1 = L(2n + 1) +
1
ϕ2n+1
= [L(2n + 1); L(2n + 1)]
などをつかって変形すると、さまざまな形が得られるかも知れない。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
17 /
26
生成母関数
2 次関数の分割：最適値との関係式
分割最適化（岩本・木村）
2 個の一定値を和に分解して、２乗評価の最小値では「フィボナッチ数
列」が最適となることを発見している。
初期値
c→
c の分割
xn−1 →
+
xn
2
2 乗評価の和 xn2 + xn−1
xn−1 の分割
xn−3 →
+
xn−2
2
2
xn−2
+ xn−3
xn−3 の分割
xn−5 →
x2 = 1 → 0
+
xn−4
···
与えられた c のうち、はじめの決定政策として xn を選び、c = xn + xn−1
の関係を持つよう分割する。つまり、残りの c − xn = xn−1 をつぎの状態
に受け渡して、この値を分割していく。順次繰り返す。数列の再帰関係
式、フィボナッチの生成規則になっている。したがって、最適値は
[ 2
]
2
2
2
min
(xn + xn−1
) + (xn−2
+ xn−3
) + ···
xn ,xn−1 ,xn−2 ,···
となる。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
18 /
26
生成母関数
2 次関数の分割：最適値との関係式
この値はフィボナッチ数列の２乗和：
2
2
2
Fn2 + Fn−1
+ Fn−2
+ Fn−3
+ · · · + F12 = Fn · Fn+1
という結果になる。最適な２次式がフィボナッチの生成規則が与えられ
た c = Fn に対して、決定政策 a = Fn−1 とし、つぎの状態が Fn−2 となっ
ていく。
(n 次状態) − (決定 a) = (n 次状態),
Fn − Fn−1 = Fn−2
[注] この再帰式は、カッシーニの公式
2
Fn+1
= Fn Fn+2 + (−1)n
と必要十分条件になることに興味ある。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
19 /
26
生成母関数
2 次関数の分割：最適値との関係式
Cassini の条件：
(−1)n = Fn+1 Fn−1 − Fn2
は行列のべき乗値の関係式：
(
)n (
)
Fn+1 Fn
1 1
=
Fn Fn−1
1 0
であるが、後での述べる、連分数での再帰関係を行列で表現するために
(
)
at +b
a b
·t =
c d
ct +d
と定める作用素 (·) の累次積に関係がありそうと思われる。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
20 /
26
生成母関数
2 次関数の分割：最適値との関係式
関係式は、
zn+1 =
2zn + 1
zn + 1
とみなし、zn = fn /gn とおくことで
fn+1
fn + (fn + gn )
=
gn+1
fn + gn
の再帰関係を見出せる。２乗和の関係は、Lucas 数列でも知られている。
L2n + L2n−1 + L2n−2 + L2n−3 + · · · + L21 = Ln · Ln+1 − L0
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
21 /
26
生成母関数
2 次関数の分割：最適値との関係式
たとえば、c = F5 = 5 とすると、この最小値は F5 · F4 で再帰関係式は、
F5 · F4 = F42 + F32 + F22 + F12
15 = 5 · 3 = 32 + 22 + 12 + 12
c = F8 = 13 とすると、この最小値は F5 · F4 で再帰関係式は、
F8 · F7 = F72 + F62 + · · · + F22 + F12
104 = 13 · 8 = 82 + 52 + 32 + 22 + 12 + 12
岩本・木村がユーチューブで解説した例である。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
22 /
26
生成母関数
2 次関数の分割：最適値との関係式
同様な最適関係として
係数に重みを入れた場合の最小化で、1 = x + (1 − x) の分割では
min {Ax 2 + B(1 − x)2 } = C
0≤x≤1
A
AB
B
, 1−x =
のとき、C =
である。
A+B
A+B
A+B
この関係はフィボナッチ数列をもちいて、A = 1/Fn , B = 1/Fn−1 などと
おくことで、
}
{ 2
(1 − x)2
1
x
+
=
min
0≤x≤1 Fn
Fn−1
Fn+1
となり、x =
と表すことができる。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
23 /
26
連分数を登場させる
連分数の定義
実は循環連分数を先に表していたが、
有限数列 {a0 , a1 , a2 , · · · , an } の作る連分数は [a0 ] = [a0 ; 0] = a0 ,
[a0 ; a1 , a2 , · · · , an ] = a0 +
1
[a1 ; a2 , a3 , · · · , an ]
で定めると
Theorem 5.1
[a0 ; a1 , a2 , · · · , an ] =
安田 正實
(
)(
)(
) (
)
a0 1
a1 1
a2 1
a
1
· · · n−1
· an
1 0
1 0
1 0
1
0
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
24 /
26
連分数を登場させる
少し計算すると
(
)
1
c0 c1 + 1
c 1
=
= 0
· c1
1 0
c1
c1
1
c2
c0 c1 c2 + c0 + c2
(ii) [c0 ; c1 , c2 ] = c0 +
= c0 +
=
1
c1 c2 + 1
c1 c2 + 1
c1 +
c2
(
)
c1 c2 + 1
c0 (c1 c2 + 1) + c2
c0 1
·
=
=
1 0
+1 )
c2
( c1 c)2 (
c0 1
c1 1
=
· c2
1 0
1 0
(iii) · · · · · ·
(i)
[c0 ; c1 ] = c0 +
以下は略します。
安田 正實
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
25 /
26
連分数を登場させる
OEIS
Theorem 5.2
フィボナッチ数列において
F(2n+1)∗(k+1)
=
F(2n+1)∗k
)k
(
L(2n + 1) 1
· L(2n + 1)
1
0
特に k → ∞ とすると (T.Ordowski(2013))
ϕ2n+1 = lim
k
安田 正實
F(2n+1)∗(k+1)
= [L(2n + 1); L(2n + 1)]
F(2n+1)∗k
ルーカス数の bisection と連分数
Febuary 13 (Sat), 2016 at Sasebo
26 /
26
© Copyright 2024 ExpyDoc
