Verallgemeinerte Induktion, TU Dortmund

Question

Aufgabe:

Die Fibonacci-Funktion fib : N → N ist induktiv definiert durch:
fib(0) =df 0
fib(1) =df 1
fib(n) =df fib(n − 2) + fib(n − 1) für n ≥ 2

Beweisen Sie mit Hilfe verallgemeinerter Induktion, dass für alle natürlichen Zahlen n ∈ N gilt:
(n ≥ 11) ⇒ fib(n) ≥ \( \begin{pmatrix} \frac{3}{2} \end{pmatrix} \)^_n

Problem/Ansatz:

Hallo, wie löse ich am besten diese Aufgabe? Vielen Dank im voraus.

Comments

Was bedeutet das Kürzel df?

Answer 1

\(\begin{aligned}&\operatorname{fib}(n+1)\\=\ & \operatorname{fib}(n) + \operatorname{fib}(n-1)\\\geq\ & \left(\frac{3}{2}\right)^n +\left(\frac{3}{2}\right)^{n-1}\\=\ & \left(\frac{3}{2}\right)^{n-1}\cdot\left(\frac{3}{2}+1\right)\\=\ & \left(\frac{3}{2}\right)^{n-1}\cdot\frac{5}{2}\\=\ & \left(\frac{3}{2}\right)^{n-1}\cdot\frac{10}{4}\\\geq\ & \left(\frac{3}{2}\right)^{n-1}\cdot\frac{9}{4}\\=\ & \left(\frac{3}{2}\right)^{n-1}\cdot\left(\frac{3}{2}\right)^2\\=\ & \left(\frac{3}{2}\right)^{n+1}\end{aligned}\)