Bis jetzt hast du ja anscheinend noch nicht viel gemacht, außer die ersten paar Funktionswerte zu berechnen. Per Definition müssen wir für \(f=O(g)\) zeigen, dass

\(\exists M,x_0\in\mathbb N\ \forall x\geq x_0\colon f(x)\leq Mg(x)\)

oder äquivalent dazu

\(\limsup_{x\to\infty}\left|\frac{f(x)}{g(x)}\right|<\infty\).

Wir werden mit der zweiten Formel arbeiten. Um \(f\) und \(g\) in ein Verhältnis zu bringen, stellen wir erstmal eine explizite Formel für \(f(n)\) auf. Dazu benutzen wir die Formel von Moivre-Binet für die explizite Darstellung der \(n\)-ten Fibonacci-Zahl. Wir erhalten

\(f(n)=\frac{\left(\frac{1+\sqrt5}2\right)^{(2n+1)+1}-\left(\frac{1-\sqrt5}2\right)^{(2n+1)+1}}{\sqrt5}=\frac{\left(\frac{3+\sqrt5}2\right)^{n+1}-\left(\frac{3-\sqrt5}2\right)^{n+1}}{\sqrt5}\)

Jetzt können wir den Quotienten \(\frac fg\) in einer sinnvollen Form bilden:

\(\begin{align}\frac{f(n)}{g(n)}&=\frac{\frac{\left(\frac{3+\sqrt5}2\right)^{n+1}-\left(\frac{3-\sqrt5}2\right)^{n+1}}{\sqrt5}}{\left(\frac{3+\sqrt5}2\right)^n}\\&=\frac{5+3\sqrt5}{10}+\frac{5-3\sqrt5}{10}\left(\frac{3-\sqrt5}{3+\sqrt5}\right)^n\end{align}\)

Schau, ob du die Rechnung selbst nachvollziehen kannst, ich hab ein paar Schritte übersprungen. Auf jeden Fall ist der Grenzwert für \(n\to\infty\) sicher endlich (warum? Was passiert mit der Potenz?) und von 0 verschieden. Weil er endlich ist, ist \(f=O(g)\), weil er nicht 0 ist, können wir den Kehrwert nehmen und erhalten \(\limsup_{n\to\infty}\frac{g(n)}{f(n)}<\infty\) und damit auch \(g=O(f)\).

Eine Wertetabelle ist sicher hilfreich, um sich ein Bild zu machen. Aber es geht ja um das Verhalten für \(n \to \infty\), da führt das nicht sehr weit. Kennst du die explizite Formel für die Fibonacci-Folge, die Formel von Moivre-Binet?

\[f_n = \frac{\Phi^n-\Psi^n}{\sqrt5}
            = \frac1{\sqrt 5} \left( \left(\frac{1+\sqrt 5}2\right)^n - \left(\frac{1-\sqrt 5}2\right)^n \right)\]

Damit kommst du wahrscheinlich weiter.