Aufgabe:
Wenn man einen einfachen Fibonacci Algorithmus hat mit:
$$F_0 = 0\\ F_1 = 1\\ F_n = F_{n-1} + F_{n-2} \quad \text{for } n \geq 2$$
Wie beweißt man folgende Obergrenze für die Zeikomplexität ?
$$T(n) \leq 2^n \text{ für alle} n \geq 0$$
Problem/Ansatz:
$$\text{Anfang: } T(0) = 1 \text{und } 2^0 = 1 $$
Dann:
$$\text{[1] } T(n) = 2^{n-1}+2^{n-2}+1 \leq 2^n$$
Und soweit ich weiß, sollte das der nächste Schritt sein.
$$\text{[2] } 2^{n-1}+1 \leq 2^{n-1} \quad \text{ dasteht. }$$
Ich kann diesen Schritt nicht nachvollziehen. Hab alle Potenzgesetze die ich kenne rausgekramt, aber komme einfach nicht von [1] nach [2]. Und verstehe auch nicht wie mir der Anfang weiterhelfen könnte.