Beweisen Sie durch Induktion

Question

Aufgabe:

Die Fibonacci-Zahlen \( f_{n}, n \in \mathbb{N}_{0} \) sind definiert durch die Gleichungen
\( \begin{aligned} f_{0} &=0 \\ f_{1} &=1 \\ \forall n \in \mathbb{N}_{+}: f_{n+1} &=f_{n}+f_{n-1} \end{aligned} \)
a) Geben Sie die Zahlenwerte von \( f_{2}, f_{3}, f_{4} \) und \( f_{5} \) an.
b) Beweisen Sie durch Induktion, dass für alle \( n \in \mathbb{N}_{+} \)gilt:
\( f_{n} \leq\left(\frac{7}{4}\right)^{n-1} \)

Problem/Ansatz:

Habe Probleme bei folgender Aufgabe insbesondere bei Teilaufgabe b).

Answer 1

Hallo,

Habe Probleme bei folgender Aufgabe insbesondere bei Teilaufgabe b).

bei b) zeigt man zunächst für zwei auf einander folgende Elemente der Folge, dass die Forderung$$f_{n} \leq\left(\frac{7}{4}\right)^{n-1} $$erfüllt ist:$$f_1 = 1 \le \left(\frac{7}{4}\right)^{1-1} = 1\space \checkmark\\ f_2 = 1 \le \left(\frac{7}{4}\right)^{2-1} = \frac{7}{4}\space \checkmark$$Darauf kann man denn im Folgenden zurück greifen$$\begin{aligned} f_{n+1} &= f_n + f_{n+1}\\ &\leq \left(\frac{7}{4}\right)^{n-1}+\left(\frac{7}{4}\right)^{n-2}&&|\,\text{lt. Vor. (s.o.)}\\ &= \left(\frac{7}{4}\right)^{n-2}\left(\frac{7}{4}+ 1\right) \\ &= \left(\frac{7}{4}\right)^{n-2}\cdot \frac{11}{4}&&|\,\left(\frac{7}{4}\right)^2 = \frac{49}{16} \gt \frac{11}{4} \\ &\lt \left(\frac{7}{4}\right)^{n-2}\cdot\left(\frac{7}{4}\right)^2 \\ &= \left(\frac{7}{4}\right)^{n}\\ &\text{q.e.d.} \end{aligned}$$