Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Kuriose Zahlenfolge...

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Universitäts-Niveau » Zahlentheorie » Kuriose Zahlenfolge... « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Lars Weiser
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 09. April, 2001 - 10:23:   Beitrag drucken

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 ;-)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Marcel
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 20. April, 2001 - 11:16:   Beitrag drucken

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 :-/
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Carmichael (Carmichael)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 20. April, 2001 - 14:16:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 20. April, 2001 - 22:56:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Carmichael (Carmichael)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Freitag, den 20. April, 2001 - 23:54:   Beitrag drucken

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........
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Samstag, den 21. April, 2001 - 20:36:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

holger
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 22. April, 2001 - 17:06:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 22. April, 2001 - 18:38:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Lars Weiser
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 24. April, 2001 - 11:05:   Beitrag drucken

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 ;-)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Lars Weiser
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 24. April, 2001 - 11:10:   Beitrag drucken

Natürlich muß es Q(n)>=n/2 heißen (*ARRGHHH*)
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Dienstag, den 24. April, 2001 - 18:05:   Beitrag drucken

Hallo Lars,
Du hast doch die ersten 1000 Werte berechnet.
Meinst Du lim Q(n)/n = (w(5)-1)/2 kann stimmen?
Gruß
Matroid
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Sonntag, den 29. April, 2001 - 21:04:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Montag, den 30. April, 2001 - 15:35:   Beitrag drucken

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?

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.

ad

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page