\documentclass{article}

\newcounter{blatt}
\newcounter{aufgabe}
\setcounter{blatt}{9}
\setcounter{aufgabe}{5}

\include{AnaHdrMusterLoes}
\begin{document}
\fontsize{11}{15}
\selectfont

\begin{center}
{\LARGE Musterlösung zu Blatt \theblatt, Aufgabe \theaufgabe}
\end{center}

\section{Aufgabenstellung}
Es sei $(a_n)_{n \in \mathbb{N}}$ die Folge der Fibonaccizahlen (vgl. Aufgabe 3b, Blatt 4).
\\ \\  
a) Zeigen Sie, dass die Potenzreihe $f(z):=\sum^{\infty}_{n=0} a_nz^n$ mindestens den Konvergenzradius $\rho=\frac{1}{2}$ hat.\\ \\
b) Zeigen Sie, dass für alle $z \in \mathbb{C}$ mit $\left|z\right|<\frac{1}{2}$ gilt
\[f(z)=\frac{1}{1-z-z^2}\] \\
c) Folgern Sie aus Teil b), dass
\begin{center}
$a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$  für alle $n \in \mathbb{N}$
\end{center}


\section{Beweisidee}
\paragraph{"`Worum geht's?"':}
Gegeben ist eine Folge, die Fibonaccifolge $(a_n)_{n \in \mathbb{N}}$, deren Definition weiter unten noch einmal angegeben ist. In Teilaufgabe a) soll eine Verbindung zwischen dieser Folge und der dazugehörigen Potenzreihe $f(z):=\sum^{\infty}_{n=0} a_nz^n$ hergestellt werden und dadurch die Konvergenz der Reihe für $\rho=\frac{1}{2}$ bewiesen werden.
In Teil b) wird der Grenzwert der konvergenten Reihe bestimmt und daraus soll in Teil c) die explizite Darstellung der Fibonaccizahlen nach Binet gefolgert werden.
\paragraph{"`Wie mach' ich das?"':}
In Teilaufgabe a) ist es sinnvoll die Reihe auf ein bekanntes Konvergenzkriterium zurückzuführen, in diesem Fall das Quotientenkriterium. Hier gelingt dies auch, was nicht notwendigerweise der Fall ist, da das Quotientenkriterium zwar hinreichend, aber nicht notwendig ist.\\
b) Durch Umformung wird versucht die Gleichheit zu zeigen. Günstig ist es dabei, durch Zurückführung auf die Definition der Fibonaccizahlen eine größtmögliche Vereinfachung zu erreichen. Dazu bedarf es etwas Übung im Umgang mit dem Summenzeichen, um das Herausziehen von einzelnen Summanden nachvollziehen zu können.
In Teilaufgabe c) schließlich wird die Kenntnis über die am Ende resultierende Darstellung genutzt und mit $q_1=\frac{1+\sqrt{5}}{2}$ und $q_2=\frac{1-\sqrt{5}}{2}$ der Zusammenhang hergestellt. Wegen der Form von $f(z)=\frac{1}{1-z-z^2}$ lässt sich vermuten, dass man den Nenner in zwei Faktoren und schließlich den Bruch in zwei Summanden trennen kann, so dass jeder der Summanden Grenzwert einer geometrischen Reihe ist. Damit kann die Aufgabe dann gelöst werden.


\section{Lösung}

a) Die Fibonaccizahlen wurden auf Blatt 4, wie folgt rekursiv definiert:\\
\begin{center}
$a_0=a_1=:1$ und $a_{n+2}=a_{n+1}+a_{n}$

\end{center}
Durch vollständige Induktion zeige man zunächst, dass die Folge der Fibonaccizahlen monoton steigend ist, es also gilt 
\begin{center}
$a_0>0$ und $a_{n+1} \geq a_n$, woraus dann $a_n>0$ folgt.
\end{center}
Das $a_0=1>0$ ergibt sich aus der Definition, außerdem ergibt sich aus der Defintion auch schon der Induktionsanfang, da
\begin{center}
$a_0=a_1=:1 \Rightarrow a_1 \geq a_0$
\end{center}
Als Induktionsvoraussetzung soll die Aussage für alle $a_k$ mit $k \in \mathbb{N}$ und $k \leq n$ zutreffen
\begin{center}
$a_k \geq a_{k-1}$
\end{center}
Aus der Definition ergibt sich dann der Induktionsschritt zu
\begin{center}
$a_{n+1}=a_n+a_{n-1} \geq 2a_{n-1}>a_n$, da nach Induktionsvoraussetzung $a_{n-1} \geq a_{n-2} \Rightarrow a_n =a_{n-1}+a_{n-2} \leq 2a_{n-1} $
\end{center}
Die Fibonaccizahlen sind somit monoton steigend. \\ \\
Für $z \in \mathbb{C}$, $\left|z\right|<\frac{1}{2}$ lässt sich durch Multiplikation mit der reelen Zahl 2 abschätzen nach $2\left|z\right|<1$. 
Unter Verwendung dieser beiden Abschätzungen lässt sich nun eine neue Ungleichung aufstellen
\begin{center}
$\frac{\left|a_{n+1}z^{n+1}\right|}{\left|a_nz^n\right|}=\frac{\left|a_{n+1}\right|\left|z^{n+1}\right|}{\left|a_n\right|\left|z^n\right|}=\frac{a_{n+1}}{a_n}\frac{\overbrace{\left|z\right| \cdots \left|z\right|}^{n+1}}{\underbrace{\left|z\right| \cdots \left|z\right|}_{n}}=\frac{a_n+a_{n-1}}{a_n}\left|z\right|=\left(1+\frac{a_{n-1}}{a_n}\right)\left|z\right| \leq 2\left|z\right|<1$ \end{center}
Dabei wurde  $\left|a_{n+1}\right|=a_{n+1}$ und $\left|a_n\right|=a_n$ gesetzt, da $a_n,a_{n+1} \in \mathbb{R^{+}}$. \\
Die so gefundene Ungleichung erfüllt aber gerade das Quotientenkriterium und damit konvergiert die Reihe $\sum^{\infty}_{n=0}a_nz^n$ für alle $z \in \mathbb {C}$ mit $\left|z\right|<\frac{1}{2}$. Der Konvergenzradius ist also mindestens $\rho=\frac{1}{2}$\\ \\
b) Durch Umformung erhält man
\begin{center}
$f(z)=\frac{1}{1-z-z^2}\Rightarrow (1-z-z^2)f(z)=1$
\end{center}
Man setze nun für $f(z)=\sum^{\infty}_{n=0}a_nz^n$ ein 
\begin{center}
$(1-z-z^2)f(z)=\sum^{\infty}_{n=0}a_nz^n-z\sum^{\infty}_{n=0}a_nz^n-z^2\sum^{\infty}_{n=0}a_nz^n=$\\$ =\sum^{\infty}_{n=0}a_nz^n-\sum^{\infty}_{n=1}a_{n-1}z^n-\sum^{\infty}_{n=2}a_{n-2}z^{n}=$ \\
$=a_0+a_1z+\sum^{\infty}_{n=2}a_nz^n-(a_0z+\sum^{\infty}_{n=2}a_{n-1}z^n)-\sum^{\infty}_{n=2}a_{n-2}z^{n}=$\\
$a_0+a_1z-a_0z+\sum^{\infty}_{n=2}\underbrace{(a_n-a_{n-1}-a_{n-2})}_{=0}z^{n}=$
\end{center}
Die Summe fällt nach der Definition $a_n=a_{n-1}+a_{n-2}$ weg und durch einsetzen der Werte ergibt sich die geforderte Beziehung
\begin{center}
$=a_0+a_1z-a_0z+\sum^{\infty}_{n=2}\underbrace{(a_n-a_{n-1}-a_{n-2})}_{=0}z^{n}=$\\
$=1+1-1=1$
\end{center} 
c) Man setzte
\begin{center}
$q_1=\frac{1+\sqrt{5}}{2}$~~~~~~und~~~~~~$q_2=\frac{1-\sqrt{5}}{2}$
\end{center}
Mit Hilfe von $q_1$ und $q_2$ lässt sich $f(z)$ umschreiben:
\begin{center}
$f(z)=\frac{1}{\sqrt{5}}\left(\frac{q_1}{1-q_1z}-\frac{q_2}{1-q_2z}\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\frac{(q_1)(1-q_2z)-(q_2)(1-q_1z)}{(1-q_1z)(1-q_2z)}\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\frac{\left(\frac{1+\sqrt{5}}{2}\right)\left(1-\frac{1-\sqrt{5}}{2}z\right)-\left(\frac{1-\sqrt{5}}{2}\right)\left(1-\frac{1+\sqrt{5}}{2}z\right)}{\left(1-\frac{1+\sqrt{5}}{2}z\right)\left(1-\frac{1-\sqrt{5}}{2}z\right)}\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\frac{\left(\frac{1+\sqrt{5}-1+\sqrt{5}}{2}\right)-\frac{1-\sqrt{5}^2}{4}z+\frac{1-\sqrt{5}^2}{4}z}{
1+\frac{-1-\sqrt{5}-1+\sqrt{5}}{2}z+\frac{1-\sqrt{5}^2}{4}z^2}\right)=$\\
$=\frac{1}{1-z-z^2}$
\end{center}
Da für $\left|z\right|<\frac{1}{2} \Rightarrow \left|q_1z\right|=\left|q_1\right|\left|z\right|<1,62\left|z\right|<1$ und $\left|q_2z\right|=\left|q_2\right|\left|z\right|<0,62\left|z\right|<1$ gilt, kann man nun mit dem Grenzwert der geometrischen Reihe argumentieren. Es ist dann 
\begin{center}
$q_1\sum^{\infty}_{n=0}(q_1z)^n=q_1\left(\frac{1}{1-q_1z}\right)=\frac{q_1}{1-q_1z}$~~~und~~~$q_2\sum^{\infty}_{n=0}(q_2z)^n=q_2\left(\frac{1}{1-q_2z}\right)=\frac{q_2}{1-q_2z}$
\end{center}
Fasst man die beiden Ergebnisse zusammen, so folgt
\begin{center}
$f(z)=\frac{1}{1-z-z^2}=\frac{1}{\sqrt{5}}\left(\frac{q_1}{1-q_1z}-\frac{q_2}{1-q_2z}\right)=\frac{1}{\sqrt{5}}\left(q_1\sum^{\infty}_{n=0}(q_1z)^n-q_2\sum^{\infty}_{n=0}(q_2z)^n\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\sum^{\infty}_{n=0}q^{n+1}_1z^n-\sum^{\infty}_{n=0}q^{n+1}_2z^n\right)=$\\
$=\frac{1}{\sqrt{5}}\sum^{\infty}_{n=0}\left(q^{n+1}_1-q^{n+1}_2\right)z^n$
\end{center}
Der Identitätssatz für Potenzreihen liefert
\begin{center}
$a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$  für alle $n \in \mathbb{N}$
\end{center}


\section{Variationen, Verallgemeinerungen, Abschwächungen}
\paragraph{Varianten des Beweises mit verschiedenen Methoden:} \par \flushleft
Alternativ lässt sich diese explizite Darstellung der Fibonaccizahlen auch mit Induktion beweisen.\par \flushleft
\underline{Induktionsanfang $n=0$}
\begin{center}
$a_0=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{0+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{0+1}\right)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}-1+\sqrt{5}}{2}\right)=1$  
\end{center} 
\par \flushleft
\underline{Induktionsvoraussetzung}
\begin{center}
$a_k=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}\right)$  
\end{center}
sei für alle $k \in \mathbb{N}$, $k \leq n$ erfüllt.
\par \flushleft
\underline{Induktionsschritt:}\par \flushleft
Nach der rekursiven Defintion der Fibonaccizahlen erhält man
\begin{center}
$a_{n+1}=a_n+a_{n-1}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)+\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}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\left(\frac{1+\sqrt{5}}{2}+1\right)-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\left(\frac{1-\sqrt{5}}{2}+1\right)\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\left(\frac{3+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\left(\frac{3-\sqrt{5}}{2}\right)\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\left(\frac{1+2\sqrt{5}+5}{4}\right)-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\left(\frac{1-2\sqrt{5}+5}{4}\right)\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\left(\frac{1-\sqrt{5}}{2}\right)^2\right)=$\\
$=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right)$
\end{center}
Eine weitere Möglichkeit liefert die Lineare Algebra (Lineare Algebra II). Der Vorteil dieser Methode ist, dass die Kenntnis der expliziten Darstellung nicht notwendig ist, man also mit den Mitteln der Linearen Algebra direkt auf die Formel kommt. \\
Aus der Defintion der Fibonaccizahlen $a_{n+2}=a_{n+1}+a_{n}$ lässt sich eine Matrix $A=\left( \begin{array}{ccc} 1 & 1 \\ 1 & 0  \\ \end{array} \right) $ aufstellen
\begin{center}
$\left( \begin{array}{ccc} a_{n+1} \\ a_n  \\ \end{array} \right) =
\left( \begin{array}{ccc} 1 & 1 \\ 1 & 0  \\ \end{array} \right) 
\left( \begin{array}{ccc} a_n \\ a_{n-1}   \\ \end{array} \right) =
A 
\left( \begin{array}{ccc} a_n \\ a_{n-1}   \\ \end{array} \right)
$
\end{center}

Damit lässt sich jedes $a_n$ darstellen als

\begin{center}
$\left( \begin{array}{ccc} a_{n+1} \\ a_n  \\ \end{array} \right) =
A^n 
\left( \begin{array}{ccc} a_1 \\ a_0   \\ \end{array} \right) 
$
\end{center}

Man betrachte im Folgenden einen Endomorphismus $\phi$, mit Darstellungsmatrix $A$. Diese bildet einen Vektor $\left( \begin{array}{ccc} v_1 & v_2  \\ \end{array} \right)$ auf einen Vektor $\left( \begin{array}{ccc} v_1+v_2 & v_1  \\ \end{array} \right)$ ab. Gesucht ist nun eine Basis $\left<u_1,u_2 \right>$, sodass die darstellende Matrix von $\phi$ bzgl. dieser Matrix eine Diagonalmatrix ist. Dazu müssen zunächst die Eigenwerte von $A$ bestimmt werden. Dies lässt sich nach 
\begin{center}
$\det(A-\lambda E)=\det\left(A-\left( \begin{array}{ccc} \lambda&0 \\ 0 &\lambda  \\ \end{array} \right)\right) =\det{\left( \begin{array}{ccc} 1-\lambda&1 \\ 1 &\lambda  \\ \end{array} \right)}=\left(1+\lambda\right)\lambda-1\cdot 1=\lambda^2-\lambda-1=0$\\
$\Rightarrow \lambda_1=q_1=\frac{1+\sqrt{5}}{2} \wedge \lambda_2=q_2=\frac{1-\sqrt{5}}{2}$
\end{center}
Damit erhält man die gesuchte Diagonalmatrix zu 
\begin{center}
$D=\left( \begin{array}{ccc} \lambda_1&0 \\ 0&\lambda_2  \\ \end{array} \right)=\left( \begin{array}{ccc} \frac{1+\sqrt{5}}{2}&0 \\ 0&\frac{1-\sqrt{5}}{2}  \\ \end{array} \right) $
\end{center}
Die Eigenvektoren $u_1$ und $u_2$ sind
\begin{center}
$Au_1=\lambda_1u_1\Rightarrow \left( \begin{array}{ccc} u_{11}+u_{12} \\ u_{11}  \\ \end{array} \right)=\left( \begin{array}{ccc} \frac{1+\sqrt{5}}{2} u_{11} \\ \frac{1+\sqrt{5}}{2}u_{12}  \\ \end{array} \right)$
$Au_2=\lambda_2u_2\Rightarrow \left( \begin{array}{ccc} u_{21}+u_{22} \\ u_{21}  \\ \end{array} \right)=\left( \begin{array}{ccc} \frac{1-\sqrt{5}}{2} u_{21} \\ \frac{1-\sqrt{5}}{2}u_{22}  \\ \end{array} \right)$
\end{center}
Die Lösung der Gleichungssysteme ist dann 
\begin{center}
$u_1=\left( \begin{array}{ccc} 2 \\ -1+\sqrt{5}  \\ \end{array} \right)$~~~und~~~$u_2=\left( \begin{array}{ccc} 2 \\ -1-\sqrt{5}  \\ \end{array} \right)$ 
\end{center}
Wir können nun eine invertierbare Matrix $S=\left( \begin{array}{ccc} 2&2 \\ -1+\sqrt{5}& -1-\sqrt{5} \\ \end{array} \right)$ aufstellen, die als Spalten die Basisvektoren $u_1,u_2$ besitzt. Die inverse Matrix ist dann mit $\det{S}=2 \left(-1-\sqrt{5}\right)-2\left(-1+\sqrt{5}\right)=-4\sqrt{5}$
\begin{center}
$S^{-1}=\frac{S^{Ad}}{det{S}}=\frac{\left( \begin{array}{ccc} -1-\sqrt{5}&-2 \\1-\sqrt{5} &2   \\ \end{array} \right) }{-4\sqrt{5}}
=\left(\begin{array}{ccc} \frac{1+\sqrt{5}}{4\sqrt{5}}&\frac{1}{2\sqrt{5}} \\ \frac{-1+\sqrt{5}}{4\sqrt{5}} &\frac{-1}{2\sqrt{5} }  \\ \end{array} \right)$
\end{center}
Schließlich bekommt man $A^n=SDS^{-1}$, woraus man dann die bekannte Formel ablesen kann.
\begin{center}
$A^n=\left( \begin{array}{ccc} 2&2 \\ -1+\sqrt{5}& -1-\sqrt{5} \\ \end{array} \right)\left( \begin{array}{ccc} \frac{1+\sqrt{5}}{2}&0 \\ 0&\frac{1-\sqrt{5}}{2}  \\ \end{array} \right)\left(\begin{array}{ccc} \frac{1+\sqrt{5}}{4\sqrt{5}}&\frac{1}{2\sqrt{5}} \\ \frac{-1+\sqrt{5}}{4\sqrt{5}} &\frac{-1}{2\sqrt{5} }  \\ \end{array} \right)=\left( \begin{array}{ccc} \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}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right) \\ \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-1}\right)&\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n-2}-\left(\frac{1-\sqrt{5}}{2}\right)^{n-2}\right)  \\ \end{array} \right)$
$\Rightarrow a_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$
\end{center}

Weitere interessante Eigenschaften der Fibonaccizahlen finden Sie unter
\begin{center}
Blatt 4, Aufgabe 3\\
Blatt 6, Aufgabe 1a\\
Blatt 7, Aufgabe 6\\
\end{center}
und natürlich im Internet oder in der Fachliteratur.
\section{Nutzen \& Anwendungen}
Die Formel von Binet hat wie jede explizite Darstellung den Vorteil, dass ein beliebiges Folgeglied der Fibonaccifolge direkt brechnet werden kann. Die Fibonaccifolge selbst findet sich erstaunlich oft in der Natur wieder. Um nur einige Beispiele zu nennen die Anordnung von Samen einer Sonnenblume, oder die Ahnenmenge der Honigbienen. Der goldene Schnitt $\left|q_2\right|=0,618$ findet z.B. in der Kunst und Architektur eine Anwendung. \\
Auch in der Mathematik stößt man immer wieder auf die Fibonaccizahlen, so z.B. im Pascalschen Dreieck, aber auch wie oben gezeigt in der Linearen Algebra, Analysis oder Zahlentheorie.
 

\begin{flushright}
{\footnotesize Pascal Reisert, \today}
\end{flushright}
\end{document}