Beschreibung
Die Fibbonacci Zahlen ist die Zahlenfolge, die man erhält, wenn man beginnend mit 0 und 1 rekursiv die zwei letzten Zahlen der Folge addiert.
Man erhält dann: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
Verallgemeinerungen
Negative Zahlen
Durch Ausprobieren erhalten wir die Folge -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8. Diese Fibbonaccie Zahlen sind also auch in die andere Richung fortsetzbar.
Komplexe Zahlen
Indem man statt natürlichen Indizes, reelle in die untere Formel einsetzt, erhält man Zahlen, die komplexwertig sind.
Eigenschaften
Wachstumsfaktor
Die Fibbonacci-Zahlen wachsen mit exponentieller Geschwindigkeit. Demnach sollten sie so etwas wie einen relativen Wachstumsfaktor haben.
Nimmt man den Quotient zweier Zahlen, so nähert sich dieser an an.
Der Wachstumsfaktor ist nah am Verhältnis zwischen Meilen und Kilometer (). Mit Hilfe der Fibbonacci Zahlen, könnte man also zwischen den Maßen umrechnen:
Algebraischer Beschreibung
Die Fibbonacci-Zahlen lassen sich auch durch die Formel berechnen.
ggT konsekutiver Fib- Zahlen
, denn Wählen wir nun den Induktionsanfang , so sehen wir, das die Aussage stimmt.
ggT der Fibbonacci Zahlen
Wählt man die Konvention , dann gilt
Übungen
McEliece Aufgabe 2-4
a)
Was ist ? Siehe oben
b)
Was sind die beim Berechnen des Euklidischer Algorithmus für ?
| -1 | 1 | 0 | fib(n+1) | - |
| 0 | 0 | 1 | fib(n) | - |
| 1 | 1 | -1 | fib(n-1) | 1 |
| 2 | -1 | 2 | fib(n-2) | 1 |
| 3 | 2 | -3 | fib(n-3) | 1 |
| 4 | -fib(4) | fib(5) | fib(n-4) | 1 |
| … | … | … | … | … |
| i | 1 | |||
| … | … | … | … | … |
| 1 | ||||
| 1 | ||||
| 2 |
c)
Stelle als Linearkombination dar.
elieceFiniteFieldsComputer2012]]