Fibonacci-Zahlen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:55 Sa 23.10.2004 | | Autor: | Mr.Mime |
Hi, ich habe hier eine Aufgabe, vermutlich mit vollständiger Induktion zu lösen. Leider komme ich momentan nicht auf den entscheidenden Schritt - hoffe mir kann hier jemand helfen.
Die Folge [mm]F_n [/mm] der Fibonaccizahlen ist definiert durch
[mm]F_1[/mm]=1, [mm]F_2[/mm]=2 und die Rekursionsgleichung
[mm]F_{n+1}[/mm] = [mm]F_n[/mm] + [mm]F_{n-1}[/mm] für n [mm]\ge[/mm]2.
Beweise:
[mm]F_{n+1}[/mm][mm]F_{n-1}[/mm] - [mm]F_n[/mm]² = [mm] (-1)^{n} [/mm] für n [mm]\ge[/mm]2.
Danke im Voraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:47 Sa 23.10.2004 | | Autor: | andreas |
hi
kann es sein, dass es [m] F_{n+1}F_{n-1} - F_n^2 = (-1)^{n+1} [/m] heißen soll, da für [m] n = 2 [/m] gilt: [m] F_3F_1 - F_2^n = 3 - 4 = -1 = (-1)^{3} \not= (-1)^2 [/m]
diese aufgabe würde ich so lösen, indem ich zeige, dass gilt
[m] F_{n+1}F_{n-1} - F_n^2 = \begin{cases} -1 & \textrm{wenn } n \textrm{ gerade} \\ 1 & \textrm{wenn } n \textrm{ ungerade} \end{cases} [/m]
also im prinzip zwei induktionen (zumindest zwei anfänge).
der schritt geht aber immer gleich: sei dei formel für alle [m] k \leq n - 1 [/m] bewiesen.
[m] \begin{array}{rcl} F_{n+1}F_{n-1} - F_n^2 & = & (F_n + F_{n-1}) F_{n-1} - (F_{n-1} + F_{n-2})^2 \\ & = & F_nF_{n-1} + F_{n-1}^2 - F_{n-1}^2 -2 F_{n-1}F_{n-2} - F_{n-2}^2 \\ & = & F_{n-1}(F_n - 2F_{n-2}) - F_{n-2}^2 \\ & = & F_{n-1} F_{n-3} - F_{n-2}^2 \end{array} [/m]
und schon bist du fertig.
probiere das mal nachzurechnen müsste eigentlich so stimmen, obwohl es auch etwas einfacher gehen sollte.
grüße
andreas
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:39 Di 26.10.2004 | | Autor: | Mr.Mime |
Hi Andreas, danke für die schnelle Antwort. Ich hab die Idee glaub ich verstanden, das dem vertauschten [mm] (-1)^{n} [/mm] ist mein Fehler - die ersten Glieder der Folge sind mit
[mm] F_1 [/mm] = 1 und [mm] F_2 [/mm] = 1 vorgegeben. Ich find aber gerade nicht raus wie man das editiert.. *g*
Eine Frage noch - wie kommst du im letzten Schritt von
[mm] F_n [/mm] - [mm] 2F_{n-2} [/mm] auf [mm] F_{n-3}? [/mm] Das kann ich irgendwie nicht richtig nachvollziehen..
Mfg, Mr.Mime
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:28 Mi 27.10.2004 | | Autor: | andreas |
> Eine Frage noch - wie kommst du im letzten Schritt von
>
> [mm]F_n[/mm] - [mm]2F_{n-2}[/mm] auf [mm]F_{n-3}?[/mm] Das kann ich irgendwie nicht
> richtig nachvollziehen..
setze einfach für [m] F_n [/m]die definition [m] F_{n-1} + F_{n-2} [/m] ein, vereinfache und setze danach nochmal die definition [m] F_{n-1} = F_{n-2} + F_{n-3} [/m] ein.
grüße
andreas
ps wenn du das jetzt verstanden hast kannst du ja vielleicht auf die rückfrage von misterbecks antworten. ich kann es auf jeden fall nicht mehr anders erklären.
|
|
|
| |
|
Der letzte Schritt wird mir auch nicht ganz klar. Auch das Beweisende verstehe ich nicht...wieso ist die Formel dann allgemein bewiesen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:18 Mi 27.10.2004 | | Autor: | Mr.Mime |
Hi misterbecks,
also den letzten Schritt hat andreas sehr gut erklärt, einfach 2 mal die Vorschrift anwenden, dann steht da [mm] F_{n-2} [/mm] + [mm] F_{n-2} [/mm] - [mm] 2F_{n-2}, [/mm] und damit bleibt nur das [mm] F_{n-3} [/mm] übrig, versuchs einfach mal nachzurechnen.
Was den Schritt an sich angeht - wir wollen beweisen, dass für jedes zweiten Wert von n der Term jeweils den selben Wert hat. Dies wird mit dem Induktionsschritt bewiesen. Soweit klar?
Nun müssen wir noch beweisen, dass es auch wirklich +1 bzw. -1 ist, was dabei rauskommt, das wird mit den 2 Induktionsanfängen bewiesen (also n=2 und n=3 in die Ausgangsformel einsetzen).
Wenn du in Bayern Statistik studierst, nehm ich mal an, dass wir im selben Kurs sind. ;) Vielleicht wirds ja morgen früh im Tutorium erklärt...
Mfg Mr.Mime
|
|
|
| |
|
Ja das sind wir wohl, vielleicht wird darauf morgen früh noch eingegangen. Aber das mit dem letzten Schritt ist mir noch nicht ganz klar. [mm] F_{n-1} F_{n-3} - F_{n-2}^2 [/mm] Wieso ist die Sache an dieser Stelle bewiesen.....? @Mr.Mime: Hast Du vielleicht ICQ oder so, dass Forum ist so extrem langsam.....
|
|
|
| |
|
Hallo Leute,
die Lösung von andreas funktioniert wie eine 'normale' Induktion, nur diesmal eben auf zwei Wegen.
Normalerweise zeigt man die Richtigkeit einer Aussage für einen Startwert, z.B. n=1 und schließt anschließend aus der Richtigkeit der Aussage für eine Zahl die Richtigkeit für deren Nachfolger.
Das geht hier nicht besonders gut.
Aber man kann zwei Startwerte nehmen, einen geraden und einen ungeraden. Jetzt macht man zwei Induktionen. Einmal für alle geraden Zahlen und einmal für alle ungeraden Zahlen. Dann hat man seine Aussage insgesamt auch für alle natürlichen Zahlen bewiesen.
Deswegen geht andreas bei seiner Lösung von n zwei Schritte zurück zu n-2 und bekommt heraus, dass der zu untersuchende Term für n den gleichen Wert hat wie für n-2. Also auch wie für n-4, n-6, usw. bis man am Ende bei 1 oder bei 2 rauskommt. Man erhält also entweder 1 oder -1, je nachdem ob die Zahl n gerade oder ungerade war.
Das ist der Grund, warum der Beweis funktioniert.
Hugo
|
|
|
|
