Elementare Zahlentheorie WS 2003/04
[Zur
vorangehenden
Stunde (22.01.04),
zur
nächsten
Stunde (27.01.04),
zur
Protokollübersicht]
Stundenprotokoll
zum 23.01.2004 (MP)
Inhalt: § 9 C: Fibonacci-Folgen (Vortrag CM)
Verhältniszahlen
des Goldenen Schnittes
1 :
0,6 21 : 13,0 41
: 25,3 61 : 37,7 81 : 50,1
2 : 1,2 22
: 13,6 42 : 26,0 62 : 38,3 82 : 50,7
3 :
1,9 23 : 14,2 43 : 26,6 63 : 38,9 83
: 51,3
4 : 2,5 24
: 14,8 44 : 27,2 64 : 39,6 84 : 51,9
5 : 3,1 25
: 15,5 45 : 27,8 65 : 40,2 85 : 52,5
6 : 3,7 26
: 16,1 46 : 28,4 66 : 40,8 86 : 53,2
7 : 4,3 27
: 16,7 47 : 29,0 67 : 41,4 87 : 53,8
8 : 4,9 28
: 17,3 48 : 29,7 68 : 42,0 88 : 54,4
9 : 5,6 29
: 17,9 49 : 30,3 69 : 42,6 89 : 55,0
10 : 6,2 30 : 18,5 50 : 30,9 70
: 43,3 90 : 55,6
11 : 6,8 31 : 19,2 51 : 31,5 71
: 43,9 91 : 56,2
12 : 7,4 32 : 19,8 52 : 32,1 72
: 44,5 92 : 56,9
13 :
8,0 33 : 20,4 53 : 32,8 73
: 45,1 93 : 57,5
14 : 8,7 34 :
21,0 54 : 33,4 74 : 45,7 94 : 58,1
15 : 9,3 35 : 21,6 55 : 34,0 75 : 46,4 95 : 58,7
16 : 9,9 36 : 22,2 56 : 34,6 76
: 47,0 96 : 59,3
17 : 10,5 37 :
22,9 57 : 35,2 77 : 47,6 97 : 59,9
18 : 11,1 38 :
23,5 58 : 35,8 78 : 48,2 98 : 60,6
19 : 11,7 39 :
24,1 59 : 36,5 79 : 48,8 99 : 61,2
20 : 12,4 40 :
24,7 60 : 37,1 80 : 49,4 100 : 61,8
Erklärung der Zahlen anhand eines Beispiels:
13 : 8,0 à Länge von 13 cm; nach 8 cm setzt man den
goldenen Schnitt.
13, 21, 34, 55, 89 haben ein gerades
Verhältnis. Sie sind Fibonacci-Zahlen!
Fibonacci-Folge:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Definition: 
Formel
von Binet
:
Fibonacci (1180 – 1250):
Er hieß ursprünglich Leonardo von Pisa und
war der Sohn eines Kaufmannes von Bonacci (filius de Bonacci à Fibonacci). Sein Vater betrieb viel Handel
in arabischen Ländern, zudem hatte Fibonacci arabische Lehrer, so dass er mit
den Rechenmethoden und der Mathematik der Araber bekannt wurde und diese in
Europa einführte.
1. Beispiel: Kaninchenaufgabe
(i)
Jedes Paar ist ab dem 2. Monat gebärfähig.
(ii)
Jedes Paar bringt von da an ein neues Paar zur Welt.
(∞)
Alle Kaninchen leben ewig.
Monat Paare
0 / O: gebärfähig
1 X X:
nicht gebärfähig
2 O
3
X O
4 O
X O
5 X O
O X O
6
O X O X
O O X O
Die Fibonacci-Folge ist die Lösung dieser
Aufgabe!
2. Beispiel:
Ein Briefträger muss jeden Tag 40 Stufen
hinaufgehen. Die erste Stufe betritt er immer. Ab der zweiten Stufe hat er die
Wahl, eine oder zwei Stufen auf einmal zu nehmen. Wie viele Möglichkeiten gibt
es, zur vierzigsten Stufe zu gelangen?
(Die Lösung ist auch wieder die
Fibonacci-Folge.)
Φ
und Fibonacci
Zu zeigen: (i) u verhält sich wie die Fibonacci-Folge: 
(ii)
Lucas-Folge
Beweis: (i) 
Lucas-Folge
Für jede Lucas-Folge 
und für alle k
≥ 2 gilt:
.
Daraus folgt
,
.
Beweis zur Formel von Binet:
Besprechung
der Aufgabe 7
Mit dem PC:
-
Spalten für 
definieren,
-
wegfallen lassen,
-
rekursiv berechnen.
|
k |
x |
y |
|
-1 |
1 |
0 |
|
0 |
0 |
1 |
|
1 |
1 – 1∙0 = 1 |
0 - 1∙1 = -1 |
|
2 |
0 –
1 = -1 |
1 +
1 = 2 |
|
3 |
1 +
1 = 2 |
-3 |
|
4 |
-1 –
2 = -3 |
5 |
|
5 |
5 |
-8 |
|
6 |
-8 |
|
?
