Die Fibonacci-Zahlen Fn. Zeige die Ungleichung Fn ≤ 2^n

Question

Die Fibonacci-Zahlen Fn, n ∈ N, sind rekursiv definiert durch
F1 := F2 := 1, Fn := Fn−2 + Fn−1.
Beweisen Sie, dass für die n-te Fibonacci-Zahl gilt Fn ≤ 2ⁿ

Könnte mir jemand bei dieser Aufgabe bitte behilflich sein?

Answer 1

Führe einen Induktionsbeweis.

Der Induktionsanfang sollte darin bestehen, es für F1 und F2 zu zeigen.

Da danach F_n die Summe aus F_n-1 und den noch kleineren Summanden F_n-2 ist, kann bei der Addition von  F_n-1 und  F_n-2 diese Summe nicht doppelt so groß wie F_n-1 werden.