Behouptry: Fib \( (n) \in O\left(2^{n}\right) \)
Mit Induktion über \( n \).
Basis: \( n=0 \) und \( n=1 \) : trivial
Betrachte \( n>2 \).
Es gilt: Fib(n)>0 \( \quad f_{n} \geqslant 0 \)
\( F_{i b}(n)<F_{i b}(n+1) \quad \forall n \geqslant 1 \)
\( \begin{array}{l} F_{i b}(n)=F_{i b}(n-1)+F i b(n-2) \\ <F_{i b}(n-1)+F_{i b}(n-1) \\ \text { = 2 * Fib }(n-1) \\ <\quad 4 \cdot \text { Fib }(n-2) \\ <2^{n-1} \cdot 1=\frac{1}{2} \cdot 2^{n} \\ \end{array} \)
Hallo,
ich verstehe nicht ganz wie man hier auf die Abschätzungen kommt, wieso ist z.B. 2*Fib(n-1) < 4*Fib(n-2), was ist hier die Idee ?
