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