Fibonacci Abschätzung O-Notation

Question

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 ?

Answer 1

Hallo

Wenn Fib(n)>2*Fib(n-1) folgt Fib(n-1)>2*Fib(n-2) mit demselben Argument

daraus dann Fib(n)>2*2*F(n-2)

lul