Grenzwert einer rekursiven Folge
Von: Wauzi
Datum: Mi. 30. August 2006 15:17:10
Thema: Mathematik

Grenzwert einer rekursiven Folge

Dieser Artikel ist entstanden als Antwort auf ein Problem von spitzwegerich, das hier behandelt wurde. Die Ausgangssituation ist fast banal, der Grenzwert auf den ersten Blick verblüffend und die verwendeten Methoden leicht nachvollziehbar. array(Problemstellung:)__ Die Folge (a(n))_(n\el\ \IN_0) ist definiert durch: | |\blue a(0)=1 | |\blue a(1)=0 | |\blue a(n+1)=a(n)+a(n-1)/((2n-1)*(2n+1)) für alle n\el \IN | | Dann gilt: | |\red lim(n->\inf,a(n))=1/e \big\Ein paar wenige Grundkenntnisse, die im Folgenden vorausgesetzt werden, gebe ich hier kurz an: (1) Das \blue\O\-Symbol\black und die Schreibweise << | |Sind f und g Funktionen \IN->\IC, so bedeutet | |f(n)=O(g(n)): | |Es gibt eine Konstante K>0 und ein N\el\ \IN^\+ so daß | |abs(f(n))<=K*abs(g(n)) \forall\ n>=N | |Alternativ dafür kann man auch schreiben: | |f(n)< f(n)-h(n)=O(g(n)) | |Geht g(n)/(f(n)-h(n)) gegen 0, so schreibt man auch: | |f(n)~h(n) (2) Der allgemeine Binomialkoeffizient | |\blue (\alpha;n)\black\:=1/n!*produkt((\alpha-k),k=0,n-1) für n\el\ \IN_0 und \alpha \el\ \IR (3) Die \blue\erzeugende Funktion | |Gibt es zur Folge (a(n))_(n\el\ \IN) eine Funktion f, deren Potenzreihenentwicklung | |die Form | |f(x)=sum(a(k)/k!*x^k,k=0,\inf ) | |bei positivem Konvergenzradius hat, so heißt f die | |erzeugende Funktion zur Folge (a(n))_(n\el\ \IN) | |Es gilt dann: | |a(n)=f^(n)(0) (4) Die \blue\Stirlingsche Formel\black\ (ohne Beweis) | |n! =n^n/e^n*sqrt(2\pi*n)*(1+O(1/n))
 
\big\Der naheliegende Weg wäre jetzt, die erzeugende Funktion unserer Folge zu finden. Allerdings ist dies überraschend schwierig, da sich der auftretende Nenner als äußerst unangenehm erweist. Den Ausweg findet man in einer Transformation, die zu einer einfacheren Folge führt. array(Definition:)__ | | b(n):=a(n)*(2n)!/(2^n*n!) array(\blue\Hilfssatz 1:)__ | | b(0)=1 | |\blue b(1)=0 | |\blue b(n+1)=(2n+1)*b(n)+b(n-1) | |für n>=2 array(Beweis:)__ | |Ergibt sich sofort durch Einsetzen \big\Jetzt gilt es, für diese neue Folge die erzeugende Funktion zu finden. Da jetzt der unangenehme Bruch nicht mehr auftritt, ist dies recht einfach. array(\blue\Hilfssatz 2:)__ | |Die Folge (a(n))_(n\el\ \IN) ist konvergent. array(Beweis:)__ | |Die Folge (a(n))_(n\el\ \IN) ist offensichtlich monoton wachsend. | |=>a(n+1)=a(n)+a(n-1)/((2n+1)*(2n-1))<=a(n)*4n^2/(4n^2-1) | |=>a(n+1)<=a(2)*produkt(4k^2/(4k^2-1),k=2,n) | |Es ist log(produkt(4k^2/(4k^2-1),k=2,n))=log(produkt(1+1/(4k^2-1),k=2,n))= | |=summe(log(1+1/(4k^2-1)),k=2,n)<=summe(1/(4k^2-1),k=2,n)<=summe(1/(4k^2-1),k=2,\inf )<\inf | |Damit ist die Folge monoton und beschränkt, also konvergent. | |qed. array(\blue\Hilfssatz 3:)__ | |Die Potenzreihe sum(b(k)/k!*x^k,k=0,\inf ) hat positiven Konvergenzradius array(Beweis:)__ | |b(k)/k! =a(k)*(2^k*k!)/(k!*(2k)!)<<2^k/(2k)! array(\red\Satz 1:)__ | |Für die erzeugende Funktion f der Folge (b(n))_(n\el\ \IN) gilt: | | \red f(x)=1/e*e^(sqrt(1-2x))/sqrt(1-2x) für 0<=x<1/2 array(Beweis:)__ | |Nach Hilfssatz 3 ist der Konvergenzradius positiv. | |Es ist 0=sum(b(k+1)/k!*x^k,k=1,\inf )-sum(((2k+1)*b(k))/k!*x^k,k=1,\inf )-sum(b(k-1)/k!*x^k,k=1,\inf )= | |= S_1(x)-S_2(x)-S_3(x) | |S_1(x)=(sum(b(k+1)/(k+1)!*x^(k+1),k=1,\inf ))'=(sum(b(k)/k!*x^k,k=2,\inf ))'=# | |=(sum(b(k)/k!*x^k,k=0,\inf )-1)'=(f(x)-1)'=f'(x) | |S_2(x)=sum((2k+1)*b(k)/k!*x^k,k=1,\inf )=2*sum((k*b(k))/k!*x^k,k=1,\inf )+sum(b(k)/k!*x^k,k=1,\inf )= | |=2*S_4(x)+f(x)-1 | |S_4(x)=sum(b(k)/(k-1)!*x^k,k=1,\inf )=x*sum(b(k)/(k-1)!*x^(k-1),k=1,\inf )= | |=x*(sum(b(k)/k!*x^k,k=1,\inf ))'=x*(f(x)-1)'=x*f'(x) | |=>S_2(x)=2x*f'(x)+f(x)-1 | |S'_3(x)=(sum(b(k-1)/k!*x^k,k=1,\inf ))'=sum(b(k-1)/(k-1)!*x^(k-1),k=1,\inf )=sum(b(k)/k!*x^k,k=0,\inf )=f(x) | |Wir betrachten wieder die Ausgangslage:| |0= S_1(x)-S_2(x)-S_3(x) | |=>0=f'(x)-(2x*f'(x)+f(x)-1)-S_3(x)= | |=(1-2x)*f'(x)-f(x)+1-S_3(x) | |Nochmaliges Ableiten führt zu | |0=(1-2x)*f''(x)-2f'(x)-f'(x)-S'_3(x)= | |=(1-2x)*f''(x)-3f'(x)-f(x) | |Damit ist die DGl (1-2x)*y''-3y'-y=0 zu lösen. | |Die angegebene Funktion erfüllt die DGl und auch die beiden | |Anfangswerte b(0)=1 und b(1)=0 wie man nachrechnet. | |qed. \big\Jetzt braucht man nur noch die n-ten Ableitungen an der Stelle x=0 zu berechnen und man hat die b(n) und damit auch a(n). Aber ganz so einfach ist das nicht. Die Ableitungen erweisen sich als ziemlich harte Nuß, so daß ein kleiner Trick erfolgversprechender ist. array(\blue\Hilfssatz 4:)__ | |\blue\Sei g(x):=sqrt(1-2x). Dann ist | |\blue\ exp(g(x))/g(x)=1/g(x)+sum(g(x)^k/(k+1)!,k=0,\inf ) array(Beweis:)__ | |Ergibt sich sofort durch Einsetzen in die Exp-Reihe array(\blue\Hilfssatz 5:)__| |\blue\Sei wieder g(x)=sqrt(1-2x). Dann ist | |\blue\ exp(g(x))/g(x)=1/g(x)+sum(x^k*(-2)^k*sum((t/2;k)*1/(t+1)!,t=0,\inf ),k=0,\inf ) array(Beweis:)__ | |g(x)^k=(1-2x)^(k/2) | |=>g(x)^k=sum((k/2;t)*(-2x)^t,t=0,\inf ) | |Hilfssatz 5 =>exp(g(x))/g(x)=1/g(x)+sum(1/(k+1)!\.sum((k/2;t)*(-2x)^t,t=0,\inf ),k=0,\inf )= | |Absolute Konvergenz erlaubt Reihenvertauschung: | |=1/g(x)+sum(x^t*(-2)^t*sum((k/2;t)*1/(k+1)!,k=0,\inf ),t=0,\inf ) array(\blue\Hilfssatz 6:)__| |(1/sqrt(1-2x))^(n)=(2n)!/(2^n*n!)*(1-2x)^(-1/2-n) array(Beweis:)__ | |klar für n=0 | |((2n)!/(2^n*n!)*(1-2x)^(-1/2-n))^'=(2n)!/(2^n*n!)*(2n+1)*(1-2x)^(-1/2-(n+1))= | |=(2n)!/(2^n*n!)*(2n+1)*(2n+2)/(2*(n+1))*(1-2x)^(-1/2-(n+1)) array(\blue\Hilfssatz 7:)__| | Für die n-te Ableitung dieser Funktion gilt: | |\blue ((exp(g(x))/g(x))^(n))_(x=0)=(2n)!/(2^n*n!)+n!*(-2)^n*sum((t/2;n)*1/(t+1)!,t=0,\inf ) array(Beweis:)__ | |Dies folgt sofort aus Hilfssatz 6 und der gleichmäßigen | |Konvergenz der Potenzreihe.
 
\big\Die Vorarbeiten sind geschafft. Jetzt läßt sich a(n) explizit angeben. Dazu verwenden wir Hilfssatz 7. Diese Darstellung ist zwar zum Berechnen der Folgeglieder nicht allzu brauchbar, leistet aber gute Dienste bei der Ermittlung des Grenzwerts. array(\red\Satz 2:)__ | |a(n)=1/e+O(((n!)^2*2^2n)/(2n)!*sum(abs((t/2;n))*1/(t+1)!,t=0,\inf )) array(Beweis:)__ | |Es ist b(n)=(1/e*e^(sqrt(1-2x))/sqrt(1-2x))^(n) an der Stelle x=0. | |Dies in Verbindung mit der Definition der b(n) und | |Hilfssatz 7 ergibt sofort die Behauptung array(\blue\Hilfssatz 8:)__ | | 2^2n*(n!)^2/(2n)! =O(sqrt(n)) array(Beweis:)__ | |Wir verwenden mehrfach die Stirlingsche Formel in etwas abgewandelter | |Form: | |n! =n^n/e^n*sqrt(2\pi\.n)*(1+h_1(n)) mit h_1(n)=O(1/n) | |(2n)! =(2n)^2n/e^2n*sqrt(2\pi*2n)*(1+h_2(n)) mit h_2(n)=O(1/n) | |=>2^2n*(n!)^2/(2n)! =(2^2n*(n^n/e^n*sqrt(2\pi\.n))^2*(1+h_1(n))^2)/((2n)^2n/e^2n*sqrt(2\pi*2n)*(1+h_2(n)))= | |=sqrt(\pi\.n)*(1+h_1(n))^2/(1+h_2(n))=sqrt(\pi\.n)*(1+(1+2*h_1(n)+h_1^2(n))/(1+h_2(n))-1) | |=sqrt(\pi\.n)+sqrt(\pi\.n)*(2*h_1(n)+h_1^2(n)-h_2(n))/(1+h_2(n)) | |h_2(n)=O(1/n)=>abs(h_2(n))<=1/2 für genügend großes n | |=>abs(1/(1+h_2(n)))<=2 für genügend großes n | |=>abs((2*h_1(n)+h_1^2(n)-h_2(n))/(1+h_2(n)))<2^2n*(n!)^2/(2n)! <produkt(abs((t/2-k)),k=0,n-1)<=1/2^n*produkt((2k-1),k=1,n-1-(t-1)/2)*produkt((2k-1),k=n-(t-1)/2,n-1)= | |=1/2^n\.produkt((2k-1),k=1,n-1) | |qed array(\blue\Hilfssatz 10:)__ | | abs((1/2;n))<<1/n^(3/2) array(Beweis:)__ | | abs((1/2;n))=1/(2^n*n!)*produkt((2k-1),k=1,n-1)=1/(2^n*n!)*produkt(((2k-1)*2k)/2k,k=1,n-1)= | |=1/(2^n*n!)*((2n-2)!/(2^(n-1)*(n-1)!))=1/(2n-1)*(2n)!/(2^2n*(n!)^2)<<1/n*(2n)!/(2^2n*(n!)^2) | |Analoge Beweisführung wie in Hilfssatz ergibt dann die Beh. array(\blue\Hilfssatz 11:)__ | | 1/(t+1)!*abs((t/2;n))<=1/n^3 | |für n<=t<2n array(Beweis:)__ | |abs((t/2;n))=1/n!*abs(produkt(t/2-k,k=0,n-1))<=1/n!*(t/2)^n | |Wegen t<2n ist dies | |<=n^n/n! | |Wegen t>=n ist andererseits 1/(t+1)!<=1/n! | |=>1/(t+1)!*abs((t/2;n))<=n^n/(n!)^2 | |Hierauf die Stirlingformel (diesmal ohne Restglied) ergibt: | |<=(n^n*e^2n)/(n^2n*2*\pi*n)=1/2\pi*1/n*exp(n*(2-logn))<<1/n^m | |mit einer nur von (beliebigem)m abhängigen O-Konstanten. array(\blue\Hilfssatz 12:)__ | | sum(abs((t/2;n))*1/(t+1)!,t=2n,\inf ))=O(1/n) array(Beweis:)__ | |(t/2;n)=1/n!*produkt((t/2-k),k=0,n-1)<=1/n!*(t/2)^n weil alle Faktoren | |positiv sind | |=>sum((t/2;n)*1/(t+1)!,t=2n,\inf )<=1/n!*sum((t/2)^n/(t+1)!,t=2n,\inf )<=1/n!*sum(t^n/t!,t=2n,\inf ) | |t^n/t! =t^n*(produkt(1/(t-k),k=0,n-1))*1/(t-n)!<=(t/(t-n))^n*1/(t-n)!<= | |<=(t/(t/2))^n*1/(t-n)! =2^n/(t-n)! | |Dies eingesetzt in der Summe ergibt: | |1/n!*sum(t^n/t!,t=2n,\inf )<=1/n!*sum(2^n/(t-n)!,t=2n,\inf )<=2^n/n!*e<<1/n \big\Jetzt können wir die Früchte ernten: array(\red\Satz 3:)__ | |a(n)=1/e+O(1/sqrt(n)) array(Beweis:)__ | |Satz 2 =>a(n)=1/e+O(((n!)^2*2^2n)/(2n)!*sum(abs((t/2;n))*1/(t+1)!,t=0,\inf )) | |Hilfssatz 8 =>a(n)=1/e+O(sqrt(n)*sum(abs((t/2;n))*1/(t+1)!,t=0,\inf )) | |Damit genügt es zu zeigen: sum(abs((t/2;n))*1/(t+1)!,t=0,\inf )<<1/n | |sum(abs((t/2;n))*1/(t+1)!,t=0,\inf )=sum(,t=2n,)=S_1+S_2+S_3 | |S_1<S_1+S_2+S_3<<1/n^(3/2)+1/n^2+1/n<<1/n | |qed.
 
\big\Ausblick: Die Differentialgleichung aus Satz 1, die zur Folge b(n) gehört, hat als Basis des Lösungsraums die Funktionen f_1(x)=exp(g(x))/g(x) und f_2(x)=exp(-g(x))/g(x) mit g(x)=sqrt(1-2x) (Dank an Buri) Damit sind die Lösungen von der Form r_k*f_1(x)+s_k*f_2(x) Die oben angegebene Folge b(n)=b_0(n) führt zur Lösung r_0=1/e und s_0=0 Nimmt man für die Folge b_1(n) dasselbe Entwicklungsgesetz, aber verlangt b_1(0)=0 und b_1(1)=0, so ergibt sich für die erzeugende Funktion f folgendes: r_1*e+s_1*1/e=0 und r_1*f_1|'(0)+s_1*f_2|'(0)=1 Setzt man ein, so ergibt diese letzte Gleichung: 0+s_1*2/e=1=>s_1=e/2 Dies in die erste eingesetzt ergibt: r_1*e+e/2*1/e=0 =>r_1=-1/2e =>f(x)=-1/2e*f_1(x)+e/2*f_2(x) f_1(x)=1/g(x)+sum(g(x)^k/(k+1)!,k=0,\inf ) f_2(x)=1/g(x)+sum((-g(x))^k/(k+1)!,k=0,\inf ) Die beiden Summen spielen, wie sich gezeigt hat, keine Rolle. Wir betrachten nur den ersten Summand. Damit ergibt sich b_1(n)~(-1/2e+e/2)*g^(n)(0) Damit ist lim(n->\inf ,b_0(n)/b_1(n))=1/e*1/(-1/2e+e/2)=1/(-1/2+e^2/2) Nach den bekannten Regeln für Kettenbrüche ergibt sich damit: [0;3,5,7,...]=1/(-1/2+e^2/2) Damit erhält man diesen, vermutlich längst bekannten Grenzwert: \red\[0;1,3,5,7,...]=(e^2-1)/(e^2+1) Vielen Dank an spitzwegerich für sein unermüdliches Anmahnen meiner ständigen Fehler, an Buri und viele andere bei der Hilfe, die DGlen in den Griff zu kriegen. Wauzi
 


Dieser Artikel kommt von Matroids Matheplanet
https://matheplanet.de

Die Url für diesen Artikel ist:
https://matheplanet.de/default3.html?article=1001