Berechnen Sie die ersten 8 Fibonacci-Zahlen.

Question

Aufgabe:

Wir definieren rekursiv eine Folge \( \left(f_{n}\right)_{n \in \mathbb{N}} \) natürlicher Zahlen durch
$$ f_{1}:=1, \quad f_{2}:=1, \quad f_{n+2}:=f_{n}+f_{n+1} \forall n \in \mathbb{N} $$
Die so konstruierten Zahlen \( f_{n} \) heisen Fibonacci-Zahlen.
(a) Berechnen Sie die ersten 8 Fibonacci-Zahlen.
(b) Für jedes \( n \in \mathbb{N} \) setzen wir \( x_{n}:=\left(\begin{array}{c}f_{n} \\ f_{n+1}\end{array}\right) \in \mathbb{R}^{2} . \) Finden Sie eine \( 2 \times 2 \) -Matrix \( A \mathrm{mit} \)
$$ x_{n+1}=A x_{n} $$
Mit vollständiger Induktion folgt dann \( x_{n}=A^{n-1} x_{1} . \) Insbesondere ist die Fibonacci-Zahl \( f_{n} \) der erste Eintrag des Vektors \( A^{n-1} x_{1} \)
(c) Bestimmen Sie eine explizite Formel für die \( n \) -te Fibonacci-Zahl, indem Sie die Potenzen \( A^{n} \) bestimmen.

Answer 1

(a)

Anwenden der Definition...

$$f_1=1$$

$$f_2=1$$

$$f_3=f_1+f_2=1+1=2$$

$$f_4=f_2+f_3=1+2=3$$

$$f_5=f_3+f_4=2+3=5$$

$$f_6=f_4+f_5=3+5=8$$

$$f_7=f_5+f_6=5+8=13$$

$$f_8=f_6+f_7=8+13=21$$

(b)

$$\text{Offenbar gilt } x_{n+1} = \begin{pmatrix} f_{n+1} \\ f_{n+2} \end{pmatrix}  = \begin{pmatrix} f_{n+1} \\ f_{n}+f_{n+1}  \end{pmatrix} =  \begin{pmatrix} 0\cdot f_n + 1\cdot  f_{n+1} \\ 1\cdot f_{n}+ 1\cdot f_{n+1}  \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} f_n \\ f_{n+1} \end{pmatrix}$$

$$\text{Damit ist also } A=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \text{ die gesuchte Matrix.}$$

$$\text{Vollständige Induktion über n (eigentlich fast irrelevant):}$$

$$\text{Induktionsanfang: Für } n=1 \text{ folgt } x_1=\begin{pmatrix} 1 \\ 1 \end{pmatrix} = E_2 \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} = A^0 \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} = A^0 \cdot x_1.$$

$$\text{Hinweis: } E_2=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \text{ bezeichnet die } 2\times 2 \text{ Einheitsmatrix.}$$

$$\text{Induktionshypothese: Für alle } k\in \mathbb{N}, \,1\leq k \leq n \text{ gilt } x_k=A^{k-1} \cdot x_1.$$

$$\text{Induktionsschritte }(n\mapsto n+1): x_{n+1} \overset{s.o.}{=} A\cdot x_n \overset{IH}{=} A\cdot A^{n-1} \cdot x_1 \overset{Ass.}{=} A^n\cdot x_1$$

(c)

$$\text{Um } A^n \text{ zu ermitteln, macht es Sinn eine Diagonalmatrix } D \text{ zu }A \text{ zu finden.}$$

$$\text{Die Eigenwerte finden sich bei } \lambda_1=\frac{1-\sqrt{5}}{2} \text{ und } \lambda_2=\frac{1+\sqrt{5}}{2} \text{, also ist } D=\begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix} .$$

$$\text{Es sind } S=\begin{pmatrix} \frac{-1-\sqrt{5}}{2} & \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \text{ und } S^{-1}=\begin{pmatrix} -\frac{1}{\sqrt{5}} & \frac{5-\sqrt{5}}{10} \\ \frac{1}{\sqrt{5}} & \frac{5+\sqrt{5}}{10}\end{pmatrix} \text{ Matrizen so, dass } \\D=S^{-1}\cdot A \cdot S \Rightarrow A=S\cdot D\cdot S^{-1} \Rightarrow A^n=S\cdot D^n\cdot S^{-1}.$$

$$\text{Damit folgt } A^n = \begin{pmatrix} \frac{-1-\sqrt{5}}{2} & \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} \left(\frac{1-\sqrt{5}}{2}\right)^n & 0 \\ 0 & \left(\frac{1+\sqrt{5}}{2}\right)^n\end{pmatrix} \cdot \begin{pmatrix} -\frac{1}{\sqrt{5}} & \frac{5-\sqrt{5}}{10} \\ \frac{1}{\sqrt{5}} & \frac{5+\sqrt{5}}{10}\end{pmatrix}$$

$$\text{Letztlich folgt (es interessiert nur die untere Zeile des Ergebnisvektors) } \\A^n\cdot x_1 = \begin{pmatrix} \frac{-1-\sqrt{5}}{2} & \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} \left(\frac{1-\sqrt{5}}{2}\right)^n & 0 \\ 0 & \left(\frac{1+\sqrt{5}}{2}\right)^n\end{pmatrix} \cdot \begin{pmatrix} -\frac{1}{\sqrt{5}} & \frac{5-\sqrt{5}}{10} \\ \frac{1}{\sqrt{5}} & \frac{5+\sqrt{5}}{10}\end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix}$$

$$=\frac{1}{\sqrt{5}}\cdot\begin{pmatrix} \frac{-1-\sqrt{5}}{2} & \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} \left(\frac{1-\sqrt{5}}{2}\right)^n & 0 \\ 0 & \left(\frac{1+\sqrt{5}}{2}\right)^n\end{pmatrix} \cdot \begin{pmatrix} \frac{-3+\sqrt{5}}{2} \\ \frac{3+\sqrt{5}}{2} \end{pmatrix}$$
$$=\frac{1}{\sqrt{5}}\cdot\begin{pmatrix} \frac{-1-\sqrt{5}}{2} & \frac{-1+\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} \left(\frac{-3+\sqrt{5}}{2}\right) \cdot \left(\frac{1-\sqrt{5}}{2}\right)^n \\ \left(\frac{3+\sqrt{5}}{2}\right) \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n \end{pmatrix}$$
$$=\frac{1}{\sqrt{5}}\cdot \begin{pmatrix} ... \\ \left(\frac{-3+\sqrt{5}}{2}\right) \cdot \left(\frac{1-\sqrt{5}}{2}\right)^n +  \left(\frac{3+\sqrt{5}}{2}\right) \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n \end{pmatrix}$$
$$=\frac{1}{\sqrt{5}}\cdot \begin{pmatrix} ... \\ -\left(\frac{1-\sqrt{5}}{2}\right)^2 \cdot \left(\frac{1-\sqrt{5}}{2}\right)^n +  \left(\frac{1+\sqrt{5}}{2}\right)^2 \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n \end{pmatrix}$$
$$=\frac{1}{\sqrt{5}}\cdot \begin{pmatrix} ... \\ -\left(\frac{1-\sqrt{5}}{2}\right)^{n+2} +  \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} \end{pmatrix}$$
$$=\begin{pmatrix} ... \\ \frac{1}{\sqrt{5}} \cdot \left(-\left(\frac{1-\sqrt{5}}{2}\right)^{n+2} +  \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} \right) \end{pmatrix}$$
$$=\begin{pmatrix} ... \\ f_{n+2} \end{pmatrix}$$

$$\text{Damit folgt insbesondere durch Indexverschiebung } f_n = \frac{1}{\sqrt{5}} \cdot \left(-\left(\frac{1-\sqrt{5}}{2}\right)^{n} +  \left(\frac{1+\sqrt{5}}{2}\right)^{n} \right).$$