| Autor |
Beitrag |
    
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Montag, den 12. Juni, 2000 - 15:05: | 
|
Hallo Leute
Wie ich sehe, werden immer mehr Knobelaufgaben ins Board gestellt, also komme ich auch mal mit einer:
Wie ist die explizite Darstellung dieser rekursiv definierten Folge?
D0=0
D1=1
Dn=Dn-1+Dn-2+Fn+1
F bezeichnet die Fibonnaci-Zahlen, wobei gilt:
F0=0
F1=1
Fn=Fn-1+Fn-2 = (an-bn)/sqrt(5)
wobei a=(1+sqrt(5))/2 und b=(1-sqrt(5))/2
bin mal gespannt, wer drauf kommt.
Wem diese Folge zu sehr aus der Luft gegriffen erscheint, dem sein gesagt, dass sie die Gesamtlaenge aller Wege von der Wurzel bis zu den Blaettern in einem Fibonacci-Baum angibt.
MfG
SpockGeiger |
Anonym
| | Veröffentlicht am Dienstag, den 13. Juni, 2000 - 22:49: |
|
gar nicht so einfach ... |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Dienstag, den 13. Juni, 2000 - 23:06: |
|
Hallo
Ich dachte fast schon, die Welt wuerde mich verfluchen, und mir deswegen nicht antworten, dabei habe ich noch nicht einmal die Wasserstoffbombe erfunden;) Ich gehe jetzt einfach mal davon aus, dass es nicht an mir liegt, dass ich so lange keine Antwort bekomme, also ein Tipp: Nicht die Zahlen betrachten, die beim Einsetzen herauskommen, die ergeben naemlich viel weniger als einen Sinn. Versucht es erstmal mit einer Formel mit einem Summationszeichen! (in den Summanden kommen Fibonacci-Zahlen vor(!))...
noch viel Spass beim Loesen
SpockGeiger |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Freitag, den 16. Juni, 2000 - 13:29: |
|
Hallo ihr Genies da draussen!!!
hat keiner Interesse an dieser Aufgabe? Oder hat Zahlreich beschlossen, mich zu ignorieren???
Gruss
SpockGeiger |
Zaph
| | Veröffentlicht am Samstag, den 17. Juni, 2000 - 17:26: |
|
Hi SpockGeiger, ich hab's raus! Aber du kennst die Lösung, oder? |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Samstag, den 17. Juni, 2000 - 18:17: |
|
Hi Zaph
Ja ich habe die Loesung, hast Du Deine denn auch bewiesen? Ganz schoen harter Brocken, oder?
MfG
SpockGeiger |
Zaph
| | Veröffentlicht am Samstag, den 17. Juni, 2000 - 23:04: |
|
Allerdings! Ich wette, dass ich mich bei meiner Lösung mindestens ein Mal verrechnet habe. Deshalb meine Frage, ob du die Lösung schon kennst. Wenn nicht, hätte ich sie überprüft und gepostet. So spare ich mir die Arbeit. Gruß Z. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Sonntag, den 18. Juni, 2000 - 12:46: |
|
Hi Zaph
Zum Vergleichen:
Meine Loesung ist: 1/5*(n*(an+2+bn+2)+Fn)
Gruss
SpockGeiger |
Zaph
| | Veröffentlicht am Sonntag, den 18. Juni, 2000 - 22:08: |
|
Deine Lösung ist richtig, meine war falsch! Bis
Dn = a an + b n an + c bn + d n bn
bin ich auch gekommen, aber bei der Bestimmung von a, b, c und d bin ich dann gestrauchelt. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Sonntag, den 18. Juni, 2000 - 23:33: |
|
Hi Zaph
Woher wusstest Du denn diesen Ansatz???
Vielleicht bist Du auch zu sehr nach Schema F vorgegangen? Vielleicht interessiert Dich, wie ich auf die Loesung gekommen bin?
Gruss
SpockGeiger |
Zaph
| | Veröffentlicht am Montag, den 19. Juni, 2000 - 00:37: |
|
Hi SpockGeiger,
ja, ich bin absolut nach Schema verfahren. Zunächst habe ich die Rekursion für Dn aufgestellt, indem ich Fn eliminiert habe:
Dn+1 = 2 Dn + Dn-1 - 2 Dn-2 - Dn-3 ,
D0 = 0, D1 = 1, D2 = 3, D3 = 7.
Hieraus ergibt sich die "charakteristische Gleichung"
x4 = 2x3 + x2 - 2x - 1.
Diese Gleichung hat die Lösungen a und b jeweils doppelt. Daraus ergibt sich der Ansatz von oben. Man erhällt vier Gleichungen mit den vier Unbekannten a, b, c und d (für n nacheinander 0, 1, 2, 3 einsetzen). Daran bin ich gescheitert. Nachdem ich die vermeintliche Lösung hatte, war ich zu faul, die Probe zu machen.
Es interessiert mich sehr, wie du auf deine Lösung gekommen bist!
Gruß Zaph. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Montag, den 19. Juni, 2000 - 00:43: |
|
Hi Zaph
zunaechstmal verstehe ich nicht, wie Du dass Fn verschwinden laesst, zu dem anderen: ich bin doch ein bisschen faul, oder nenn es wie Du willst. Meinen ganzen Loesungsweg anzuschreiben waere tatsaechlich etwas aufwendig, aber ich meinte es eigentlich etwas anders: willst Du sofort meinen gesamten Weg oder ein paar Hinweise, sprich: hast Du grad nichts besseres vor, als Dich totzurechnen?;)
viele Gruesse
SpockGeiger |
Zaph
| | Veröffentlicht am Montag, den 19. Juni, 2000 - 22:05: |
|
Das Fn verschwinden zu lassen ist leicht:
Betrachte
I) Dn+1 - Dn - Dn-1 = Fn+2 ,
II) Dn - Dn-1 - Dn-2 = Fn+1 ,
III) Dn-1 - Dn-2 - Dn-3 = Fn .
Jetzt Gleichung II und III von Gleichung I abziehen und nach Dn+1 auflösen.
Eine kleine Skizze deines Beweises würde mir zunächst reichen. Ich habe ja auch nicht alle Einzelheiten dargelegt. Ich melde mich dann wieder, wenn ich einen Schritt nicht verstehe.
Vielen Dank, Z. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Dienstag, den 20. Juni, 2000 - 18:24: |
|
Hi Zaph
Tut mir leid, hab Dich lange warten lassen. Jetzt die Skizze. Berchne Dn teilrekursiv. Da ich nicht weiss, wie man das wirklich nennt, erklaer ich das nochmal: Du loest die Rekursion ein paar Schritte lang auf, und bekommst ein Gefuehl dafuer, wie eine Formel, die nur aus Fibonnaci-Zahlen besteht, aussehen koennte, die zu beweisen, ist einfache Induktion. Die naechsten Schritte verrate ich Dir weiter unten, also wenn Du Lust hast, mach das erstmal, hast Du heute Deinen Faulen, so scroll mal'n bisschen. Vorsicht: es steht nicht sofort die Loesung da, sondern weitere Schritte skiziert.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Die Formel mit Fibonacci-Zahlen hat irgendwie die Gestalt Sb a Fx*Fy, a,b,x und y verrate ich Dir noch nicht.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Die Formel ist:
Dn = Sn k=0 Fk*Fn-k+2
Setzt Du nun fuer F die expliziten Formeln ein, laesst sich tatsaechlich (ohne besonders grossen Aufwand, hat mich sehr gewundert) die Formel herleiten, die Du ja schon leider hast, deswegen wette ich, diesen Schritt wirst Du nicht mehr durchrechnen.
hoffe, Du hast viel Spass gehabt...
Da wir schon mal bei der Sache sind, weisst Du zufaellig, ob es eine Seite gibt, wo wirklich knifflige Aufgaben zu loesen sind? Vielleicht von Studenten, die Hilfe brauchen?
viele Gruesse
SpockGeiger |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Dienstag, den 20. Juni, 2000 - 20:48: |
|
Hi Zaph
Deine Subtraktionsmethode ist gut, waere ich nicht draufgekommen, Respekt. Allerdings komme ich mit Deinen Folgerungen nicht klar.
Denn aus Dn+4-2Dn+3-3Dn+2-2Dn+1-Dn=0 kann ich folgern:
Dn+2+2Dn+1+Dn=0
Nun weiss ich aber nicht, was mir diese doppelte Nullstelle bei -1 mitteilen moechte. Wie geht es jetzt weiter?
Uebrigens hat mir heute wer gesagt, es gaebe noch eine kuerzere Formel, das spornt uns doch wohl an, oder???
viele Gruesse
SpockGeiger |
Zaph
| | Veröffentlicht am Dienstag, den 20. Juni, 2000 - 23:42: |
|
Hi SpockGeiger,
weiß weder, wie du auf
Dn+4 - 2Dn+3 - 3Dn+2 - 2Dn+1 - Dn = 0,
geschweige denn, wie du von dort aus auf
Dn+2 + 2Dn+1 + Dn = 0
kommst. Verzeih, dass ich zu faul zum formatiern bin, aber dafür ist mir im Moment zu heiß. *schwitz*
Zu deiner Nachricht von überoben bin ich auch noch nicht gekommen. Und die Frage mit der doppelten Nullstelle im anderen Thread ist auch noch offen.
Dazu morgen mehr. Über die kürzere Formel denke ich auch noch mal nach.
Gruß Z. |
Zaph
| | Veröffentlicht am Mittwoch, den 21. Juni, 2000 - 17:58: |
|
Hi again,
auf die merkwürdige Summendarstellung von Dn bist du wirklich durch Probieren gekommen?? Allerhand! Habe versucht aus der Summendarstellung die explizite Darstellung zu bestimmen. Ist ja ziemlich eklig. Ich glaube dir mal, dass es stimmt, schließlich bist du so zur richtigen Formel gelangt. Herzlichen Glückwunsch!! Wie lange hast du denn an der ganzen Aufgabe gesessen?
Einfachere Formel:
Dn = 1/5 [(3 + W(5)) n/2 + 1/W(5)) an + (3 - W(5)) n/2 - 1/W(5)) bn].
Ist aber nicht wesentlich einfacher...
Éine andere Seite mit schwierigeren Aufgaben kenne ich nicht. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 21. Juni, 2000 - 19:08: |
|
Hi Zaph
Ich kann Dir nicht so genau sagen, wie lange ich daran rumgebruetet habe, da sicherlich auch unbewusste Bedenkzeit mit eingeflossen ist, aber ich schaetze, an die 5 Stunden. Hey, Du hast mir immer noch nicht verraten, wie Du von der F-freien Form auf die Formel kommst.
viele Gruesse
SpockGeiger |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 21. Juni, 2000 - 19:10: |
|
Ach ja, ich hab natuerlich einen daemlichen Vorzeichenfehler eingebaut, das, was man wirklich rauskriegt, hat zwei Nullstellen, und zwar die gleichen, wie F, jedoch kommen beide 2-mal vor, und damit kann ich nichts anfangen |
Zaph
| | Veröffentlicht am Donnerstag, den 22. Juni, 2000 - 01:50: |
|
Komme gerade nach Hause, und da das Fernsehprogramm heute abend nichts mehr hergibt, hier noch ein paar Hinweise.
Hast du etwas Ahnung von Vektorräumen und so? Dann könnte ich das folgende etwas plausibler begründen. Hier aber nur das Kochrezept. (Ich mache es etwas ausführlicher, falls es auch andere interessiert.)
Zu einer Rekursionsformel
Dn+k = ak-1Dn+k-1 + ak-2Dn+k-2 + ... + a0Dn
und Anfangswerten
D0 = c0, D1 = c1, ... , Dk-1 = ck-1
ist eine explizite Darstellung von Dn gesucht.
Ansatz: Dn = xn.
(D. h. man hat die Hoffnung, dass es ein x gibt, so dass das die explizite Darstellung ist.)
Wenn das der Fall ist, folgt aus der Rekursionsgleichung
xn+k = ak-1xn+k-1 + ak-2xn+k-2 + ... + a0xn.
Teilt man dies durch xn, so erhält man die "charakteristische Gleichung"
xk = ak-1xk-1 + ak-2xk-2 + ... + a0.
In deinem Beispiel lautet die charakteristische Gleichung somit
x4 = 2x³ + x² - 2x -1.
Wenn ein x gefunden ist, das diese Gleichung erfüllt, haben wir somit eine Folge, die der Rekursionsformel genügt. Im Allgemeinen wird die charakteristische Gleichung k (im Beispiel 4) Lösungen besitzen, also haben wir k Folgen, die der Rekursion genügen. Jetzt kommen aber noch die Anfangswerte erschwerend hinzu. Keine der k Folgen wird uns in der Regel den Gefallen tun, den Anfangswerten zu genügen.
Nun überlege man ich leicht, dass mit k Folgen F(1)n, ... , F(k)n auch eine beliebige Libneakombination dieser Folgen der Rekursionsgleichung genügt:
Dn = r1F(1)n + ... + rkF(k)n.
Setzt man nun für F(i)n die k Folgen, die sich aus der charakteristischen Gleichung ergeben und für n nacheinander die Werte 0, ..., k-1 ein,
so ergibt sich ein Gleichungssystem mit k Gleichungen und k Unbekannten r1, ... , rk, welches immer (!) lösbar ist.
Dieser Trick funktioniert aber nur, wenn die charakteristische Gleichung k verschiedene Lösungen hat. Wenn die Gleichung mehrfache Lösungen hat, muss man sich auf anderem Wege die k "Urlösungen" beschaffen, aus denen dann die endgültige Lösung (die, die auch den Anfangswerten genügt) zusammengebastelt werden kann.
Allgemein gilt: Wenn x eine m-fache Lösung der charakteristischen Gleichung ist, dann sind die Folgen
xn,
nxn,
...
nm-1xn
Lösungen der Rekursionsformel.
In deinem Beispiel sind a und b jeweils doppelte Lösungen der charakteristischen Gleichung. Also lauten die "Urlösungen"
an,
nan,
bn,
nbn,
und die allgemeine Lösung der Rekursionsformel somit
r1an + r2nan + r3bn + r4nan .
Um zu sehen, dass z. B. nxn eine Lösung der Rekursionsformel ist, wenn x eine doppelte Nullstelle der charakteristischen Gleichung ist, betrachte
f(t) = tk - ak-1tk-1 - ak-2tk-2 - ... - a0.
Dann ist f(t) = (t-x)²g(t) für ein Polynom g(t).
Es ist f '(t) = 2(t-x)g(t) + (t-x)²g'(t) = (t-x)h(t) für ein Polynom h(t).
Also f '(x) = 0.
Andererseits ist
f '(x) = kxk-1 - (k-1)ak-1tk-2 - (k-2)ak-2tk-3 - ... - a1.
Nutze dies, um zu zeigen, dass nxn eine Lösung der Rekursionsformel ist.
Hoffe, das war jetzt einigermaßen nachvollziehbar. |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Donnerstag, den 22. Juni, 2000 - 11:50: |
|
Hi Zaph
Bist etwa auch ein Nachtmensch, oder kamst Du gerade von einer Party, und noch nicht muede gewesen? War auf jeden Fall interessant, zu lesen, Du kaemst um 2.50 nach Hause, und da nichts im Fernsehen lief, wuerdest Du die Frage beantworten.
Angeblich habe ich schon 2 Vorlesungen zur linearer ALgebra gehoert, jedoch diese Anwendung nie gemacht. Ich danke Dir fuer die Erklaerung, in erster Linie interessierte mich das Rezept, in den Beweis der Korrektheit muesste ich mich noch vertiefen.
Unter der Aufgabe "Turm von Hanoi mal anders" hat man mir das schon mal erklaert, jedoch kamen darin keine doppelten Nullstellen vor.
nochaml vielen Dank
SpockGeiger |
|
