Fibonacci Induktion

07.12.2016, 18:01

NoobOfNerds

Fibonacci Induktion

Meine Frage:
Guten Tag,

Ich versuche schon seit Stunden verzweifelt folgende Gleichung mittels Vollständiger Induktion zu beweisen.

$\begin{eqnarray*} F_{n+10} = F_{n-2}*F_{10} + F_{n-1}*F_{11} \end{eqnarray*}$

Mit F ist hier immer die Fibonaccifolge gemeint.

Die Bedingung ist hier dass n > 1 ist.

Meine Ideen:

Induktionsanfang:
$\begin{eqnarray*} F_{n+10} = F_{n-2}*F_{10} + F_{n-1}*F_{11} \end{eqnarray*}$
$\begin{eqnarray*} F_{12} = 1*F_{10} + 1*F_{11}\checkmark \end{eqnarray*}$

Induktionsvorraussetzung:
n=k; $\begin{eqnarray*} F_{k+10} = F_{k-2}*F_{10} + F_{k-1}*F_{11} \end{eqnarray*}$

Induktionsbehauptung:
n=k+1; $\begin{eqnarray*} F_{k+11} = F_{k-1}*F_{10} + F_{k}*F_{11} \end{eqnarray*}$

Induktionsbeweis: (Hier bin ich mir nicht mehr sicher mit welcher Seite ich weiter machen soll, aber meine Überlegungen führen immer auf das ähnliche hinaus.)

$\begin{eqnarray*} F_{n-1}*F_{10} + F_{n}*F_{11} \end{eqnarray*}$ $\begin{eqnarray*} = F_{k-1}* \left(F_{41}+F_{40} \right) + F_{k} * \left( F_{42}+ F_{41} \right) \end{eqnarray*}$ $\begin{eqnarray*} = F_{k-1} * F_{41} + F_{k-1} * F_{40} + F_{k} * F_{42} + F_{k} + F_{41} \end{eqnarray*}$

07.12.2016, 18:17

HAL 9000

Auf diesen Beitrag antworten »

Vorabfrage: In der Regel meint man mit Fibonacci-Folge die Folge $\begin{align*} F_n=F_{n-1}+F_{n-2} \end{align*}$ mit Start $\begin{align*} F_0=0,F_1=1 \end{align*}$ . Bei dir hingegen ist aber anscheinend der Start "verschoben" mit $\begin{align*} F_0=1,F_1=1 \end{align*}$ . verwirrt

Woher hier nun plötzlich $\begin{align*} F_{40} \end{align*}$ sowie $\begin{align*} F_{41} \end{align*}$ auftauchen, bleibt wohl dein Geheimnis.

Generell wird der Beweis eher nicht als Induktion $\begin{align*} k\to k+1 \end{align*}$ funktionieren, sondern wohl eher $\begin{align*} k-1,k\to k+1 \end{align*}$ , denn man benötigt nicht nur einen, sondern zwei Vorgänger. Das klappt natürlich nur, wenn auch der Induktionsanfang zwei statt nur einen Wert umfasst.

P.S.: Deine Behauptung ist der Spezialfall $\begin{align*} m=10 \end{align*}$ der allgemeineren Behauptung $\begin{align*} F_{n+m} = F_{n-2}F_m + F_{n-1}F_{m+1} \end{align*}$ .

07.12.2016, 18:28

iTutHD

Auf diesen Beitrag antworten »

Danke schonmal für die schnelle Antwort!

Genau diese Verschiebung ist mir warum auch immer vorgegeben.

Das im Induktionsschritt $\begin{eqnarray*} F_{40} und F_{41} \end{eqnarray*}$ vorkommen ist, leider durch ein durcheinander kommen meiner Unterlagen zu verschulden. Entschuldigung dafür!

Mir ist leider nicht ganz verständlich, was du mir sagen willst. Das hört sich für mich so an als ob die Aufgabe unter den Bedingungen garnicht lösbar ist?

PS.: Habe mir mal einen Account erstellt, da ich das doch für ganz sinnvoll erachte.

07.12.2016, 18:30

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von iTutHD
Das hört sich für mich so an als ob die Aufgabe unter den Bedingungen garnicht lösbar ist?

Dann hast du meine Antwort nicht richtig durchdacht.

07.12.2016, 18:37

iTutHD

Auf diesen Beitrag antworten »

Doch jedoch ist es mir nicht ganz schlüssig.

Du meinst, dass ich im Induktionsanfang 2 Fälle brauche statt einen.

Aber so wie ich das gelernt habe, benutzt man die Fälle erst in der Induktionsbehauptung.

Meinst du dass ich bei dem was ich als Induktionsbehauptung kenne, einmal n -> k+1 und einmal n -> k -1 brauche?

Wenn ja könntest du mir villeicht erklären wie ich da weiter machen muss?

Wir haben bis jetzt nur Induktionen mit 1nem Fall(nämlich n-> k+1) bearbeitet und ich vermute mal, dass man das ganze in irgend einer Art und Weise verknüpfen muss.

08.12.2016, 09:07

HAL 9000

Auf diesen Beitrag antworten »

Das ist keine "neue" Art Induktion, sondern lässt sich problemlos in das gewohnte Schema eintakten: Man beweist einfach die Aussage

Zitat:

$\begin{align*} A(n) \end{align*}$ : Es gelten sowohl

$\begin{align*} F_{n+10} = F_{n-2}\cdot F_{10} + F_{n-1}\cdot F_{11} \end{align*}$

als auch

$\begin{align*} F_{n+11} = F_{n-1}\cdot F_{10} + F_{n}\cdot F_{11} \end{align*}$

per Vollständiger Induktion. Im Induktionsanfang $\begin{align*} n=2 \end{align*}$ muss dann sowohl

$\begin{align*} F_{12} = F_0\cdot F_{10} + F_1\cdot F_{11} \end{align*}$

als auch

$\begin{align*} F_{13} = F_1\cdot F_{10} + F_2\cdot F_{11} \end{align*}$

nachgewiesen werden. Der positive Effekt ist, dass du im Induktionsschritt $\begin{align*} n\to n+1 \end{align*}$ zum Nachweis der Aussage $\begin{align*} A(n+1) \end{align*}$ auf die Aussage $\begin{align*} A(n) \end{align*}$ zurückgreifen darfst, mit beiden Gleichungen.

Neue Frage »

Antworten »

Fibonacci Induktion

Verwandte Themen