Autor |
Beitrag |
Stefan
| Veröffentlicht am Freitag, den 03. November, 2000 - 22:53: |
|
Hallo, obwohl in diesem Forum schon einiges über die Fibonacci-Zahlenreihe diskutiert wurde, komme ich damit nicht ganz klar. Die Fibonacci Zahlen errechnen sich ja aus der Summe der zwei vorhergehenden Glieder, also: U0=0; U1=1; U2=1; U3=2; U4=3; U5=5; U6=8 usw. Es gilt für diese Zahlen nun folgendes (Indizes in eckigen Klammern): (I) U[n+m] = U[n-1]U[m] + U[n]U[m+1] Das soll per vollst. Ind. bewiesen werden. Einen geeigneten Induktionsanfang findet man. Allerdings ist die Vorschrift ja von m und n abhängig, muss man also sowohl von m auf m+1, und von n auf n+1 schliessen? Ich habe mal für n+1 ein bisschen rumgerechnet: U[n+m+1] = U[n]U[m] + U[n+1]U[m+1] U[n+m] + U[n+m-1] = (U[n-1] + U[n-2])U[m] + (U[n]+U[n-1])U[m+1] wenn man das ausmultipliziert findet man einiges aus der Induktionsvorraussetzung (I) wieder, so dass stehenbleibt: U[n+m-1] = U[n-2]U[m] + U[n-1]U[m+1] Kann mich jemand auf die richtige Spur bringen? Danke, Stefan |
Zaph (Zaph)
| Veröffentlicht am Samstag, den 04. November, 2000 - 11:41: |
|
Du bist doch schon fast da! Musst das bloß andersrum aufschreiben. Induktion über n. n=1, n=2: [hoffentlich klar] Beachte, dass du zwei Induktionsanfänge brauchst! Sei nun n >= 2. Nach IV gilt U[n+m] = U[n-1]U[m] + U[n]U[m+1] und (!) U[n+m-1] = U[n-2]U[m] + U[n-1]U[m+1] Es folgt U[n+m+1] = U[n+m] + U[n+m-1] = U[n-1]U[m] + U[n]U[m+1] + U[n-2]U[m] + U[n-1]U[m+1] = (U[n-1] + U[n-2])U[m] + (U[n] + U[n-1])U[m+1] = U[n]U[m] + U[n+1]U[m+1] |
Stefan
| Veröffentlicht am Samstag, den 04. November, 2000 - 19:53: |
|
hallo Zaph, ich verstehe nicht, warum U[n+m-1] = U[n-2]U[m] + U[n-1]U[m+1] auch Induktionsvorraussetzung sein soll. Wenn man U[n+m] = U[n-1]U[m] + U[n]U[m+1] und U[n+m-1] = U[n-2]U[m] + U[n-1]U[m+1] vorraussetzt, dann wäre das ja schon ein vollwertiger Schluss von n auf n+1 (bloss mit Verschiebung um -1), den wir ja erst per Induktion beweisen wollen! Ansonsten ist es mir klar, das man dann auf das gewünschte U[n+m+1] = U[n]U[m] + U[n+1]U[m+1] kommt. Gruss, Stefan |
Zaph (Zaph)
| Veröffentlicht am Samstag, den 04. November, 2000 - 20:34: |
|
Hallo Stefan, beim Induktionsschluss ist die Behauptung für n+1 (U[n+1+m] = ...) zu zeigen. Als Induktionsvoraussetzung verwendest du die Formeln für n und n-1 (U[n+m] = ..., U[n-1+m] = ....). Normalerweise wird beim Induktionsschluss von n auf n + 1 geschlossen. Hier wird als Induktionsvorausetzung angenommen, dass die Behauptung bereits für alle Werte bis einschließlich n gültig ist. Da du beim Induktionsschritt um zwei (und nicht wie sonst üblich um eins) zurück musst, ist der Induktionsanfang doppelt (für n = 1 und n = 2) zu führen. Hoffe, jetzt ist ales klar. |
Jasmin
| Veröffentlicht am Freitag, den 10. November, 2000 - 09:22: |
|
Könnt ihr mir erklären, was Induktion ist? |
Matroid (Matroid)
| Veröffentlicht am Freitag, den 10. November, 2000 - 16:18: |
|
Hi Jasmin, ich habe hier einiges erklärt: {http://www.zahlreich.de/cgi-bin/hausaufgaben/show.cgi?25/6775,http://www.zahlreich.de/cgi-bin/hausaufgaben/show.cgi?25/6775}. Am besten liest Du zuerst den letzten Beitrag. Gruß Matroid |
Abeer Swidan (Abura)
| Veröffentlicht am Dienstag, den 29. Mai, 2001 - 20:30: |
|
zu beweisen ist:F(n)= 1/(Wurzel 5)*(((1+(Wurzel 5))/2)-(1-(Wurzel 5))/2))^n mit vollstaendige Induktion) |
Jens
| Veröffentlicht am Dienstag, den 29. Mai, 2001 - 20:53: |
|
Hey Abura, schau dir diesen Link mal an: http://www.mathehotline.de/mathe4u/hausaufgaben/messages/4244/15748.html?989941338 Damit hab ichs auch geschafft. Grüße, Jens |
Abeer Swidan (Abura)
| Veröffentlicht am Mittwoch, den 30. Mai, 2001 - 10:31: |
|
Danke Jens,das war sehr hilfreich. Hast du auch eine Ahnung,wie man diese Aufgabe löst: Der euklidische Algorithmus bestimmt zu zwei gegebenen natürlichen Zahlen 1<=x<=y den ggT(x,y).Man zeige:Die Anzahl der Schritte des euklidischen Algorithmus ist O(logy). Hinweis:Zeige,daß Xn+1<Xn/2 für n=0,1,2... . |
|