Mathematik: Grenzwert einer rekursiven Folge
Released by matroid on Mi. 30. August 2006 15:17:10 [Statistics]
Written by Wauzi - 8795 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\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

\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
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria 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
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 8795
 
Aufrufstatistik des Artikels
Insgesamt 260 externe Seitenaufrufe zwischen 2012.01 und 2022.03 [Anzeigen]
DomainAnzahlProz
http://google.de22084.6%84.6 %
http://www.bing.com2610%10 %
http://search.babylon.com20.8%0.8 %
http://search.conduit.com20.8%0.8 %
http://search.genieo.com20.8%0.8 %
http://r.duckduckgo.com10.4%0.4 %
https://duckduckgo.com10.4%0.4 %
http://www.ecosia.org20.8%0.8 %
http://search.chatzum.com10.4%0.4 %
http://de.yhs4.search.yahoo.com10.4%0.4 %
http://google.com10.4%0.4 %
https://google.at10.4%0.4 %

Häufige Aufrufer in früheren Monaten
Insgesamt 210 häufige Aufrufer [Anzeigen]
DatumAufrufer-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
201301-01 (4x)http://google.de/url?sa=t&rct=j&q=rekursive folge konvergenz

[Top of page]

"Mathematik: Grenzwert einer rekursiven Folge" | 2 Comments
The authors of the comments are responsible for the content.

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\)
 

Landausymbol bei Abschätzungen
von: fru am: So. 03. September 2006 17:03:43
\(\begingroup\)Hallo Juergen! Da Wauzi sich wohl noch einige Zeit die Sonne auf den Bauch scheinen lassen wird, erlaube ich mir, für ihn einzuspringen: Die Schreibweise mit dem Gleichheitszeichen ist korrekt. Ein Summand der Form O(x) steht für den Fehler der Abschätzung (eigentlich für eine Funktion aus einer ganzen Funktionenklasse). Liebe Grüße, Franz \(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]