Granica ciągu rekurencyjnego — kolokwium z analizy 1 na MIMUW, zad. 5
Zadania od widzów⏱ 22 min
Zadanie 5 z kolokwium z Analizy Matematycznej 1 na MIMUW – złośliwe, bo kusi szukaniem wzoru jawnego, którego nie ma. Rozwiązanie przez brutalne szacowanie ciągu z góry i z dołu, z granicą ukrytą pod podwójnym logarytmem.
W tym nagraniu
Ciąg rekurencyjny bez wzoru jawnego
Monotoniczność i indukcja
Szacowanie z góry i z dołu, twierdzenie o trzech ciągach
Granice z logarytmami – co „znika” pod podwójnym logarytmem
Zadanie 5 z kolokwium z Analizy Matematycznej 1 na MIMUW dotyczy ciągu zadanego rekurencyjnie. Jest złośliwe, bo kusi szukaniem wzoru jawnego, a takiego wzoru po prostu nie ma — trzeba sobie poradzić bez niego.
Rozwiązanie zaczyna się od monotoniczności udowodnionej indukcyjnie, a potem przechodzi do „brutalnego” szacowania wyrazów ciągu z góry i z dołu prostszymi wyrażeniami. Twierdzenie o trzech ciągach zamyka sprawę: jeśli oba oszacowania mają tę samą granicę, ma ją też badany ciąg.
Najciekawszy jest finał: granica ukryta pod podwójnym logarytmem, gdzie trzeba ocenić, które składniki „znikają” po dwukrotnym zlogarytmowaniu, a które decydują o wyniku. Krótkie, 23-minutowe nagranie dobrze pokazuje, jak podchodzić do ciągów rekurencyjnych na kolokwium.
Lekcje kursu „Matematyka od nowa” na ten temat
Szkolne podstawy tego, o czym jest nagranie — interaktywnie i za darmo.
Transkrypt został wygenerowany automatycznie na podstawie napisów YouTube, więc może zawierać błędy w zapisie wzorów, nazwisk i terminów. Kliknij znacznik czasu, aby przewinąć wideo do danego fragmentu. (2135 słów)
Słyszałem że studenci na analizie na na mimie dostali tak trudne zadanie że nawet Panda się obraziła i stoi do niego odwrócona tyłem A tak No więc zadanie jest w pewnym sensie złośliwe bo ono ono beje na to że może policzyć wzór jawny a tu nie tu wzoru jawnego po prostu nie ma chyba że ktoś chce mnie oświecić to bardzo chętnie się dowiem W każdym razie nasz plan jest taki żeby zrobić to zadanie przez brutalne szacowanie w pewnym sensie fakt że mamy do policzenia te granice z tymi logarytmami to jest jakaś podpowiedź to znaczy że dużo informacji o tym ciągu może znikać pod podwójnym logarytmem W każdym razie Powiedzmy że niech to będzie klasa ciągów ków to jest zbi XN od z do nieskończoności takich że XN kW nie bez kwadratu rów XN 1 K plus XN 2 kW dla większego równego 2 tak tymczasem właśnie tam się dzieje wojna domowa między
Kotami która zabiła już kilka poprzednich nagrań w każdym razie mamy nasz ciąg co może nim powiedzieć możemy o nim powiedzieć że Zauważcie że ma taką monotoniczność od wyrazów porządkowych pierwsza oczywista rzecz do powiedzenia jest taka że że jeśli A0 i A1 są mniejsze od 1/2 to przez indukcję to ogólnie an jest mniejsze niż 1/2 No bo to szacuje się przez D poprzednie do kwadratu i dodane dwa poprzednie są mniejsze niż 1/4 1/4 1/2 W każdym razie nasz plan jest strasznie strasznie brutalny my chcemy bo ogólnie z monicz nością tego ciągu to jest problem tak A priori ciężko się porównuje to z x-1 Zrobimy tak Powiedzmy że niech niech duże u to będzie maksimum A0 A1 i duże l to będzie minimum a01 no i przez l to oznaczymy ciągi
Które są lower Bound to znaczy powiemy że ciąg un jest taki że u0 jest równe U1 równe oraz cgas i tak SG nie przestrzeni naturalny który się pojawi w tym zadaniu tak to oznaczenie jest trochę złośliwe tak i ten ciąg jest jest tej klasie dob zaczy od d x Zobaczmy co się dzieje Wyobraźmy sobie że x jest mały to to potem się dzieje 2x kW jak x jest 1 to jest 1 to jest strasznie mało tak to jest tak w tej wersji potem mamy sumę kwadratów poprzednich czyli tu jest x kwad to jest jeszcze jakieś A poprzed to jest to jest str małe Domin x
K jak bierzemy sumę kwadratów tych to to jest 4x do C plus kwadrat tego czyli x do C plus 8x do6 + 16x do88 Nieważne nie za bardzo umiem liczyć na na liczbach całkowitych ale chodzi mi o to że Spójrzcie tu są dwa jakieś x są z grubsze tego samego rzędu wielkości jak x jest małe tu jest rzędu x k tu jest rzęd x k potem jest znowu x4 następne to będzie kwadrat tego rzędu x4 Plus jes czyli tak mniej więcej heurystycznie spodziewamy się że będzie coś na rzeczy ze skakaniem O2 Ponadto gdzie k poszedł sobie trudno Ponadto ponadto Zauważcie że x kwadrat jest mniejsze niż owszem mniejsze niż 1/2 natomiast jest również mniejsze niż x x 2x a 2x jest mniejsze od 1 czyli jak zaczynamy od dwóch rzeczy
Mniejszych od JJ drugiej to pierwsze trzy wyrazy tworzą ciąg nierosnący to jest pierwsze spostrzeżenie które chcem udowodnić pierwsze spostrzeżenie jest takie kim zer że że nie wychodzimy SP poza 012 kim 1 jest taki że u i l są ni rosnące nie rosnące dlaczego tak jest dlatego że Spójrzcie że u0 większe równe U1 większe równe U2 bo U2 jest równe 2 U1 krat bo te są w ogóle równe w szczególności większe równe No to ja to propaguje przez indukcję fakt że un jest większy równy u n plus 1 większy równy niż un + 2 to to produkuje stwierdzenie że un 3 to jest un + 2 k plus un + 1 K I to jest mniejsze równe niż un + 2 tu
Się mogę cofnąć tu się mogę cofnąć a Toż to z definicji jest un plus 2 czyli do każdego takiego cinu trzech nierówności mogę dopisać następną że to jest że un + 2 jest większe rów niż + 3 więc jest udow przez indukc rosnące dobra drugi doś oczywisty tejas r że One S monotoniczne ze względu na warunki początkowe to znaczy że jeśli ja powiem że że takie jak tam są to prostu jest taki że ten lower Bound jest mniejszy niż mniejszy niż No to jest rów un plus 1 K plus 2 k to jest większe równe niż an min 1 kW plus an min 2 kW i to jest równe an więc z tego oszacowania dla dost wystarczy pierwszych dwó a dla pierwszych dwóch było tak uszyte zaczynało się odum
Dobra na tym się kończy ta identyczność tego jak traktujemy ciągi u dob to teraz prościej będzie szacować szacować z dołu bo Patrzcie teraz mam taki napis Mam taki napis że ln rów l 1 K plus ln min 2 k w moich notatkach pracowałem na ciągu 2 raz an więc zapewne pomyli się gdzieś w oznaczeniach albo w w potęgach dwójki tu nasz plan jest taki żeby zrobić hiper brutalne szacowanie to znaczy to szacujemy po prostu z dołu przez ln min 2 k tak tak No to to już goł okiem widać co się stanie ja mam l0 L1 co najwyżej to do kwadratu co najwyżej poprzednie do kwadratu 0
1 tu jest l0 L1 w ten SP naw L3 mniejsze równe tu mam za poprzednie do kwadratu tu mam też za poprzednie do kwadratu i teraz żeby się nie pomylić w indeksach Napisałem tak więc przez indukcję przez indukcję mówimy że ln jest ach Chciałem sować to z dołu tak przepraszam to miało być w ten sposób tak ln są większe równe niż l Do jakiej potęgi za każdym pójściem tutaj o 2 idę z potęgą dwójki o 1 w górę czyli to powinno być 2 do potęgi podłoga n PR 2 zgadza mi się tu mam L do 8 l do 8 l6 L7 6 PR 2 to jest 3 7 PR 2 to jest 3 i zgadza się To jest to jest k 3 i
Teraz tu było hiper brutalne szacowanie korzystające po prostu z tego że po prostu z tego że żeśmy dodatni wymiem odrobinę mądrzej teraz w ciągu n ja to Oszacuj przez poprzednie No przez większe z tych dwóch poprzednich tak udowodniliśmy w którymś tam kimie że te ciągi są jakie są nie rosnące czy jak ja się chcę brutalnie oszacować przez D razy większy No to mam d razy un k to teraz żeby się nie narobić To ja powiem że jak ja chcę powiedzieć Powiem że niech VN jak ja powiem że niech un będzie równe 2n czy PR 2 jak podstawi 2n to mi się tut rozmnoży za dużo dwójek Czy potrzebuję VN PR 2 to wtedy VN PR 2 będzie mniejsze równe niż 2 x VN 2 2 k czyli VN jest k tak
Tak I mam dokładnie te samo sytuację tutaj tylko że z odwroconymi nierównościami tu jestem większy niż sięgnięcie dwa wyrazy WZ do kwadratu a tu jestem mniejszy Czyli dokładnie tak samo ja zaczynam od tego że że moje pierwsze dwa wyrazy szacują jest 0o jest jest mze równe niż nawet równe u jest mnie rów niż potem mam kW U2 U3 i tak dalej tak samo jak tutaj czyli tak samo przez indukcję tak samo przez ind także on to ja powiem co ja powiem że niech duże to będzie d razy duże u tak ja tut chciałem zrobić V wszystko żeby tylko mieć jak naj więcej literek jak najkrótsze wzory tak przez indukcję Ja teraz chcę powiedzieć że VN jest mniejsze równe niż V do
Potęgi 2 do potęgi podłoga z n pr2 tak samo jak tam I teraz jak wrócimy do do u to ten 4 który chcemy który twierdzimy że udowodniliśmy to jest jaki taki że un jest równe PR 2 czyli jest mniejsze równe niż 1/2 duże v v to jest 2u świnie 2 do pot 2 do po n dobrze to jest ten to Teraz jesteśmy praktycznie w domu patz było Górne posanie na było dobre Myślałby kto że robimy szacowania brutalne także aż zęby bolą natomiast heurystyka była taka że wynik zadania nie zależy od warunków początkowych to jest dość ciężka heurystyka x policzy to to z grubsza widać m No więc ja teraz napiszę sobie że an jest mniejsze równe niż 1/2 2 u do potęgi 2 do podłoga n PR 2 większe równe
Niż y jak tam było l do potęgi 2 do podłoga n PR 2 tak napisałem tak no to co co z tego widać oczywiście to jest większe od zera a to dąży do zer bo u u jako jako maksimum A0 a1 jest mniejsze niż 1/2 więc 2u jest mniejsze niż jedynka więc to dąży do z świetnie to Zrobiliśmy a zrobiliśmy część a wyszło jako teraz walczyliśmy część B w części B to robimy szacowania z góry i z dołu takie jak tutaj bierzemy ten logarytm logarytmu 1 PR an prze n tak być może dla złośliwych złośliwie dużego a A0 toog więc to jest większe od zera tak więc ten napis ma sens w każdym razie szacowali z dołu przez takie coś mam
Mianowniku więc szacujemy to z góry tak dla dostatecznie dużych n to jest to jest dodatnie wic tak to szacujemy z góry przez logarytm naturalny logary naturalnego l do potęgi min 2 do podła n pr2 Przez N No to co się ukazuje naszym oczom ukazuje się wielki festiwal skracania i wyciągania rzeczy przed nawias tu będzie 2 do potęgi n PR 2 a tu będzie logarytm naturalny 1 przez l widziałem kiedyś na Facebooku sondę czy czy liczby mniejsze od 1 wolicie pisać logary Natural X min log naturalny x czy moduł logary Natural z x to to to właśnie zabawne jak różne okoliczności w których się zazwyczaj spotyka logarytm powodują różne preferencje estetyczne dopisania tego no tak czy tak każda z tych rzeczy jest jest większa od zera Więc ja tu mogę napisać logarytm naturalny 2 do podłoga n przez 2 plus logarytm naturalny logarytm naturalnego 1 PR l Przez N No i już
Widać konspirację to nie ma znaczenia to jest To jest coś co się szacuje z góry przez 100 raz 1 n plus Przez N podłoga n przez 2 razy konkretna stała No więc to dąży do zera to dąży do 1/2 to dąży do logarytm naturalnego 2 PR 2 to bez sensu napisałem bo i tak zaraz będę pisał oszacowanie Dolne z tych z u tak mamy nadzieję że z góry wyjdzie że z dołu wyjdzie tak samo przez to szacowanie a z góry to znaczy że nie będzie miało znaczenia że tu mam 1/2 i mam dwójkę No spodziewamy się że tak będzie gdyż gdyż co no gdyż tu d pełni taką samą rolę jak l i to J dr nie powinna przeszkadzać więc jak l log 1 PR an to to jest większe równe log log I teraz tu była 1/2 czyli tu będziemy mieć 2 r 2u do potęgi min 2 do n PR
2 Przez N teraz jest Trę większe od te wszystkie logarytmy s Legal tak to jest większe od jedynki więc tak więc to jest większe dobr to jest równe logarytm logarytmu przeszkadza najprostszy sposób pewnie jest taki żeby wpakować do wykładnika bo to będzie mieć sumę logarytmów to oczywiście się wszystko napisze tak samo natomiast chc to pisać w najmniejszej ilości znaczków to napiszemy to tak że tu jest 2u tu jest 1 PR 2u do potęgi jakaś stała plus 2 do n PR 2 gdzie gdzie c jest równe logarytm przy podstawie 1 PR 2u z 2 tak
Tak no to to jest dokładnie to samo co było wcześniej 1 PR 2 jest pełni rolę naszego min pi logary Z C 2 2 raz logarytm naturalny 1 PR 2u takie coś przez n czyli logarytm naturalny co tutaj dje to plus logarytm logarytmu tego czegoś To przez n i to przez n to dąży do zera to jest wbrew pozorom u a nie n a to na przykład możemy to napisać jako logary 2 do podłoga n PR 2 raz 1 plus 2 do minus podłoga plus c x 2 do minus podłoga n PR
2 Przez N i i to jest jen logarytm czyli takie coś plus drugi logarytm 1 plus coś co dąży do coś co dąży do jedynki więc to dąży do zera bo to jest bo to dąży do stałej A to to jak już wiemy dąży do logt naturalnego 2 przez przez d i już wyszła odpowiedź z góry i z dołu o panna przyszła patogeniczny kod m