Eine fiese Rekursion < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Vor einiger Zeit sollte ich für ein Seminar die eine Funktionalgleichung lösen. Den Schein für das Seminar habe ich zwar nun schon längst, aber die eine Gleichung ist noch offen. Sie lautet:
Gesucht: f:N->N, f(n+1)=n-f(f(n))
(N = nat. Zahlen MIT 0)
Ich konnte noch zeigen, daß f(1)=0 sein muß, und daß es genau zwei Lösungen gibt, die von der Wahl von f(0) [mm] \in [/mm] {0,1} abhängen. Mehr aber auch nicht.
Was ich mir wünsche, ist eine explizite Auflösung der Rekursion für beide Wahlen von f(0).
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 09:13 Mi 05.01.2005 | | Autor: | Paulus |
Hallo holy_diver_80
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Ich glaube nicht, dass es da 2 Lösungen geben kann!
f(n) muss ja [mm] $\ge [/mm] 0$ sein!
Wenn man die Rekursionsvorschrift ein Wenig umstellt, sieht sie so aus:
$f(n)+f(n+1)=n_$
Dies gibt nacheinander:
$f(0)+f(1)=0_$
$f(1)+f(2)=1_$
$f(2)+f(3)=2_$
$f(3)+f(4)=3_$
$f(4)+f(5)=4_$
$f(5)+f(6)=5_$
$f(6)+f(7)=6_$
$f(7)+f(8)=7_$
$f(8)+f(9)=8_$
...
...
Jetzt kannst du das ganz einfach von oben nach unten auflösen, und zwar immer eindeutug:
$f(0)+f(1)=0 [mm] \Rightarrow f(0)=0;\, [/mm] f(1)=0$
weil ja sowohl f(0) und f(1) nicht negativ sein können. Wenn ihre Summe 0 sein soll, müssen beide =0 sein!
Die 2. Gleichung ergibt dann $f(2)=1_$
Die 3. Gleichung ergibt dann $f(3)=1_$
Die 4. Gleichung ergibt dann $f(4)=2_$
Die 5. Gleichung ergibt dann $f(5)=2_$
Die 6. Gleichung ergibt dann $f(6)=3_$
Die 7. Gleichung ergibt dann $f(7)=3_$
Die 8. Gleichung ergibt dann $f(8)=4_$
Die 9. Gleichung ergibt dann $f(9)=4_$
...
...
Mir scheint, dass die Folge dann so aussehen müsste:
$(0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,...)_$ 
Mit lieben Grüssen
Paul
|
|
|
| |
|
Zunächst einmal: Es hieß
f(n+1)=n-f(f(n))
und nicht
f(n+1)=n-f(n).
Das wäre ja wirklich leicht.
Dann möchte ich noch mitteilen, was ich bis jetzt dazu zeigen konnte:
- f(1)=0: Setze n=0 => f(1)=f(0+1)=0-f(f(0)). Da ran(f)=N, bleibt nur f(1)=f(f(0))=0.
- f(0) [mm] \in [/mm] {0,1}: Wäre f(0) [mm] \ge [/mm] 2, so wäre für n=1:
f(2)=f(1+1)=1-f(f(1))=1-f(0)<0 Widerspruch zu ran(f)=N.
Also ist f(0) [mm] \in [/mm] {0,1}
- Für jede Wahl von f(0) [mm] \in [/mm] {0,1} kann man mit obiger Vorschrift eine Funktion f:N->N konstruieren.
Dazu ausreichend z.z.: Für alle n [mm] \ge1 [/mm] gilt: Für alle m, 1 [mm] \le [/mm] m [mm] \le [/mm] n ist 0 [mm] \le [/mm] f(m) [mm] \le [/mm] n-1.
Bew: n=1: f(0)=0,1, 0 [mm] \le [/mm] 0=f(1) [mm] \le [/mm] 0.
n->n+1: Für 0 [mm] \le [/mm] m [mm] \le [/mm] n nichts zu zeigen. Sei nun m=n+1
f(m)=f(n+1)=n-f(f(n))= (IV) =n-f(k) (für ein k, 0 [mm] \le [/mm] k [mm] \le [/mm] n) =
= (IV) = n-l (für ein l, 0 [mm] \le [/mm] l [mm] \le [/mm] n)
Daher auch 0 [mm] \le [/mm] f(n+1) [mm] \le [/mm] n.
Es gibt also 2 Lösungen, die von der Wahl von f(0) abhängen, und man kann diese Lösungen rekursiv berechnen. Kann man diese Rekursion aber auch auflösen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:59 Mi 05.01.2005 | | Autor: | moudi |
Ich habe mal die ersten 100 Funktionswerte berechnet. Tja sieht nicht gut aus. Nach meiner Meinung zeigen die Funktionswerte in beiden Fällen chaotisches Verhalten. Im ersten Fall f(0)=0 scheint die Funktion monoton wachsend zu sein. Es gilt (habe es aber nicht bewiesen), dass zwei aufeinanderfolgende Funktionswerte gleich sind, oder sich um 1 unterscheiden:
f(n+1)=f(n) oder f(n+1)=f(n)+1
gilt f(n+1)=f(n), dann ist f(n+2)=f(n+1)+1
Es sind höchstens zwei aufeinanderfolgende Funktionswerte gleich.
gilt f(n+1)=f(n)+1 und f(n+2)=f(n+1)+1, dann ist f(n+3)=f(n+2)
Es steigt höchstens zweimal nacheinander um 1.
Trotzdem ergibt sich kein regelmässiges Muster.
Falls f(0)=1 scheint das Verhalten noch chaotischer zu sein. Es würde mich wundern, wenn es einfache explizite Formeln gäbe.
mfG Moudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:48 Mi 05.01.2005 | | Autor: | Paulus |
Hallo holy_diver_80
> Zunächst einmal: Es hieß
> f(n+1)=n-f(f(n))
> und nicht
> f(n+1)=n-f(n).
Ja, genau deshalb habe ich die Antwort auch sogleich wieder zurückgenommen. Da sie bereits gelesen worden war, wollte ich sie nicht einfach löschen! Und ein Bisschen öffentliche Blamage gehört ja auch dazu. Andere müssen ja auch sehen, dass sie nicht die einzigen sind, die Fehler machen! 
Ich habe, ähnlich wie Moudi, ca. 150 Folgeglieder berechnet, respektive die Aenderungen von Glied zu Glied.
Zuerst dachte ich, bei f(0)=0 ergäbe sich, nach den ersten 2 Gliedern, eine Periode der Länge 21. Aber nach ein Paar Wiederholungen hatte sich wieder ein Schwarzes Schaf in die Folge geschlichen.
Das Gleiche Lied mit f(0)=1, einfach mit einer Periodenlänge 24.
Ich glaube mittlerweile auch, wie Moudi, dass sich die Glieder dieser rekursiv recht einfach aussehenden Folge, nicht in einer geschlossenen Formel erhaschen lassen!
Also wirklich ein chaotisches Verhalten! Offensichtlich bin ich nicht der einzige Chaot auf dieser Welt!
Mit lieben Grüssen
Paul
|
|
|
| |
|
Hallo holy_diver_80,
Ich hab' mir jetzt ein wenig Zeit genommen, und ein Delphi-Programm geschrieben, daß dir Folgeglieder deiner rekursiven Folge berechnen kann.
Die erste Ausgabe sind die Folgeglieder in einem Format, welches von Derive als Tabelle akzeptiert wird. (Ist jetzt vermutlich nur für mich nützlich. ) Die zweite Ausgabe in der Datei sind einfach nur die Folgeglieder durch Kommas getrennt.
Das Programm (ist unten beigefügt) benutzt eine linear verkettete Liste, um Folgeglieder, die es bereits berechnet hat, abzuspeichern, um sie beim Berechnen neuer Folge-Werte nicht nochmal berechnen zu müssen. Die alten Werte, werden dann einfach aus der Liste entnommen, wodurch sich die Rekursionstiefe beim Berechnen drastisch reduziert. (Auf meinem Pentium II 300 MHZ war es beim Berechnen von 300 Werten immerhin eine Verbesserung von mehreren Minuten auf ein Paar Sekunden!).
Das einzige Problem dabei ist, daß die Liste der Werte unaufhörlich wächst, je mehr Werte man haben will. Bei 10000 Werten hat mein System bereits mehr als 100 MB Auslagerungsspeicher auf der Festplatte verschlungen (so groß wurde am Ende die Liste). Leider wüßte ich nicht, wie man die Liste verkleinern könnte, ohne das die Rekursionstiefe wieder steigt. Eventuell könnte man zwei Zählvariablen in die FOR-Schleife in myf0() einbauen, die Zählen, wie oft die Schleife bei jedem zu berechnenden Wert aufgerufen wird, und das Maximum bzw. Minimum der Anzahl der Aufrufe betrachten und diese als separate Folge in eine Datei speichern. Ich habe nämlich das Gefühl, daß die Liste nie wirklich "tief" durchlaufen wird. Am Ende ist es vielleicht so, wie mit der iterativen Berechnung der Fibbonacci-Zahlen. Dort gibt es auch einen sehr schnellen iterativen Algorithmus, der immer von den letzten berechneten Folgewerten ausgeht. Eventuell könnte man die FOR-Schleife dann viel weiter vereinfachen und die Liste vollständig entfernen.
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: zip) [nicht öffentlich]
|
|
|
| |
|
Ich habe ein wenig im Netz recherchiert, und bin auf die folgende, sehr ähnliche Gleichung gestoßen
f(n)=n-f(f(n-1)) f(0)=1
Diese hat die Lösung f(n)=floor(c*(n+1)) mit [mm] c=\bruch{-1+\wurzel{5}}{2}
[/mm]
http://www.math.rutgers.edu/~clong/mensa/solutions.html
Ich vermute nun, daß meine Gleichung für den Fall f(0)=0 eine ähnliche Form hat, etwa
f(n)=floor(c*(n+d)) mit einem noch zu bestimmenden d.
Ich habe ein wenig herumexperimentiert, und herausgefunden, daß das d irgendwo bei 0,24 liegen müßte.
Kann mir jemand bei der Bestimmung dieses d's helfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:22 Mi 12.01.2005 | | Autor: | moudi |
Hallo holy_diver
Danke für den Typ (Link).
@Karl_Pech Es hat einen Fehler, denn holy_diver meinte natürlich [mm] $f(n)=\mathrm{floor}(c*n+d)$. [/mm] Bitte korrigieren, wenn meine Verumutung nicht stimmt.
Im Link geht es um die Aufgabe, eine explizite Lösung der Rekursion
[mm] $f(n+1)=n+1-f(f(n))\quad [/mm] f(0)=0$ zu finden.
(Lösung [mm] $f(n)=[(n+1)\cdot [/mm] c]$ mit [mm] $c=\bruch{-1+\wurzel{5}}{2}$
[/mm]
Ich hab ein bisschen umgeschrieben, um besser vergleichen zu können.)
Die zu untersuchende Funktion [mm] $f^\ast$ [/mm] hat die Rekursionsgleichung
[mm] $f^\ast(n+1)=n-f^\ast(f^\ast(n))\quad f^\ast(0)=0$.
[/mm]
Ich hab die Funktionswerte der beiden Funktionen miteinander verglichen und bin schnell darauf gekommen, dass [mm] f^\ast(n)=f(n+1)-1 [/mm] sein könnte.
Man muss den Anfangswert prüfen (kein Problem) und die Rekursionseigenschaft.
Man erhält :
[mm]f^\ast(n+1)=f(n+2)-1=n+2-f(f(n+1))-1=n+1-f(f^\ast(n)+1)=n+1-\Bigl(f^\ast(f^\ast(n))+1\Bigr)= n-f^\ast(f^\ast(n))[/mm] QED
Setzt man jetzt die Explizite Lösung ein, so erhält man
[mm] $f^\ast(n)=[(n+2)c]-1=[(n+2)c-1]=[nc+(2c-1)]$. [/mm] Dein d ist also [mm] $d=(2c-1)=\sqrt5-2=0.236$.
[/mm]
mfG Moudi
|
|
|
|
