Hans Walser, [20260525]
Binets Formel
Verallgemeinerung der Formel von Binet.
Gegeben sei eine Folge fn mit der verallgemeinerten Fibonacci-Rekursion
(1) fn = p fn–1 + q fn–2
und den beliebigen Startwerten f1 und f2.
Gesucht ist eine explizite Formel für die Berechnung von fn in Abhängigkeit von n.
Wir definieren:
(2) c1 = (p + √(p2 + 4q))/2, c2 = (p – √(p2 + 4q))/2
Dies sind die beiden Lösungen der quadratischen Gleichung c2 – p c – q = 0 für c.
Damit machen wir den Ansatz:
(3) fn = a c1n + b c2n
Wir bilden also einen Linearkombination der beiden geometrischen Folgen c1n und c2n, welche beiden der Rekursion (1) genügen.
Für die Berechnung der Koeffizienten a und b verwenden wir die Startwerte f1 und f2. Wir erhalten das lineare Gleichungssystem:
(4) f1 = a c11
+ b c21
f2 = a c12
+ b c22
Die Lösungen a und b setzen wir in (3) ein. Das ist die gesuchte explizite Formel.
Für p = 1, q = 1, f1 = 1 und f2 = 1 erhalten wir die klassische Fibonacci-Folge (Tab. 1).
|
n |
fn |
|
1 |
1 |
|
2 |
1 |
|
3 |
2 |
|
4 |
3 |
|
5 |
5 |
|
6 |
8 |
|
7 |
13 |
|
8 |
21 |
|
9 |
34 |
|
10 |
55 |
Tab. 1: Klassische Fibonacci-Folge
Für p = 1, q = –1, f1 = 3 und f2 = 4 erhalten wir eine periodische Folge (Tab. 2). Sie ist antiperiodisch mit der Periodenlänge 3 und periodisch mit der Periodenlänge 6.
|
n |
fn |
|
1 |
3 |
|
2 |
4 |
|
3 |
1 |
|
4 |
–3 |
|
5 |
–4 |
|
6 |
–1 |
|
7 |
3 |
|
8 |
4 |
|
9 |
1 |
|
10 |
–3 |
Tab. 2: Periodische Folge
Für p = i, q = 1, f1 = 3 und f2 = 4 erhalten wir eine periodische Folge mit komplexen Zahlen (Tab. 3). Sie ist antiperiodisch mit der Periodenlänge 6 und periodisch mit der Periodenlänge 12. Weiter ist fn+3 = ifn.
|
1 |
3 |
|
2 |
4 |
|
3 |
3 + 4i |
|
4 |
3i |
|
5 |
4i |
|
6 |
–4 + 3i |
|
7 |
–3 |
|
8 |
–4 |
|
9 |
–3 – 4i |
|
10 |
–3i |
|
11 |
–4i |
|
12 |
4 – 3i |
|
13 |
3 |
|
14 |
4 |
|
15 |
3 + 4i |
|
16 |
3i |
|
17 |
4i |
|
18 |
–4 + 3i |
|
19 |
–3 |
|
20 |
–4 |
Tab. 3: Komplexe Werte