Latex-Bibliographie in HTML umwandeln

Mathematik: Grenzwert einer rekursiven Folge Released by matroid on Mi. 30. August 2006 15:17:10 [Statistics] [Comments] Written by Wauzi - 8817 x read [Outline] Printer-friendly version -  Choose languageDE EN   \(\begingroup\) 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 [Edit] [To the bottom] \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)) [Edit] \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. [Edit] \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. [Edit] \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 [Edit] \(\endgroup\) [Show outline only] Get link to this article   Printer-friendly version -  Choose languageDE EN     Comments   Für diesen Artikel gibt es keine pdf-Datei Write a comment Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen: : Mathematik :: Zahlentheorie :: Differentialgleichungen :: Rekursion :: Binomialkoeffizienten :: Erzeugende Funktion :: Reine Mathematik :: Folgen und Reihen : Grenzwert einer rekursiven Folge [von Wauzi]   Dieser Artikel ist entstanden als Antwort auf ein Problem von spitzwegerich, das hier behandelt wurde. Die Ausgangssituation ist die Folge (a(n)), die durch folgende Rekursion definiert ist: a(0)=1 a(1)=0 a(n+1)=a(n)+a(n-1)/((2n-1)*(2n+1)) für alle natürlichen n [Edit] [Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

Aufrufzähler 8817   Aufrufstatistik des Artikels Insgesamt 264 externe Seitenaufrufe zwischen 2012.01 und 2023.05 [Anzeigen] Domain Anzahl Proz http://google.de 220 83.3% https://google.com 4 1.5% http://www.bing.com 26 9.8% http://search.babylon.com 2 0.8% http://search.conduit.com 2 0.8% http://search.genieo.com 2 0.8% http://r.duckduckgo.com 1 0.4% https://duckduckgo.com 1 0.4% http://www.ecosia.org 2 0.8% http://search.chatzum.com 1 0.4% http://de.yhs4.search.yahoo.com 1 0.4% http://google.com 1 0.4% https://google.at 1 0.4% Häufige Aufrufer in früheren Monaten Insgesamt 214 häufige Aufrufer [Anzeigen] Datum Aufrufer-URL 2012-2015 (44x) http://google.de/url?sa=t&rct=j&q= 201211-11 (42x) http://google.de/url?sa=t&rct=j&q=standardabweichung rekursiv ermitteln 201212-12 (26x) http://google.de/url?sa=t&rct=j&q=limes rekursive folge 201201-01 (19x) http://google.de/url?sa=t&rct=j&q=rekursive funktion grenzwert 201202-02 (17x) http://google.de/url?sa=t&rct=j&q=rekursive folge grenzwerte 201203-03 (15x) http://google.de/url?sa=t&source=web&cd=6&sqi=2&ved=0CF0QFjAF 201205-05 (12x) http://google.de/url?sa=t&rct=j&q=rekursive folgen grenzwert 201312-12 (9x) http://google.de/url?sa=t&rct=j&q=1/2(a(n-1)+a(n-2)) rekursive folge konverge... 201206-06 (8x) http://google.de/url?sa=t&rct=j&q=zeige rekursive folge konvergiert 201305-05 (8x) http://google.de/url?sa=t&rct=j&q=konvergenzradius rekursion bestimmen 201204-04 (6x) http://google.de/url?sa=t&rct=j&q=stirling transformation rekursion 2022-2023 (4x) https://google.com/ 201301-01 (4x) http://google.de/url?sa=t&rct=j&q=rekursive folge konvergenz [Top of page]

Re: Grenzwert einer rekursiven Folge von: Spock am: So. 03. September 2006 15:27:32

\(\begingroup\)Hallo Wauzi, mit "banal" und "leicht nachvollziehbar" hast Du sicherlich ein wenig "leicht untertrieben", man muß sich schon etwas mehr beschäftigen mit dem Grenzwert, :-). Auf welche Art und wie man dabei vorgehen sollte, hast Du uns sehr schön und nachvollziehbar gezeigt. Frage: An den Stellen, an denen Du die Stirling'sche Formel benutzt, sollte da statt ein "=" nicht ein vorsichtigeres"~=" stehen, oder steckt das "~" in O(x)? Gruß Juergen\(\endgroup\)