Autor |
Beitrag |
Lars Weiser
| Veröffentlicht am Montag, den 09. April, 2001 - 10:23: |
|
Hallo Leute, ich habe ein Problem: vor einiger Zeit bin ich beim Stöbern in der Bibliothek auf eine interessante Zahlenfolge gestoßen, die wie folgt definiert ist: Q:IN -> IN mit Q(n):=1, für n<3 Q(n):=Q(n-Q(n-1))+Q(n-Q(n-2)), sonst Ich habe abends die ersten 1000 Glieder der Folge (mit Hilfe des Computers) berechnet und bin zu der Vermutung gekommen, daß Q(n)<=n, für alle n aus IN gilt - doch habe ich Probleme bei der Beweisführung, denn mittels Induktion gilt: I.A.: Q(1)=1 (nach Def.) also 1<=1 (w) Q(2)=1 (nach Def.) also 1<=2 (w) I.V.: Q(n)<=n, Q(n+1)<=n+1, für fixes n aus IN I.S.: Q(n+2)=... (und wie geht's weiter ???) Gibt es zudem auch einen expliziten Ausdruck für Q(n) ??? Wäre schön, wenn mir jemand dabei helfen könnte! Ciao Lars ;-) |
Marcel
| Veröffentlicht am Freitag, den 20. April, 2001 - 11:16: |
|
Die Frage die sich bei meinen Überlegungen dabei ergibt, ob du so einfach unter >I.V.: >Q(n)<=n; Q(n+1)<=n+1 deine Vermutung als Induktionsschritt einbauen kannst? (oder habe ich I.V. missverstanden???) Folglicherweise müsstest du nach dem Beweis für das erste Glied (Q(1)=1<=1 (w)) erstmal den Induktionsschritt (Q(n)<=n (w?)) ausführen... Denn wenn du diesen bewiesen hast gilt nach dem Prinzip des Beweises durch Induktion auch Q(n+1)<=n+1 und Q(n+2)<=n+2 Berichtige mich bitte jemand, falls ich völlig auf dem Holzwege bin :-/ |
Carmichael (Carmichael)
| Veröffentlicht am Freitag, den 20. April, 2001 - 14:16: |
|
mit Induktion in "einfacher" Form denk ich kommt man hier nicht weiter. Hatte mal folgenden Ansatz gemacht: n/a < Q(n) < n/ka => (n+1)/a < Q(n+1) < (n+1)/ka; lässt nicht mit voll. Ind. beweisen, egal für welches a,k gleiches dürfte für f(n) < Q(n) < g(n) => f(n+1) < Q(n+1) < g(n+1) gelten |
Matroid (Matroid)
| Veröffentlicht am Freitag, den 20. April, 2001 - 22:56: |
|
Ich kenne diese Folge nicht, aber wenn sie wohldefiniert ist, dann MUSS Q(n)<n (für n>1) sein. wäre das nicht der Fall, dann wäre irgendwann die Rekursion nicht mehr definiert. Bedenke: man muß Q(n-Q(n-1)) berechnen - und die Folge ist für neN definiert. Was wäre wenn Q(n-1) größer oder gleich n wäre! Der Sinn dieser Folge liegt sicher nicht darin Q(n)<n zu zeigen, denn das ist schon notwendig, damit es diese Folge überhaupt geben kann. Man muß sich natütlich überlegen, ob die Folge wohldefiniert ist. Aber dann ist Q(n)<n (für n>1) nur eine Voraussetzung für die Definition der Folge. Die Rekursionsgleichung darf man nur so aufstellen, wenn das gilt. Folglich kann mit mittels Induktion aus der Rekursionsgleichung nicht auf Q(n)<n (für n>1) schließen. Was ist das? Eine Art Fraktal aus natürlichen Zahlen? Gruß Matroid |
Carmichael (Carmichael)
| Veröffentlicht am Freitag, den 20. April, 2001 - 23:54: |
|
hm, naja, dass Induktion hier nichts bringt, ist nicht völlig klar! Es könnte durchaus sein, dass sich die "Wohldefiniertheit" der Folge induktiv zeigen lässt. Dazu kann es durchaus "legitim" sein, dass man einen rekursiven Ansatz macht. (triviales Beispiel: a(n+1) = 1/a(n); a(1) = 1;) aber das ist Formalismus........ |
Matroid (Matroid)
| Veröffentlicht am Samstag, den 21. April, 2001 - 20:36: |
|
Hi Carmichael, Du hast recht. Man muß aber irgendetwas wesentlicheres als Q(n)<=n bei der Induktion zeigen. Wenn die Behauptung zu schwach ist, dann kann sie beim Induktionsschritt kein Argument sein. Ich habe mich ein wenig an der Aufgabe festgebissen, habe aber immer noch keine tollen Ergebnisse, nur einige Vermutungen. Ich stelle daher zur Belebung der Diskussion folgende Behauptung auf: n/2 <= Q(n) < n, für n>2 Induktionsanfang: n=3, n=4 ok Induktionsschritt (n>2): Q(n+1) = Q(n+1-Q(n)) + Q(n+1-Q(n-1)) n+1-Q(n) bzw. n+1-Q(n-1) möchte ich jetzt unter Anwendung der Induktionsvoraussetzung nach oben abgeschätzen. Dafür unterscheide ich die Fälle: A) n gerade B) n ungerade Zu A) Wenn n gerade, dann ist n-1 ungerade und aus Q(n-1)>=(n-1)/2 folgt sogar Q(n-1)>=n/2, denn Q(n) ist eine Folge natürlicher Zahlen. Darum ist 1 <= n+1-Q(n) <= n+1 - n/2 = n/2 + 1 und 2 <= n+1-Q(n-1) <= n+1 - n/2 = n/2 + 1 Betrachte nun Q(n+1-Q(n)). Den Ausdruck in der Klammer haben ich abgeschätzt, er liegt zwischen 1 und n/2+1. Deshalb kann man sagen: Q(n+1-Q(n)) hat einen Wert aus folgender Menge hat { Q(k) | 1<=k<= n/2+1 } Betrachte nun Q(n+1-Q(n-1)). Den Ausdruck in der Klammer haben ich abgeschätzt, er liegt zwischen 2 und n/2+1. Deshalb kann man sagen: Q(n+1-Q(n-1)) hat einen Wert aus folgender Menge hat { Q(k) | 2<=k<= n/2+1 }. Wir wissen nichts über die Monotonie der Folge. Aber egal welches der Wert ist, er ist kleiner als n/2+1 oder kleiner gleich n/2, denn das sagt die Induktionsvoraussetzung, weil für n>2 immer n/2+1<n ist. Darum ist Q(n+1) = Q(n+1-Q(n)) + Q(n+1-Q(n-1)) <= n/2 + n/2 = n. Und darum: Q(n+1) < n+1. Nun ist weiter zu zeigen, daß Q(n+1) >= (n+1)/2. Q(n+1) = Q(n+1-Q(n)) + Q(n+1-Q(n-1)) >= (n+1-Q(n)) / 2 + (n+1-Q(n-1)) / 2 nach Induktionsvoraussetzung, denn n+1-Q(n) ist kleiner als n+1, weil Q(n) mindestens 1 ist (s.o.). = n+1- Q(n)/2 - Q(n-1)/2 ????????????????? Und da geht's nicht weiter ... Ich muß jetzt die Abschätzung nach oben benutzen, und die bringt nichts. Ja, wenn die Abschätzung nach oben strenger wäre, dann vielleicht. Ich schaue mir die Folge an, und stelle fest, daß Q(n)<n für wachsende n immer ungenauer ist. Welches ist denn eine mögliche stärkere Abschätzung ?? Meine weiteren Vermutungen sind: *) Q(n)/n konvergiert gegen (1+w(5))/2 = 1.61... Denn einige ausgerechnete Quotienten passen zu der Vermutung. Und die Folge hat vielleicht etwas mit Fibonacci zu tun, nur eben ein Fibonacci mit Rückkopplung. So weit bin ich. Nun soll sich das bitte mal jemand ansehen. Gruß Matroid |
holger
| Veröffentlicht am Sonntag, den 22. April, 2001 - 17:06: |
|
Was wollt ihr eigentlich beweisen? Das die Folge für alle n wohldefiniert ist, also für alle n terminiert?<br> Das kann doch unmöglich so schwer sein.<br> Wenn Q(n) nach I.V. terminiert, dann doch auch Q(n-a) (a in N). <br> Demnach terminiert auch Q(n+1) <br> Nach I.V gilt n >= Q(n) also auch n + 1 >= Q(n) und ebenso n + 1 >= Q(n - 1).<br> Was soll denn da schief gehen? <br> Es gibt in Q(n+1) also keine Q(x) mit x > n oder x < 1. <br> Und aus Q(n) terminiert sollte man dann auch Q(n) <= n folgern können.<br> Wahrscheinlich sehe ich das viel zu einfach...<br> -holger |
Matroid (Matroid)
| Veröffentlicht am Sonntag, den 22. April, 2001 - 18:38: |
|
Hallo Holger, ich sehe es aber nicht. Du schreibst
Quote:Wenn Q(n) nach I.V. terminiert, dann doch auch Q(n-a) (a in N).
Aber da kommt ein aeN vor und Q(n-a) ist nur ok, wenn a<n. Ja, wenn man zusätzlich definieren würde, daß Q(z)=0 für z<=0, dann wäre erst mal die Definition der Folge immer gegeben. Das wäre vielleicht für den Anfang eine sinnvolle Ergänzung. Dann hat man aber noch überhaupt keine Erkenntnisse über die Folge. Noch nicht einmal, daß Q(n)<n. Was wir zunächst mal haben sollten, wäre ein oder mehrere Aufgabenstellungen, was denn für die Folge gelten könnte. Gruß Matroid |
Lars Weiser
| Veröffentlicht am Dienstag, den 24. April, 2001 - 11:05: |
|
Hallo Leute, 1. zu Marcel: du hast zwei Rekursionsanker und demzufolge auch zwei Induktionsvoraussetzungen !!! 2. Die Frage bleibt offen, ob Q(n) überhaupt 'wohldefiniert' ist (im Buch gab es keinerlei Hinweise dazu - ebenso die Frage, ob Q(n) überhaupt für alle n berechenbar ist, ist auch nicht ganz klar, oder ?) Über die Abschätzung Q(n)<=n/2 habe ich mir auch schon den Kopf zerbrochen ;-) |
Lars Weiser
| Veröffentlicht am Dienstag, den 24. April, 2001 - 11:10: |
|
Natürlich muß es Q(n)>=n/2 heißen (*ARRGHHH*) |
Matroid (Matroid)
| Veröffentlicht am Dienstag, den 24. April, 2001 - 18:05: |
|
Hallo Lars, Du hast doch die ersten 1000 Werte berechnet. Meinst Du lim Q(n)/n = (w(5)-1)/2 kann stimmen? Gruß Matroid |
Matroid (Matroid)
| Veröffentlicht am Sonntag, den 29. April, 2001 - 21:04: |
|
In "Gödel, Escher, Bach" von Douglas Hochstadter wird diese Folge im Kapitel 5 beschrieben unter der Überschrift "Eine chaotische Folge". Hofstadter gibt selbst keine Interpretation oder Bedeutung an. Da steht: "Die Folge ist [...] absonderlich. Je weiter man geht, desto weniger Sinn scheint sie zu haben." Eine explizite Berechnung ist nicht gegeben. Hochstadter schließt aber nicht aus, daß eine gefunden wird: "[...] wenn man Glück hat [...]". Ich habe die Folge mal bis n=200.000 ausgerechnet. Es tanzt Q(n) immer um n/2. Die Werte von Q(n) werden anscheinend genauso oft größer wie nicht größer im Verlauf der Rekursion. Hat schon mal jemand einen Interpretationsvorschlag gesehen oder gehört? Ist ja immerhin ein Wachstumsprozeß. Aber wenn es was reales wäre, dann hätte Hochstadter das wohl schon selbst beschrieben. Also lassen wir das. Gruß Matroid |
Matroid (Matroid)
| Veröffentlicht am Montag, den 30. April, 2001 - 15:35: |
|
Ich habe ein Programm ins Netz gestellt, mit dem man die ersten 2000 Folgenwerte berechnen kann (in Blöcken zu je 100). Hier zu finden: http://matheplanet.de/ unter "Was bedeutet die Hofstadter-Folge". Wer hilft bei der Diskussion? |
|