0 Daumen
1,1k Aufrufe

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 ≤ 2n


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

Avatar von

1 Antwort

0 Daumen

Führe einen Induktionsbeweis.

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

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

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community