Autor |
Beitrag |
Mira13 (Mira13)
Mitglied Benutzername: Mira13
Nummer des Beitrags: 12 Registriert: 01-2003
| Veröffentlicht am Montag, den 06. Oktober, 2003 - 18:25: |
|
Hallo, Ich soll die folgende Formel mit vollständiger Induktion beweisen. Ich komme aber beim besten Willen zu keinem Ziel. Ich möchte daher um Hilfe bitten . Die Relation betrifft die Fibonaccizahlen und lautet: f(2n) = f(n) * {f(n-1) + f(n+1)} für n > = 1 wobei f(0) = 0 , f(1) = 1 f(n) = f(n-1) +f(n-2) für n > = 2. Für jede Hilfe bin ich dankbar Mit freundlichen Grüßen Mira
|
Martin243 (Martin243)
Senior Mitglied Benutzername: Martin243
Nummer des Beitrags: 779 Registriert: 02-2001
| Veröffentlicht am Montag, den 06. Oktober, 2003 - 21:59: |
|
Hi! Fangen wir mal mit dem Induktionsanfang an. Hier sind zwei Fälle zu betrachten. Mit der Null kann man wegen dem (n-1) nicht anfangen. Also: n=1: f(2n) = f(2*1) = f(2) = 1 = 1*(0+1) = f(1)*(f(0)+f(2)) = f(n)*(f(n-1) + f(n+1)) n=2: f(2n) = f(2*2) = f(4) = 3 = 1*(1+2) = f(2)*(f(1) + f(3)) = f(n)*(f(n-1) + f(n+1)) Induktionsvoraussetzung: für m=n und m=n+1 gilt: f(2m) = f(m) * {f(m-1) + f(m+1)} Induktionsschluss: f(2(n+2)) = f(2n+4) = f(2n+2) + f(2n+3) (Definition) = f(2(n+1)) + f(2n+1) + f(2n+2) (Def.) = 2*f(2(n+1)) + f(2n+1) = 2*f(2(n+1)) + f(2n+2) - f(2n) = 3*f(2(n+1)) - f(2n) = 3*f(n+1)*{f(n) + f(n+2)} - f(n)*{f(n-1) + f(n+1)} = 3*f(n)*f(n+1) + 3*f(n+1)*f(n+2) - f(n)*f(n-1) - f(n)*f(n+1) = f(n)*f(n+1) + 3*f(n+1)*f(n+2) + f(n)(f(n+1)-f(n-1)) = f(n)*f(n+1) + 3*f(n+1)*f(n+2) + f(n)*f(n) = f(n)*(f(n)+f(n+1)) + 3*f(n+1)*f(n+2) = f(n)*f(n+2) + 3*f(n+1)*f(n+2) = f(n+2)*[f(n)+f(n+1)+f(n+1)+f(n+1)] = f(n+2)*[f(n+1)+f(n+1)+f(n+2)] = f(n+2)*[f(n+1)+f(n+3)] q.e.d. Etwas länglich und ohne Erklärungen, aber die kann ich morgen nachliefern, wenn du Fragen hast. MfG Martin |
Megamath (Megamath)
Senior Mitglied Benutzername: Megamath
Nummer des Beitrags: 2754 Registriert: 07-2002
| Veröffentlicht am Dienstag, den 07. Oktober, 2003 - 11:20: |
|
Hi Mira, Deine Aufgabe kann auch dadurch gelöst werden, dass wir sie auf eine bereits gelöste zurückführen, nach dem Prinzip, den Hut von einem Haken an den andern zu hängen. Das ist eine recht wirksame und auch ökonomische Methode. Das geht so: Als zentrale Formel dient uns die am letzten Samstag von Orion mit vollständiger Induktion bewiesene Relation f(n+m) = f(n-1)*f(m) +f(n)*f(m+1) m > = 0, n > = 1 Setzen wir darin n = m, so kommt f(2n) =f(n-1)*f(n) +f(n)*f(n+1) °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Das ist aber genau die von Dir vorgelegte Formel. Damit ist der Fall erledigt. Gelegentlich formt man die rechte Seite R(n) um. Nach der Rekursionsvorschrift f(n+1) = f(n) + f(n-1) gilt: f(n) = f(n+1) - f(n-1), somit R(n) = {f(n + 1) - f( n - 1)} {f( n +1) + f( n - 1)} °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°° Mit freundlichen Grüßen H.R.Moser,megamath
|
Megamath (Megamath)
Senior Mitglied Benutzername: Megamath
Nummer des Beitrags: 2759 Registriert: 07-2002
| Veröffentlicht am Mittwoch, den 08. Oktober, 2003 - 13:46: |
|
Hi Martin Zu Deiner Lösung der Aufgabe von Mira möchte ich Dir gerne noch zwei Fragen stellen. 1. Geht die Verankerung nicht einfacher, in dem man bloss n = 1 setzt ? Dann kommt: f(2) = f(1) [f(0) + f(2) ) = 1 [ 0 + 1 ] = 1, was offensichtlich stimmt. 2. Die erste Zeile nach „Induktionsschluss“ verstehe ich nicht. Sollte nicht der Schluss von n auf n+1 vollzogen werden, also mit f(2(n+1)) = f(2n+2) statt mit f(2n + 4 ) begonnen werden? Vielleicht kann uns Jemand helfen und die Angelegenheit zu einem guten Ende führen! Mit freundlichen Grüßen H.R.Moser,megamath
|
|