[Diskrete Strukturen] Induktionsbeweis (?) zu Fibonacci-Folge

05.01.2015, 10:15

JayKay42

[Diskrete Strukturen] Induktionsbeweis (?) zu Fibonacci-Folge

Hallo!

Ich habe mal wieder eine Frage:

[EDIT: ist das eigentlich der richtige Beweis, oder in welchen Bereich statt sonstiges kommt es korrekter Weise hinein?)

Es ist zu zeigen, dass:

$\begin{eqnarray*} \sum\limits_{i=1}^n F_i = F_{n+2} -1 \end{eqnarray*}$

Mein erster Gedanke und Lösungsansatz: Das ist ein Induktionsbeweis.

Ferner weiß ich noch folgendes:

$\begin{eqnarray*} F_n = F_{n-1}+F_{n-2} \end{eqnarray*}$ für alle n>2 und

$\begin{eqnarray*} F1 = F2 = 1 \end{eqnarray*}$ .

Mein Induktionsanfang (i=1):

F_1 = 1 = F_{1+2}-1 = F3 - 1 = 2-1 = 1 korrekt!

F3 habe ich übrigens herausbekommen mittels:

$\begin{eqnarray*} F_3 = F_{3-1}+F_{3-2} = F_2+F_1 = 1+1 = 2 \end{eqnarray*}$

Induktionsvorraussetzung: Für ein beliebiges, aber festes n gilt:

$\begin{eqnarray*} \sum\limits_{i=1}^{n+1} F_i = F_{(n+1)+2} - 1 \end{eqnarray*}$

Induktionsschritt:

$\begin{eqnarray*} F_i = F_{(n+1)+2} - 1 \end{eqnarray*}$
$\begin{eqnarray*} F_i = F_{n+3} - 1 \end{eqnarray*}$

Da hakts dann. Ich muss ja letzen Endes auf $\begin{eqnarray*} F_{n+2}-1 \end{eqnarray*}$ wieder kommen. Allerdings hilft mir da das Umformen zu n+3 nicht weiter, und auch sonst bin ich überfragt, was "dazwischen" kommt. Ich muss irgendwo noch die Induktionsvorraussetzung einbauen. Aber diese soll ich ja auch irgendwie beweisen. Da beißt sich meiner Meinung nach die Katze in den Schwanz. Wie komme ich da zu einem gescheiten Zwischenschritt der mir weiter hilft?

05.01.2015, 11:32

Elvis

Auf diesen Beitrag antworten »

Der Induktionsanfang ist falsch, weil $\begin{eqnarray*} F_0 \end{eqnarray*}$ und $\begin{eqnarray*} F_{-1} \end{eqnarray*}$ nicht definiert sind. Der Induktionsanfang wird für n=3 gemacht.

Der Induktionsschritt ist auch falsch. Aus der Voraussetzung $\begin{eqnarray*} \sum_{i=1}^n F_i=F_{n+2}-1 \end{eqnarray*}$ musst du auf $\begin{eqnarray*} \sum_{i=1}^{n+1} F_i=F_{n+1+2}-1 \end{eqnarray*}$

05.01.2015, 12:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Der Induktionsanfang ist falsch, weil $\begin{eqnarray*} F_0 \end{eqnarray*}$ und $\begin{eqnarray*} F_{-1} \end{eqnarray*}$ nicht definiert sind. Der Induktionsanfang wird für n=3 gemacht.

Der sieht doch oben eigentlich ganz gut aus. Ok, es sollte da n=1 statt i=1 stehen, aber ansonsten ist er doch Ok. verwirrt

Schon eher zu kritisieren ist die Induktionsvoraussetzung: Wenn (wie ich annehme) der Induktionsschritt $\begin{align*} n\to n+1 \end{align*}$ beabsichtigt ist, dann ist $\begin{eqnarray*} \sum\limits_{i=1}^{n+1} F_i = F_{(n+1)+2} - 1 \end{eqnarray*}$ ja die Induktionsbehauptung, nicht die -voraussetzung. unglücklich

Und der Induktionsschritt ist in der Tat Blödsinn: Während man im Induktionsanfang bei

$\begin{align*} \sum_{i=1}^1 F_i = F_1 \end{align*}$

tatsächlich noch das Summenzeichen weglassen konnte, weil es schlicht nur ein Summand war, geht das bei allgemeinem $\begin{align*} n \end{align*}$ selbstverständlich nicht mehr! Forum Kloppe

05.01.2015, 13:37

Elvis

Auf diesen Beitrag antworten »

Bitte um Entschuldigung, der Induktionsanfang war im Wesentlichen in Ordnung.

05.01.2015, 15:13

JayKay42

Auf diesen Beitrag antworten »

Hallo,

Zitat:

Der sieht doch oben eigentlich ganz gut aus. Ok, es sollte da n=1 statt i=1 stehen, aber ansonsten ist er doch Ok.

An welcher Stelle genau? Wann wandle ich das in ein n um? Bei der Vorraussetzung unter der Summe?

Dann habe ich Behauptung und Vorraussetzung durcheinander gebracht. Die Vorraussetzung, die gilt, muss ich ja beweisen um sie später dann einsetzen zu können um auf das gewünschte Endergebnis zu kommen. Das werde ich mir wohl noch einmal anschauen müssen. traurig

05.01.2015, 15:30

HAL 9000

Auf diesen Beitrag antworten »

Ich habe davon geredet:

Zitat:

Original von JayKay42
Mein Induktionsanfang (i=1):

Was natürlich Quatsch ist, denn $\begin{align*} i \end{align*}$ als Summenindex hat außerhalb des Summenrahmens keinerlei inhaltliche Bedeutung, und hat damit insbesondere in der Beschreibung des Induktionsanfangs nicht das geringste zu suchen.

05.01.2015, 18:14

Elvis

Auf diesen Beitrag antworten »

Bei vollständiger Induktion muss man die Induktionsvoraussetzung voraussetzen, deshalb heißt sie Voraussetzung. Eine Voraussetzung kann man nicht beweisen.

Aus der Voraussetzung $\begin{eqnarray*} \sum_{i=1}^n F_i=F_{n+2}-1 \end{eqnarray*}$ musst du auf $\begin{eqnarray*} \sum_{i=1}^{n+1} F_i=F_{n+1+2}-1 \end{eqnarray*}$ schließen, das nennt man Induktionsschluß.

05.01.2015, 21:16

JayKay42

Auf diesen Beitrag antworten »

Zitat:

Was natürlich Quatsch ist, denn i als Summenindex hat außerhalb des Summenrahmens keinerlei inhaltliche Bedeutung, und hat damit insbesondere in der Beschreibung des Induktionsanfangs nicht das geringste zu suchen.

Ja, da ist es in der Tat Quatsch und war ein Versehen. Ich will ja auf das "nachfolgende Element", also n+1 schließen und nicht auf irgendein i. Schlichtweg Typo.

Ich habe noch einmal in anderen Aufgaben nachgeschlagen. Bei der Induktionsvorraussetzung haben wir immer die Kernaussage der Aufgabe stehen, also hier in diesem Fall,

Für ein beliebiges, aber festes n gilt:

$\begin{eqnarray*} \sum\limits_{i=1}^{n} F_i = F_{(n+2} - 1 \end{eqnarray*}$

Nämlich ohne n+1, sondern einfach nur die Aufgabe plus die Angabe, dass es für ein "beliebiges, aber festes n" gelten soll.

Mit der Summe stimmt das natürlich. Der Trick ist bei solchen Aufgaben ja oft, etwas vor die Summe zu ziehen, was oben schon bewiesen worden ist in der Induktionsannahme und was man dann gescheit einsetzen kann. (Hoffe ich habe das richtig ausgedrückt).

Die Summe oben heißt ja ausgeschrieben und gleich Werte / Zahlen eingesetzt:

(F_1 = F_3 -1) + (F_2 = F_4 - 1) + F_3 = F_5 -1) + ... + (F_n = F_{n+2} - 1)

Ich versuche also, einen Teil vor die Summe zu ziehen.

$\begin{eqnarray*} (F_1 = F_{1+2} - 1) + \sum\limits_{i=2}^n F_i = F_{n+2} - 1 \end{eqnarray*}$

Den ersten Teil habe ich ja oben schon bewiesen, denn das ist 1. Allerdings bringt mir das jetzt irgendwie nicht wirklich was, um auf n+3 in der Summe zu kommen. Ich muss ja irgendwie hinkommen zu "gilt für dieses, und für das nächste!".

06.01.2015, 11:46

Elvis

Auf diesen Beitrag antworten »

Probier's mal so :

$\begin{eqnarray*} \sum_{i=1}^{n+1} F_i=\sum_{i=1}^{n} F_i+F_{n+1}=... \end{eqnarray*}$

Die Summe bis n kennst du nach Voraussetzung und $\begin{eqnarray*} F_{n+1} \end{eqnarray*}$ hat Fibonacci definiert.

Neue Frage »

Antworten »

[Diskrete Strukturen] Induktionsbeweis (?) zu Fibonacci-Folge

Verwandte Themen