# Kapitel 13     Der Befehl  "rsolve".
# ========================
> restart;
> ?rsolve
# Der Befehl rsolve ist haupts"achlich f"ur lineare Rekursionen gedacht,
# m"oglichst solche mit konstanten Koeffizienten, doch f"ur sie leistet
# er viel mehr als nur die Bestimmung des Grenzwerts, n"amlich die
# explizite L"osung der Rekursionsgleichung (also die Bestimmung einer
# Funktion von n , die die Rekursion f"ur alle n erf"ullt, und deren
# Verhalten f"ur n gegen unendlich  unseren  Grenzwert liefert). 
# 
# If rsolve is unable to compute a solution, it returns the 
# unevaluated function invocation. This unevaluated rsolve invocation
# may be understood by other functions; for example, the asympt function
# is able to compute an asymptotic series expansion for the solution in
# some cases.
# 
# Beispiel 1):} Ohne Erfolg.
> rsolve({a(n+1) = sqrt(1 + a(n)^2/n), a(1) =1}, a(n));
> asympt(",n);
Error, (in asympt) unable to compute series
# =============================================
# Beispiel 2):} Ohne Erfolg.
> rsolve({b(n+1) = (2*b(n) + 1/b(n)^2)/3, b(0)= 2}, b(n));
> asympt(",n);
Error, (in asympt) unable to compute series
# Die Beispiele aus Kapitel 12 werden von rsolve nicht bew"altigt.
# ============================================
# Beispiel 3): Eine lineare Rekursion mit konstanten 
# Koeffizienten, die durch "rsolve" explizit gel"ost wird.
# -----------------------------------------------------------------
> rsolve({f(0)=0, f(1)=1,f(n)=(f(n-1)+f(n-2))/2}, f(n));
> limit(", n=infinity);
> simplify(");
# =============================================
# Beispiel 4):
# Wenn man beim Aufruf von rsolve als dritte 
# Variable den string "makeproc" (make a procedure) eingibt, erh"alt man
# ein von Maple selbst"andig geschriebenes Programm, das die
# L"osungsfunktion berechnet:
> rsolve({h(0)=0,h(1)=1, h(n)=(h(n-1)+h(n-2))/2}, h(n),'makeproc');
# Dieses Programm sieht sogar den Fall vor, dass  n einen negativen Wert
# hat.
# Die lokale Variable  f  hat hier das Format einer "table", siehe
# "?table".
# Um das Programm benutzen zu k"onnen, m"ussen wir ihm noch einen Namen
# "h" geben:
> h:=":
> seq(evalf(h(i)),i=0..20);
# ===========================================
# Beispiel 5):}
#  Die folgende nichtlineare Rekursion wird zwar nicht explizit, aber
# "asymptotisch" gel"ost durch den Befehl "asympt".
> rsolve({u(n+1)=1/(1+1/u(n)),u(1)=1}, u(n));
> asympt(",n);
# Das bedeutet: Es existieren Konstanten _C , M und n[0] , so dass f"ur
# alle n>=n[0] gilt:
# u(n)-(1/n+_C/n^2+_C^2/n^3+_C^3/n^4)<=M/n^5
# Bildet man nun den Grenzwert n gegen unendlich , so folgt das 
# richtige Ergebnis:
> limit(", n=infinity);
# Warum trat oben der Parameter _C auf ?
# Wiederholt man die Rechnung mit Entwicklungsordnung 10 statt der fest
# eingestellten Ordnung 6 (n"aheres dazu unter "?Order"), so erh"alt
# man: 
> asympt(""",n,10);
# Daraus ist abzulesen, dass u(n) durch folgende Reihenentwicklung
# (geometrische Reihe) dargestellt sein k"onnte ( Hier ist _C ersetzt
# durch C ):
> 1/n + sum(C^k/n^(k+1),k=1..infinity);
# Definiere eine entsprechende Funktion U(n):
> U:= n -> 1/n + C/(n*(-C+n));
# Vermutung: Diese Funktion sollte f"ur beliebigen Wert des Parameters C
# die Rekusion l"osen. Teste dies:
> normal(U(n+1)-1/(1+1/U(n)));
# ----------------------------------------------------------------------
# ----------
# Maple hat zwar die exakte L"osung der Rekursion nicht bestimmen
# k"onnen, hat aber geholfen, sie auf einem Umweg zu finden. Allerdings
# entstand dabei der Eindruck, als ob diese nicht eindeutig bestimmt
# sei. In Wahrheit ist die Konstante C jedoch nur deshalb aufgetaucht,
# weil die Anfangsbedingung offenbar nicht ber"ucksichtigt worden ist.
# Die Forderung U(1)=1 l"asst n"amlich nur C=0 zu. Also haben wir
# U(n)=1/n als exakte L"osung der Rekursion erhalten.
# ============================================
# Ergebnis:
# Die Funktion "asympt" versteht zwar gelegentlich den 
# unausgewerteten output der Funktion "rsolve", 
# doch hat sie daraus offenbar nur die Rekursionsgleichung "ubernommen,
# nicht die Anfangswerte. Ein "ahnlicher Effekt zeigt sich beim
# n"achsten Beispiel.
# ============================================
# Beispiel 6):
# --------------
# Maple findet eine explizite L"osung, ber"ucksichtigt aber die 
# Anfangswerte nicht.
> rsolve({a(0)=1, a(1)=1, (n+1)*a(n+1)-2*n*a(n)+(n-1)*a(n-1)=0},a(n));
> simplify(");
# Definiere eine entsprechende Funktion:
> a:=(n,C)->(1-C+C*n)/n;
# Die unbestimmte Konstante C diente nur dazu,
# die L"osungsgesamtheit bei fehlender Anfangsbedingung zu
# beschreiben. Das zeigt sich bei der folgenden Probe:
> (n+1)*a(n+1,C)-2*n*a(n,C)+(n-1)*a(n-1,C);
> expand(");
# Wie man leicht sieht, sind nur f"ur C=1 die 
# Anfangsbedingungen erf"ullt, allerdings f"ur n=0 nur als Grenzwert:
> limit(a(t,C),t=0);
> ?limit
> limit(a(t,C),t=0,right);
> limit(a(t,1),t=0);
# d.h. die L"osung ist gegeben durch die konstante Folge a(n)=1 f"ur
# alle n=0,1,2,... . Das Problem scheint f"ur Maple darin zu bestehen,
# dass die
# erhaltene L"osung f"ur C<>1  im Nullpunkt singul"ar ist.
# In der Tat findet Maple bei der folgenden Variante der Aufgabe
# die L"osung ohne Probleme:
> a:='a';
> rsolve({a(1)=1, a(2)=1/2, (n+1)*a(n+1)-2*n*a(n)+(n-1)*a(n-1)=0},
> a(n));
> simplify(");
# ============================================
# Beispiel 7): Hier existiert der Grenzwert nicht.
# --------------------------------------------------------
> rsolve({a(1) = 1, a(2) = 2, a(n+2) +
> 2*a(n+1) + a(n) = 0}, a(n));
> limit(",n=infinity);
>