Zeigen Sie mit vollständiger Induktion über n , dass F_{m+n}=F_{m-1} F_{n}+F_{m} F_{n+1} für alle natürlichen Zahlen …

Question

Text erkannt:

(c) Seien \( F_{n}, n \geq 1 \) die Fibonacci-Zahlen, das heißt \( F_{1}=F_{2}=1 \) und \( F_{n}=F_{n-2}+F_{n-1} \) für \( n \geq 3 \). Zeigen Sie mit vollständiger Induktion über \( n \), dass \( F_{m+n}=F_{m-1} F_{n}+F_{m} F_{n+1} \) für alle natürlichen Zahlen \( m \geq 2 \) und \( n \geq 1 \) gilt.
Hinweis: Verwenden Sie folgende Variante der vollständigen Induktion: Zeigen Sie im Induktionsanfang, dass die Aussage für \( n=1 \) und \( n=2 \) wahr ist. Nehmen Sie in der Induktionsbehauptung die Aussage für ein beliebiges \( n \geq 1 \) und für \( n+1 \) an und folgern Sie im Induktionsschluss die Aussage für \( n+2 \).

Aufgabe: Wie kann ich dieses Problem mit Vollständige Induktion lösen?

Answer 1

Ich mach mal den Induktionschritt \(n\rightarrow n+1\):

$$\begin{array}{rcl}F_{m+n+1} &= & F_{m+n}  + F_{m+n-1} \\& \stackrel{Ind.V.}{=} &F_{m-1}F_n + F_mF_{n+1}  + F_{m-1}F_{n-1} + F_mF_{n}\\& = & F_{m-1}(F_n+F_{n-1}) + F_m(F_{n+1}+F_n)\\&=& F_mF_{n+1} + F_{m-1}F_{n+2} \end{array}$$

Für \(n=1,2\) kannst du es direkt nachrechnen. Blabla mit \(n+2\) ist nicht notwendig.

Answer 2

Zeigen Sie im Induktionsanfang, dass die Aussage für \( n=1 \) und \( n=2 \) wahr ist.

\( F_{m+n}=F_{m-1} F_{n}+F_{m} F_{n+1} \)  gibt also

\( F_{m+1}=F_{m-1} F_{1}+F_{m} F_{2} = F_{m-1}+F_{m} \)

stimmt also. Und

\( F_{m+2}=F_{m-1} F_{2}+F_{m} F_{3} = F_{m-1}+2F_{m} \)

\( = F_{m-1}+F_{m}+F_{m}= F_{m+1}+F_{m}\)

stimmt also auch.

Nehmen Sie in der Induktionsbehauptung die Aussage für ein beliebiges \( n \geq 1 \) und für \( n+1 \) an und folgern Sie im Induktionsschluss die Aussage für \( n+2 \).

Sei also \( F_{m+n}=F_{m-1} F_{n}+F_{m} F_{n+1} \)

und  \( F_{m+n+1}=F_{m-1} F_{n+1}+F_{m} F_{n+2} \)

==>  \( F_{m+n+2}=F_{m+n+1}+ F_{m+n} \)

\(=F_{m-1} F_{n+1}+F_{m} F_{n+2} +F_{m-1} F_{n}+F_{m} F_{n+1} \)

Das müsste dann ergeben \( F_{m-1} F_{n+2}+F_{m} F_{n+3} \)

Tut es auch, denn

\(F_{m-1} F_{n+1}+F_{m} F_{n+2} +F_{m-1} F_{n}+F_{m} F_{n+1} \)

\(=F_{m-1} F_{n+1}+F_{m-1} F_{n}+F_{m} F_{n+2} +F_{m} F_{n+1} \)

\(=F_{m-1}( F_{n+1}+ F_{n}) +F_{m} (F_{n+2} + F_{n+1}) \)

\( = F_{m-1} F_{n+2}+F_{m} F_{n+3} \)

Comments

Wie haben Sie das am Ende bekommen?

Text erkannt:

Tut es auch, denn
\( \begin{array}{l} F_{m-1} F_{n+1}+F_{m} F_{n+2}+F_{m-1} F_{n}+ \\ F_{m} F_{n+1} \\ =F_{m-1} F_{n+1}+F_{m-1} F_{n}+F_{m} F_{n+2}+ \\ F_{m} F_{n+1} \\ =F_{m-1}\left(F_{n+1}+F_{n}\right)+F_{m}\left(F_{n+2}+F_{n+1}\right) \\ =F_{m-1} F_{n+2}+F_{m} F_{n+3} \end{array} \)

Danke für ihren Antwort

---

Es ist doch immer \( F_{n}=F_{n-2}+F_{n-1} \)

also \( F_{n+2}=F_{n}+F_{n+1} \)

und \( F_{n+3}=F_{n+1}+F_{n+2} \)

---

Noch eine Frage: Mit was Sie schon geschrieben haben, ist die Vollständige Induktion eigentlich  fertig?

DANKE DANKE DANKE YOU ARE THE BEST!!!

---

Ja, so ist es !