Fibonacci und Goldener Schnitt

Fibonacci-Folge und Goldener Schnitt

Eine der bekanntesten Zahlenfolgen ist die Fibonacci-Folge. Sie ist ein schönes Beispiel für eine rekursiv definierte Folge, deren Rekursionsvorschrift sich wunderbar erzählen lässt. Darüber hinaus tauchen die Fibonacci-Zahlen in der Natur (z.B. in den spiralförmig aufgebauten Fruchtständen vieler Pflanzen) sowie in diversen mathematischen Zusammenhängen auf und erzeugen somit ein starkes Interesse.

Geschichtliches:

Die früheste bekannte Erwähnung dieser Zahlenfolge stammt aus Indien im 5. Jh v. Chr. Aber auch in der Antike war im Mittelmeerraum diese Folge z.B. bekannt.
Aber verbunden ist diese Zahlenfolge mit , der sie in seinem 'Buch der Rechenkunst' um 1227 mit seinem berühmten Kaninchen-Beispiel einführte: Kaninchen bekommen zum érsten Mal nach zwei Monaten und dann monatlich Nachwuchs in Form eines weiteren Kaninchenpaars. Selbstredend sterben sie niemals. Gefragt ist nach der Anzahl der Kaninchenpaare nach n Monaten.
Der Goldene Schnitt - das Aufteilungsverhältnis einer Strecke dergestalt, dass das Verhältnis der gesamten Strecke zum längeren Teil genau so groß ist wie das Verhältnis des längeren zum kürzeren Teil - findet sich erstmals bei Euklid um 300 v. Chr. Ein Zusammenhang mit der Fibonacci-Folge wurde erstmals im 16. Jh von einem unbekannten Leser in einer handchriftliche Anmerkung zu einer Euklid-Ausgabe hergestellt.

Inhalt

1. Fibonacci

1.1. Definition

1.2. Eigenschaften und Sätze

1.3. Formel von Binet

1. Fibonacci

1.1. Definition

Ausgehend von der Kaninchenaufgabe ist die n. Fibonaccizahl fib(n) definiert durch:

$ fib(n)~~ =~~\begin{cases}~~~~~~~~~~~~~~~~~~~~0~~~~~~~~~~~~~~~~~~~~,~falls~n=0\\~~~~~~~~~~~~~~~~~~~~1~~~~~~~~~~~~~~~~~~~~,~falls~n=1\\fib(n-1)+fib(n-2)~,~falls~n>1\end{cases}$

Die n. Fibonaccizahl ist demnach die Summe der beiden vorangehenden Fibonaccizahlen.
Die ersten Glieder der Fibonacci-Folge lauten:

n	0	1	2	3	4	5	6	7	8
fib(n)	0	1	1	2	3	5	8	13	21

Im 0. Monat (oft wird die Fibonacci-Folge auch erst für n > 0 definiert) gibt es noch kein Kaninchenpaar.
Nun mit vollständiger Induktion:
Induktionsanfang:
Im ersten Monat entsteht das erste Paar (durch göttliche Fügung oder einfach frisch geboren auf dem Wochenmarkt gekauft).
Im zweiten Monat gibt es noch keinen Nachwuchs.
Induktionsschritt:
Im (n+1). Monat besteht die Anzahl der Paare aus der Anzahl der Paare im n. Monat sowie aus dem Nachwuchs der Paare aus dem (n-1). Monat.

1.2. Eigenschaften und Sätze

Nachfolgend findet sich eine kleine Auswahl an Zusammenhängen zwischen Fibonaccizahlen:

1. $~~\displaystyle \sum_{k=0}^{n}fib(k)~=~fib(n+2)~-~1~~~~~~~~~~~~~~~~$

Der Beweis erfolgt nun mit Vollständiger Induktion:

Behauptung: $\forall n\ge 0~gilt:~\displaystyle \sum_{k=0}^{n} fib(k)~=~fib(n+2)-1$.
Induktionsanfang: $\displaystyle \sum_{k=0}^{0} fib(k)~=~fib(0)~=~0~=~fib(0+2)-1~=~1-1$

Induktionsannahme: Die Behauptung gilt für n: $\displaystyle \sum_{k=0}^{n} fib(k)~=~fib(n+2)-1$.

Induktionsrechnung: zu zeigen: Wenn die Behauptung für n gilt, dann auch für n+1.
$\displaystyle \sum_{k=0}^{n+1}fib(k)~=~\sum_{k=0}^{n} fib(k)+fib(n+1)~=~fib(n+2)-1~+~fib(n+1)~=~fib((n+1)+2)-1$

Induktionsschluss: Die Behauptung gilt für alle n.

2. $~~\displaystyle \sum_{k=1}^{n}fib(2k-1)~=~fib(2n)~~~~~~~~~~~~~~~~~~~~~$

Der Beweis erfolgt nun mit Vollständiger Induktion:

Behauptung: $\forall n\ge 1~gilt:~\displaystyle \sum_{k=1}^{n} fib(2k-1)~=~fib(2n)$.
Induktionsanfang: $\displaystyle \sum_{k=1}^{1} fib(2k-1)~=~fib(1)~=~1~=~fib(2\cdot 1)$

Induktionsannahme: Die Behauptung gilt für n: $\displaystyle \sum_{k=1}^{n} fib(2k-1)~=~fib(2n)$.

Induktionsrechnung: zu zeigen: Wenn die Behauptung für n gilt, dann auch für n+1.
$\displaystyle \sum_{k=1}^{n+1}fib(2k-1)=\sum_{k=1}^{n} fib(2k-1)+fib(2\cdot(n+1)-1)$$=fib(2n)+fib(2n+1)=fib(2n+2)=fib(2\cdot(n+1))$

Induktionsschluss: Die Behauptung gilt für alle n.

3. $~~\displaystyle \sum_{k=0}^{n}fib(2k)~=~fib(2n+1)~-~1~~~~~~~~~~~~$

Der Beweis erfolgt nun mit Vollständiger Induktion:

Behauptung: $\forall n\ge 0~gilt:~\displaystyle \sum_{k=0}^{n} fib(2k)~=~fib(2n+1)~-~1$.
Induktionsanfang: $\displaystyle \sum_{k=0}^{0} fib(2k)~=~fib(0)~=~0~=~fib(2\cdot 0+1)~-~1~(=~1-1)$

Induktionsannahme: Die Behauptung gilt für n: $\displaystyle \sum_{k=0}^{n} fib(2k)~=~fib(2n+1)~-~1$.

Induktionsrechnung: zu zeigen: Wenn die Behauptung für n gilt, dann auch für n+1.
$\displaystyle \sum_{k=0}^{n+1}fib(2k)=\sum_{k=0}^{n} fib(2k)+fib(2\cdot(n+1))$$=fib(2n+1)-1+fib(2n+2)=fib(2n+3)-1=fib(2\cdot(n+1)+1)-1$

Induktionsschluss: Die Behauptung gilt für alle n.

4. $~~\displaystyle \sum_{k=0}^{n}(fib(k))^2~=~fib(n)\cdot fib(n+1)~~~~~~~$

Der Beweis erfolgt nun mit Vollständiger Induktion:

Behauptung: $\forall n\ge 0~gilt:~\displaystyle \sum_{k=0}^{n} (fib(k))^2~=~fib(n) \cdot fib(n+1)$.
Induktionsanfang: $\displaystyle \sum_{k=0}^{0} (fib(k))^2~=~(fib(0))^2~=~0~=~fib(0)\cdot fib(1)~=~0\cdot 1$

Induktionsannahme: Die Behauptung gilt für n: $\displaystyle \sum_{k=0}^{n} (fib(k))^2~=~fib(n) \cdot fib(n+1)$.

Induktionsrechnung: zu zeigen: Wenn die Behauptung für n gilt, dann auch für n+1.
$\displaystyle \sum_{k=0}^{n+1}(fib(k))^2=\sum_{k=0}^{n} (fib(k))^2+(fib(n+1))^2$$=fib(n)\cdot fib(n+1)+fib(n+1)\cdot fib(n+1)$$=fib(n+1)\cdot (fib(n)+fib(n+1))~=~fib(n+1\cdot fib(n+2)~=~fib(n+1)\cdot fib((n+1)+1)$

Induktionsschluss: Die Behauptung gilt für alle n.

5. Je zwei benachbarte Fibonaccizahlen sind teilerfremd.

Beweis durch Widerspruch:

Angenommen, fib(n) und fib(n-1) besitzen den gemeinsamen Teiler t > 1: t/fib(n) sowie t/fib(n-1).

Wegen fib(n) = fib(n-1) + fib(n-2) und daraus fib(n-2) = fib(n) - fib(n-1) teilt t auch fib(n-2).
(Denn nach Voraussetzung teilt t sowohl fib(n) als auch fib(n-1).)

Wegen t teilt sowohl fib(n-1) als auch fib(n-2) teilt t auch fib(n-3).
Diese Argumentation lässt sich fortsetzen bis: t teilt fib(1).

Da fib(1) = 1 und nach Voraussetzung t > 1 kann t aber nicht fib(1) teilen. → Widerspruch!

Also ist die Annahme falsch und die ursprüngliche Behauptung richtig.

6. Die Summe der Diagonalglieder im Pascal-Dreieck ist eine Fibonaccizahl.

Die Zahlen im Pascal-Dreieck sind Binomialkoeffizienten: $\large \binom {n}{k}$. n entspricht der Zeile, k der Spalte.
Außerdem: $k~\le~n$ sowie $k,n~\ge~0$. Für k < 0 oder n < 0, setze $\large \binom{n}{k}=0$.
Jede Zahl im Pascal-Dreieck ist die Summe der beiden Zahlen darüber: $\large \binom {n}{k}~=~\binom{n-1}{k}~+~\binom{n-1}{k-1}~~~~(*)$.
Die n. Summe der Diagonalzahlen im Pascal-Dreieck ist: $\displaystyle s_n~=~\sum_{k=0}^{n} \binom{n-k}{k}$.

Der Beweis erfolgt nun mit Vollständiger Induktion:

Behauptung: $\forall n\ge 0~gilt:~\displaystyle s_n~=~\sum_{k=0}^{n} \binom{n-k}{k}~=~fib(n+1)$.
Induktionsanfang: $\displaystyle s_0~=~\sum_{k=0}^{0} \binom{0-k}{k}~=~\binom{0}{0}~=~1~=~fib(0+1)~=~fib(1)$
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\displaystyle s_1~=~\sum_{k=0}^{1} \binom{1-k}{k}~=~\binom{1}{0}+\binom{0}{1}~=~1+0~=~1~=~fib(1+1)~=~fib(2)$

Induktionsannahme: Die Behauptung gilt für n-1 und n:
$\displaystyle s_{n-1}=\sum_{k=0}^{n-1} \binom{n-1-k}{k}=fib(n)~~sowie~~s_n=\sum_{k=0}^{n} \binom{n-k}{k}=fib(n+1)$.

Induktionsrechnung: zu zeigen: Wenn die Behauptung für n-1 und n gilt, dann auch für n+1.
$\displaystyle s_{n+1}~=~\sum_{k=0}^{n+1}\binom{n+1-k}{k}~=~\sum_{k=0}^{n+1}\left(\binom{n-k}{k}~+~\binom{n-k}{k-1}\right)~~~~wegen~(*)$
$\displaystyle ~~~~~~~~~=~\sum_{k=0}^{n+1}\binom{n-k}{k}~+~\sum_{k=0}^{n+1}\binom{n-k}{k-1}$
$\displaystyle ~~~~~~~~~=~\sum_{k=0}^{n}\binom{n-k}{k}~+~\binom{n-(n+1)}{n+1}~+~$$\displaystyle \sum_{k=0}^{n}\binom{n-k)}{k-1}~+~\binom{n-(n+1)}{(n+1)-1}$
$\displaystyle ~~~~~~~~~=~s_n~+~0~+~\sum_{k=0}^{n}\binom{n-k)}{k-1}~+~0$
$\displaystyle ~~~~~~~~~=~s_n~+~\sum_{k=1}^{n}\binom{n-k}{k-1}$ , denn für k=0: $\large \binom{n}{-1}~ =~ 0$
$\displaystyle ~~~~~~~~~=~s_n~+~\sum_{k=0}^{n-1}\binom{n-(k+1)}{(k+1)-1}~=~s_n~+~\sum_{k=0}^{n-1}\binom{n-1-k}{k}$
$\displaystyle ~~~~~~~~~=~s_n~+~s_{n-1}$ = fib(n+1) + fib(n) = fib(n+2)

Induktionsschluss: Die Behauptung gilt für alle n.

1.3. Formel von Binet

Anstatt die Fibonaccizahlen rekursiv zu berechnen, können sie auch direkt mittels einer Formel bestimmt werden.
Diese Formel wurden unabhängig voneinander von 1718 und 1843 angegeben. Aber auch anderen Mathematikern war diese Formel bekannt, unter anderen oder , der 1728 auch einen Beweis lieferte.

Die n. Fibonaccizahl entspricht

$\large fib(n)~=~$$\Large \frac{1}{\sqrt{5}}~\left(\left(\frac{1+\sqrt{5}}{2}\right)^n~-~\left(\frac{1-\sqrt{5}}{2}\right)^n \right)~=~\frac{1}{\sqrt{5}}~(\Phi^n~-~\Psi^n)$

falls $\large \Phi=\frac{1+\sqrt{5}}{2}$ und $\large \Psi=\frac{1-\sqrt{5}}{2}=1-\Phi=-\Psi^{-1}$.

Es ist erstaunlich, dass für ganzzahlige n immer ganzzahlige Werte herauskommen!

$\Phi$ und $\Psi$ sind Lösungen der sogenannten charakteristischen Gleichung $x^2-x-1=0$.

Die charakteristische Gleichung ist ein Hilfsmittel, um Lösungen von linearen Differenzengleichungen zu ermitteln. Lineare Differenzengleichungen wiederum sind einfache Beziehungen zwischen Gliedern einer Folge.
Wenn eine Folge (f_i) gegeben ist, heißt jede Gleichung der Form $f_n=a_1f_{n-1}+a_2f_{n-2}~mit ~n>1$ homogene lineare Differenzengleichung zweiter Ordnung.
Im Fall der Fibonacci-Folge gilt: $a_1=a_2=1~sowie~f_0=0~und~f_1=1$.
Um nun statt einer rekursiven Definition einen direkten Ausdruck zu erhalten, wählt man den Lösungsansatz:
$f_n~=~x^n$ , denn Differenzenfolgen wachsen oft exponentiell.

Angewendet auf die Fibonacci-Folge erhält man:
$fib(n)~=~fib(n-1)~+~fib(n-2)~~\rightarrow~~x^n~=x^{n-1}~+~x^{n-2}~~\rightarrow~~(x^2~-~x~-~1)~x^{n-2}~=~0$.
Dann ist $x^2-x-1=0$ die charakteristische Gleichung mit den Lösungen
$\large \Phi=\frac{1+\sqrt{5}}{2}$ und $\large \Psi=\frac{1-\sqrt{5}}{2}$.

Der Lösungsraum ist dann $fib(n)=\lambda_1\Phi^n+\lambda_2\Psi^n~~~~(*)$.
Die Parameter $\lambda_i$ ergeben sich aus den Anfangsbedingungen. Im Falle der Fibonaccifolge sind das $fib(0)=0~sowie~fib(1)=1$. Deshalb:

$I.~~~fib(0)=\lambda_1\Phi^0+\lambda_2\Psi^0=\lambda_1+\lambda_2=0~~\rightarrow~~\lambda_2=-\lambda_1~~$ sowie
$II.~~fib(1)=\lambda_1\Phi^1+\lambda_2\Psi^1=\lambda_1\frac{1+\sqrt{5}}{2}+\lambda_2\frac{1-\sqrt{5}}{2}=1$

I. in II. eingesetzt: $\lambda_1=\frac{1}{\sqrt{5}}~~\rightarrow~~\lambda_2=-\frac{1}{\sqrt{5}}$

In (*) eingesetzt: $fib(n)=\lambda_1\Phi^n+\lambda_2\Psi^n=$$\large \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$

Alternativ: Beweis durch vollständige Induktion

Induktionsanfang:
Die Formel ist erfüllt für $fib(0) =$ $\large \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^0-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^0=0$
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~fib(1) =$ $\large \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^1-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^1=1$.

Induktionsrechnung:
$\Phi$ und $\Psi$ wie oben definiert.

$fib(n-1)+fib(n)= \frac{1}{\sqrt{5}}(\Phi^{n-1}-\Psi^{n-1}+\Phi^n-\Psi^n)=\frac{1}{\sqrt{5}}\left(\Phi^{n-1}(1+\Phi)-\Psi^{n-1}(1+\Psi)\right)~~~(**)$

Zur Erinnerung: $\Phi$ und $\Psi$ sind Lösungen der charakteristischen Gleichung $x^2-x-1=0~~\rightarrow x^2=x+1$.
Deshalb: $\Phi^2=\Phi+1$ sowie $\Psi^2=\Psi+1$.

Eingesetzt in (**):
$fib(n-1)+fib(n)= \frac{1}{\sqrt{5}}\left(\Phi^{n-1}~\Phi^2-\Psi^{n-1}~\Psi^2\right)=\frac{1}{\sqrt{5}}\left(\Phi^{n+1}-\Psi^{n+1}\right)=fib(n+1)$

Anmerkung:
Es reicht für die Binet-Formel, den ersten Summanden zu berechnen und zu runden, denn der zweite Summand wird schnell kleiner.

$\large fib(n)~=~$$\Large \left[\frac{1}{\sqrt{5}}~\left(\frac{1+\sqrt{5}}{2}\right)^n~+~0,5\right]$

Außerdem kann die Fibonaccifolge auch nur mit dem Vorgänger rekursiv definiert werden:
$\large fib(n)~=~ \left[ \frac{1}{2}\left(fib(n-1)+1+\sqrt{5(fib(n-1))^2}\right)\right]$

Die eckigen Klammern sind jeweils Gauß-Klammern - also den Wert abrunden!

1.4. Erweiterungen

negative Argumente

Die Fibonaccizahlen können auf negative ganzzahlige Argumente erweitert werden!
Um das einzusehen, formt man die ursprüngliche rekursive Definition um:

fib(n+1) = fib(n) + fib(n-1) → fib(n-1) = fib(n+1) - fib(n)

Anstatt eines Nachfolgers bestimmt man nun einen Vorgänger!

Nachfolgend einige Werte.

n	-5	-4	-3	-2	-1	0	1	2	3	4	5
fib(n)	5	-3	2	-1	1	0	1	1	2	3	5

Betragsmäßig ändern sich die Fibonaccizahlen nicht, aber bei geraden Argumenten werden die Werte negativ!

reelle Argumente

Natürlich können reelle Argumente nicht in die rekursive Definition eingesetzt werden.

Aber man kann reelle Argumente in die Formel von Binet einsetzen! Im Ergebnis erhält man im Allgemeinen komplexe Funktionswerte für die Fibonaccizahlen.

Zeichnet man diese in die komplexe Zahlenebene ein, erhält man sogenannte Argand-Diagramme.

Nachfolgend sind die Fibonaccizahlen für 0 ≤ n ≤ 6 abgebildet.

Die Kurve windet sich um die reelle Achse. Die Schnittpunkte mit der reellen Achse (bei x=1 zweimal) sind die 'normalen' Fibonaccizahlen.

Im zweiten Bild sind die Argumente negativ. Wiederum sind die Schnittpunkte mit der x-Achse die 'normalen ganzzahligen' Fibonaccizahlen. Aber wegen des ständigen Vorzeichenwechsels windet sich die Kurve nun spiralförmig um den Ursprung.

1.5. Implementierung

Für die Implementierung einer Funktion zur Berechnung der Fibonaccizahlen eignet sich die rekursive Definition nur bedingt (hier in JavaScript):
function fibonacci_rekursiv(n) {
$~~~~~~$if (n<2) { return n; }
$~~~~~~~~~$ else { return fibonacci_rekursiv(n-1)+fibonacci_rekursiv(n-2); }
}

Die Implementierung ist elegant, aber die Rechenzeit für die rekursive Version ist viel zu hoch.
Die ständigen Funktionsaufrufe sind extrem zeitaufwendig.

Besser ist eine iterative Variante;

Da ganzzahlige Variablen nur einen eingeschränkten Zahlenbereich abdecken, erfolgt die Implementierung mit BigInteger- Variablen (deshalb das n am Ende der Zahlen). Es können im Prinzip beliebig große Fibonaccizahlen genau berechnet werden.

Die Implementierung kann selbstvertändlich auch über die (ggfs modifizierte) Binet-Formel erfolgen. Aber auch hier gilt (wegen reeller Variablen): der Zahlenbereich ist nur eingeschränkt und führt bei größeren Werten ggfs zu Rundungsfehlern.

2. Goldener Schnitt

2.1. Definition

Wird eine Strecke AB durch den Punkt C so geteilt, dass das Verhältnis der gesamten Strecke zur größeren Teilstrecke gleich dem Verhältnis der gößeren zur kleineren Teilstrecke ist, nennt man dieses Teilungsverhältnis $\phi$ den Goldenen Schnitt.

$\large \phi~=~\frac{a+b}{a}~=~\frac{a}{b}~=~\frac{1+\sqrt{5}}{2}~=~1,618...$

Sei ohne Beschränkung der Allgemeinheit a die längere Teilstrecke und die Gesamtstrecke a + b = 1.
Dann lässt sich die Verhältnisgleichung umformen zu

$\large \frac{a+b}{a}~=~\frac{a}{b}~~\rightarrow~~\frac{1}{a}~=~\frac{a}{1-a}~~\rightarrow~~a^2+a-1~=~0$

Mit Hilfe der p-q-Formel folgt daraus:

$a_{1,2}~=~-\frac{1}{2}~\pm~\sqrt{\frac{1}{4}+1}~=~-\frac{1}{2}~\pm~\frac{1}{2}\sqrt{5}$

Es kommen für die Strecke a nur positive Werte infrage, also:

$a~=~-\frac{1}{2}~+~\frac{1}{2}\sqrt{5}~=~\frac{1}{2}~(\sqrt{5}-1)~=~0,618...$

Für die kürzere Strecke b gilt:

$b~=~1~-~a~=~1~-(\frac{1}{2}~(\sqrt{5}-1))~\approx~0,382$

Für das Verhältnis $\phi$ der Gesamtstrecke zur größeren Strecke gilt mithin:

$\large \phi~=~\frac{1}{a}~=~\frac{2}{\sqrt{5}-1}$$~=~\frac{2}{\sqrt{5}-1}\frac{\sqrt{5}+1}{\sqrt{5}+1}~=~\frac{1}{2}(\sqrt{5}+1)~=~1,618...$

$ \phi$ ist irrational, aber algebraisch, denn diese Zahl lässt sich durch einen Wurzel-Ausdruck darstellen.

2.2. Potenzen

Wie bereits im Kapitel 'Formel von Binet' angegeben, ist der Goldene Schnitt $\Phi$ die positive Lösung der Gleichung $x^2~-~x~-~1~=~0$.

Deshalb gilt: $\Phi^2~-~\Phi~-~1~=~0~~\rightarrow~~\Phi^2~=~\Phi~+~1$.

Wie sieht es für höhere Potenzen aus?
$\Phi^3~=~\Phi^2\cdot\Phi~=~(\Phi+1)\cdot\Phi~=~\Phi^2+\Phi~=~(\Phi+1)+\Phi~=~2\Phi+1$
$\Phi^4~=~\Phi^2\cdot\Phi^2~=~(\Phi+1)\cdot(\Phi+1)~=~\Phi^2+2\Phi+1~=~(\Phi+1)+2\Phi+1~=~3\Phi+2$
$\Phi^5~=~\Phi^3\cdot\Phi^2~=~(2\Phi+1)\cdot(\Phi+1)~=~2\Phi^2+3\Phi+1~=~2\cdot (\Phi+1)+3\Phi+1~=~5\Phi+3$
$\Phi^6~=~\Phi^3\cdot\Phi^3~=~(2\Phi+1)\cdot(2\Phi+1)~=~4\Phi^2+4\Phi+1~=~4\cdot (\Phi+1)+4\Phi+1~=~8\Phi+5$

Allgemein gilt: $\Phi^n~=~\Phi^{n-1}~+~\Phi^{n-2}~=~fib(n)\cdot \Phi~+~fib(n-1)$

Der Beweis erfolgt nun mit Vollständiger Induktion:

Behauptung 1: $\forall n\ge 2~gilt:~\Phi^n~=~\Phi^{n-1}~+~\Phi^{n-2}$.
Induktionsanfang: $\Phi^2~=~\Phi^{2-1}~+~\Phi^{2-2}~=~\Phi+1$

Induktionsannahme: Die Behauptung gilt für n: $\Phi^n~=~\Phi^{n-1}~+~\Phi^{n-2}$.

Induktionsrechnung: zu zeigen: Wenn die Behauptung für n gilt, dann auch für n+1.
$\Phi^{n+1}~=~\Phi^n\cdot\Phi~=~(\Phi^{n-1}~+~\Phi^{n-2})\cdot\Phi~=~\Phi^n~+~\Phi^{n-1}~=~\Phi^{(n+1)-1}~+~\Phi^{(n+1)-2}$

Induktionsschluss: Die Behauptung gilt für alle n.

Behauptung 2: $\forall n\ge 2~gilt:~\Phi^n~=~fib(n)\cdot\Phi~+~fib(n-1)$.
Induktionsanfang: $\Phi^2~=~fib(2)\cdot\Phi~+~fib(2-1)~=~1\cdot\Phi+1$

Induktionsannahme: Die Behauptung gilt für n: $\Phi^n~=~fib(n)\cdot\Phi~+~fib(n-1)$.

Induktionsrechnung: zu zeigen: Wenn die Behauptung für n gilt, dann auch für n+1.
$\Phi^{n+1}~=~\Phi^n\cdot\Phi~=~(fib(n)\cdot\Phi~+~fib(n-1))\cdot\Phi$$~=~fib(n)\cdot\Phi^2~+~fib(n-1)\cdot\Phi~=~fib(n)\cdot(\Phi+1)~+~fib(n-1)\cdot\Phi$$~=~(fib(n)+fib(n-1))\cdot\Phi~+~fib(n)~=~fib(n+1)\cdot\Phi~+~fib((n+1)-1)$

Induktionsschluss: Die Behauptung gilt für alle n.

Hinweis: Die Beziehung gilt nicht nur für natürliche Potenzen und Fibonaccizahlen, sondern sogar für ganzzahlige Potenzen und Fibonaccizahlen!

2.3. Konstruktionen

Vorgestellt werden zwei geometrische Konstruktionen, um eine Strecke AB nach dem Goldenen Schnitt durch den Punkt S zu teilen.

Klassisches Verfahren mit innerer Teilung

1. Errichte zur Strecke AB in B ein Lot der halben Länge von AB mit dem Endpunkt C.

2. Der Kreis um C mit dem Radius CB schneidet die Strecke AC in D.

3. Der Kreis um A mit dem Radius AD schneidet die Strecke AB in S.

Begründung:
Ohne Beschränkung der Allgemeinheit sei die die Länge der Strecke AB: |AB| = 1.
Nach Pythagoras ist dann |AC| = $\frac{1}{2}\sqrt{5}$. Von dieser Länge wird die Länge $\frac{1}{2}$ (= |CD|) abgetragen.
Demnach ist |AD| =|AS| = $\frac{1}{2}\sqrt{5}-\frac{1}{2}$.

Klassisches Verfahren mit äußerer Teilung

1. Errichte zur Strecke AS in S ein Lot der Länge von AS mit dem Endpunkt C.

2. Konstruiere den Mittelpunkt M der Strecke AS.

3. Der Kreis um M mit dem Radius MC schneidet die Verlängerung der Strecke AS in B.

Begründung:
Ohne Beschränkung der Allgemeinheit sei die die Länge der Strecke AS: |AS| = 1.
Nach Pythagoras ist dann |MC| = $\frac{1}{2}\sqrt{5}$ = |MB|. Die Strecke AM besitzt die Länge |AM| = $\frac{1}{2}$. Demnach ist |AB| =|AM| + |MB| = $\frac{1}{2}+\frac{1}{2}\sqrt{5}$.

2.4. Anwendungen

In der Architektur und in der Kunst ist die der Goldene Schnitt ein häufig wiederkehrendes Gestaltungsmerkmal.

Beispiele: Eifel-Turm in Paris sowie Altes Rathaus Leipzig
$~~~~~~~~~~~~~~~~~~~~~~$

$~~~~~~~~~~~~~~~~~~~~~~$

Bildkompostion von Eugene Delacrix Die Freiheit für das Volk (1830)

Bildformate pendeln häufig um den Goldenen Schnitt, weil man diese Art der Einteilung häufig als ästhetisch empfindet:

4 : 3 ≈ 1,33 $\sqrt{2}$ : 1,41 ≈ 1 3 : 2 = 1,5
5 : 3 ≈ 1,67 16 : 9 ≈ 1,77

$~~~~~~~~~~~~~~~~~~~~~~$

Bei einem sogenannten goldenen Rechteck entspricht dem Verhältnis der Seitem dem Goldenen Schnitt.
Teilt man den kleineren Teil des Rechtecks erneut nach dem Goldenen Schnitt und führt dieses fort, gelangt man zur goldenen Spirale, indem man in den größeren Teil jeweils Viertelkreise zeichnet.

3. Zusammenhang

Schon erkannte, dass der Quotient aufeinanderfolgender Fibonaccizahlen dem Goldenen Schnitt beliebig nahe kommt.

In heutiger Schreibweise:
$$\large \lim_{n\to\infty}\frac{fib(n+1)}{fib(n)}~=~\Phi~=~\frac{1+\sqrt{5}}{2}~\approx~1,618$$
Für einen Beweis kann die Formel für Binet herangezogen werden.
Es gilt: $ \displaystyle \lim_{n\to\infty}\Psi^n~=~ \lim_{n\to\infty}(\frac{1-\sqrt{5}}{2})^n~=~0$, denn |$\Psi$| ≈ 0,618 < 1.

Dann gilt: $\displaystyle \lim_{n\to\infty}\frac{fib(n+1)}{fib(n)}~=~\lim_{n\to\infty}\frac{\Phi^{n+1}-\Psi^{n+1}}{\Phi^n-\Psi^n}~=~\frac{\Phi^{n+1}}{\Phi^n}~=~\Phi$