matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-Analysis-InduktionFibonacci-Zahlen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Uni-Analysis-Induktion" - Fibonacci-Zahlen
Fibonacci-Zahlen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Fibonacci-Zahlen: Frage
Status: (Frage) beantwortet Status 
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.

        
Bezug
Fibonacci-Zahlen: rückfrage und idee
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Fibonacci-Zahlen: Rückfrage
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Fibonacci-Zahlen: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                
Bezug
Fibonacci-Zahlen: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 18:46 Mi 27.10.2004
Autor: misterbecks

Der letzte Schritt wird mir auch nicht ganz klar. Auch das Beweisende verstehe ich nicht...wieso ist die Formel dann allgemein bewiesen?

Bezug
                        
Bezug
Fibonacci-Zahlen: Erklärung
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Fibonacci-Zahlen: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 21:35 Mi 27.10.2004
Autor: misterbecks

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.....

Bezug
                                        
Bezug
Fibonacci-Zahlen: Induktionsbeweise
Status: (Antwort) fertig Status 
Datum: 01:34 Do 28.10.2004
Autor: Hugo_Sanchez-Vicario

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]