Indukcja matematyczna i zasada minimum — wykład 1 z analizy I
Analiza matematyczna · UJK⏱ 55 min
Wykład 1 z Analizy Matematycznej I na UJK w wersji nieokrojonej: słaba i silna indukcja matematyczna oraz zasada minimum dla liczb naturalnych. Na przykładach: jawny wzór na wyrazy ciągu Fibonacciego ze złotym podziałem i nierówność między średnią arytmetyczną a geometryczną dowodzona „zwariowaną” indukcją – najpierw dla potęg dwójki, potem w dół.
W tym nagraniu
Słaba indukcja – w wersji ze zdaniami i ze zbiorami
Silna indukcja i opowieść o kulcie na wyspie
Zasada minimum: każdy niepusty zbiór liczb naturalnych ma element najmniejszy
Jawny wzór na ciąg Fibonacciego i liczba złotego podziału
Nierówność AM-GM przez indukcję od potęg dwójki w dół
Pierwszy wykład z Analizy Matematycznej I na UJK, w wersji nieokrojonej, jest o indukcji matematycznej. Słaba indukcja pojawia się w dwóch wersjach — dla zdań T(n) i dla zbiorów liczb naturalnych — a silna indukcja, z założeniem dla wszystkich mniejszych liczb, zostaje zilustrowana opowieścią o kulcie na wyspie.
Równoważną postacią indukcji jest zasada minimum: każdy niepusty zbiór liczb naturalnych ma element najmniejszy. Pierwszy duży przykład to jawny wzór na ciąg Fibonacciego, Fₙ = (φⁿ − ψⁿ)/√5, gdzie φ = (1 + √5)/2 to liczba złotego podziału, a ψ = (1 − √5)/2.
Drugi przykład to nierówność między średnią arytmetyczną a geometryczną, dowodzona „zwariowaną” indukcją Cauchy’ego: najpierw dla liczby składników będącej potęgą dwójki (2, 4, 8, …), a potem „w dół” — z n składników na n − 1. To dobry wstęp do całego kursu analizy.
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. (4672 słów)
Zobaczymy dzisiaj wykład o indukcji w wersji nieokrojonej. To, co widzieliśmy na wykładzie na żywo, to było takie twierdzenie. Która jest tak zwana słaba indukcja? Twierdzenie jest takie, że mamy jakiś ciąg zdań, powiedzmy t od 0, t od 1 itd. To są zdania. I ja wiem dwie rzeczy. Wiem, że t od 0 i umiem dla każdego n przynajmniej 0 z t od n wywnioskować t od n plus 1. I twierdzenie mówi tyle, że to implikuje, że t od n zachodzi zawsze.
My to formułowaliśmy w wersji do zdań i to jest sposób w jaki się o tym myśli. Natomiast taka totalnie wysuszona z fabuły wersja jest taka. Ja mam zbiór, to jest postbiór liczb naturalnych i on spełnia dwa warunki. 0 należy do a, dla każdego n-a wiem, że jeśli n należy do a, to n plus 1 należy do a. I z tego wnioskuję, że a to jest całe n. Ogólnie tu jestem leniwy i dla mnie n to jest n z 0.
To wszystko można zaczynać od dowolnej innej liczby, dla ustalenia uwagi od 0. Dlaczego te dwie wersje to jest to samo? Dlatego, że konwersja w tę stronę jest taka, że zbiór A to jest zbiór tych N-ów, że zachodzi T od N. Konwersja w tę stronę jest taka, że zdanie T od N mówi, że N należy do A. Ja tu mam całą listę tych zdań. Z listy zdań mogę zrobić zbiór i ze zbioru zrobię listę zdań.
Każde zdanie mówi taką jedną rzecz. I to jest taka najprostsza, najbardziej bread and butter indukcja, jaką się widzi, kiedyś się widziało w szkole. I o niej należy myśleć w ten sposób. Liczby chorują na COVID. Mamy ustalone w rządku 0, 1, 2, 3, 0, dostało test pozytywny. Ta implikacja, o niej należy myśleć w ten sposób, że jeśli N choruje na COVID, to N plus 1 się od niego zarazi. Więc biorąc N równe 0, zarazimy 1.
Biorąc n równe 1, zarazimy dwójkę. Biorąc n równe 2, zarazimy trójkę, itd. W ten sposób zachoruje nam wszystkie liczby naturalne. Jeśli będziemy je kwarantannować, to zajmą wszystkie miejsca w hotelu Hilberta, o którym prawdopodobnie usłyszycie na podstawach matematyki. Najbardziej brutalny z nietrywialnych przykładów tego, jak działa taka indukcja, to jest nierówność Bernoulliego, jednego z wielkiego mnóstwa Bernoullich. To były jeszcze te czasy, kiedy za napisanie czegoś takiego w naturalnych, a większe równego minus 1, kiedy za napisanie czegoś takiego można było zostać nazwiskiem przy twierdzeniu z nazwiskiem.
Potem czasy się trochę zmieniły. Zrobiło się więcej matematyków i więcej twierdzeń. to myślimy o tym w ten sposób, że zdanie t0 to jest ta nasza nierówność dla 0. 0 i większe równe 1 plus 0 razy a. Nie jest to specjalnie nieoczekiwane. To jest 1 i to jest 1. Zdanie tn mówi tyle i chcemy z tego wywnioskować zdanie tn plus 1. Jak to robimy?
W najbardziej brutalny możliwy sposób. Patrzymy na 1 plus a do n plus pierwszej. Ono się składa z tego i na to mamy paragraf. Teraz 1 plus a. I teraz tu jest ważne. Szacujemy to z dołu, korzystając z tego, że to jest nieujemne. Tak, to jest ten jedyny moment, w którym korzystamy z tego założenia. Więc to możemy oszacować z dołu z założenia indukcyjnego przez 1 plus n. To już się wymnaża.
Tu jest 1 plus n plus 1a plus na2 i to jest szczęśliwie zawsze nieujemne. Więc to jest większe równo niż 1 plus to, co miało wyjść. I już, koniec. Jak zaczniemy coś mówić o pochodnych, to zobaczymy, że dla małych a, ogólnie ta nierówność jest bardzo brutalna. Dla dużych a to jest wielomiennego stopnia, to jest głupia funkcja liniowa. Przy okazji pochodnych się przekonamy, że tak naprawdę ta nierówność jest fajna dla małych a. Dla małych a te rzeczy są bardzo, bardzo bliskie jedno drugie.
Naprawdę to, jak to potraktować jako funkcję od a, to to jest styczne do wykresu tej funkcji. Koniec spoilerów. No więc jak się ogólnie mówi o indukcji, to warto wiedzieć, że jeśli chcemy udowodnić zdanie Tn plus 1, to naszym całym arsenałem nie jest tylko zdanie Tn. Tak naprawdę można skorzystać ze wszystkich wcześniejszych. I to jest twierdzenie, które się nazywa silną indukcją. Czyli ja mam zdania T0, T1 i tak dalej.
I ja wiem dwie rzeczy. Wiem t0 i wiem, że dla każdego n od t0 do tn, jak piszę przecinek, to jest domyślna koniunkcja. Dla każdego n to całe towarzystwo implikuje tn plus 1. To ja z tego wnioskuję, że dla każdego n zachodzi tn. Równoważnie w wersji ze zbiorami mam a, to jest pozbiór liczb naturalnych. Konwersja jest taka sama jak wcześniej. a to jest zbiór dokładnie tych n, dla których zachodzi ich zdanie tn. Ja wiem, że 0 należy do A i wiem, że dla każdego n, jeśli to całe towarzystwo należy do A, to i n plus 1 należy do A, to z tego ja mogę wywnioskować, że dla każdego n należy do A, czyli po polsku A to jest wszystko.
I widać, że to jest twierdzenie, które jest istotnie silniejsze od tej normalnej indukcji. Teza jest taka sama, ale kładziemy słabsze założenia, bo ta implikacja jest tym słabsza i więcej zakładamy. W nagrodę za to, że udowodnimy silniejsze twierdzenie, które rządzi tym całym interesem, to będziemy mieć prościej w dowodzeniu zadań. Gdzie słowo udowodnimy było na wyrost, ponieważ jeszcze nie udowodniliśmy, Myślę, że to jest prawda, ale udowodnimy za niedużo minut.
Kanoniczny przykład zastosowania. Mogę zrobić jakiś głupi przykład, ale zrobię taki trochę mądrzejszy. Tak naprawdę po prostu chcę przemyślić ten rachunek kiedyś, a teraz jest dobry moment. Ciąg fibonacciego. Trochę trudno nie mieć z tym styczności, jak się kiedykolwiek trafiło w szpony jakiegoś popularyzatora matematyki. To jest ciąg nirwowy. pierwszy wyraz 0, drugi wyraz 1 i teraz jest rekurencja fn plus 2 to jest fn plus 1 plus fn a, oczywiście jeszcze powinienem był powiedzieć obowiązkową interpretację życiową tego jak działa silna indukcja wcześniej było tak, że zarażaliśmy kolejnych pacjentów covidem teraz ci pacjenci są odporniejsi oni potrzebują wszystkich poprzednich, więc myślimy o tym w ten sposób Jest sobie wysepka i na niej jest kult, który czci coś, czci jakiegoś kotka.
No i ten kotek ma swój ołtarzyk. I na wyspę przyjeżdża liczba 0. Ona staje się założycielem kultu. Potem do wyspy przepływa liczba 1. Liczba 1 jest sceptykiem. Liczba 1 uwierzy w kult tylko wtedy, kiedy wszyscy inni na wyspie będą w niego wierzyć. Więc to jest taki trochę sceptyk, ale trochę jednak podatny na presję grupy. Jak na razie wszyscy wierzą. Jeden też zostaje wyznawcą kotka.
Potem przepływa liczba dwa. Liczba dwa jest takim samym sceptykiem. Ona uwierzy w kult, tylko jeśli każdy, z którym porozmawia, będzie w niego wierzył. No to mamy. To jest dokładnie to założenie, że wszyscy wcześniejsi są prawdziwi. No i tak dalej. Przepływa sobie liczba trzy. patrzy, że wszyscy do tej pory uwierzyli, to ja uwierzę. I tak dalej. A oprócz tego nikt nie zabrania im mieć COVID-u. Tymczasem, ciąg sił bonacciego. To będzie takie kiepskie zastosowanie tej silnej indukcji, ale ono jest fajne samo w sobie. Twierdzenie, które my chcemy udowodnić jest takie.
Zdanie TN mówi, że FN to jest taki napis alfa do entej minus beta do entej przez alfa minus beta, gdzie alfa to jest 1 plus pierwiastek z 5 przez 2, beta to jest 1 minus pierwiastek z 5. Dlaczego takie liczby? Ponieważ dla nich wychodzi rachunek, który dalej będzie miał miejsce. Będziecie mieć osobny przedmiot pod tytułem matematyka dyskretna, na którym będzie mowa o tym, skąd się takie rzeczy biorą. Co nie stoi w sprzeczności z faktem, że na algebrze liniowej też to powinno być pokazane jako zastosowanie potęgowania macierzy.
Czy będzie to już nie zależy ode mnie my robimy tak my najpierw sprawdzamy t0 t0 to jest proste bo to jest powiedzenie, że f0 jest równe alfa do zerowej minus beta do zerowej przez alfa minus beta czyli innymi słowy f0 jest równe 0 to jest też dość podobne to samo jest, to jest 1 minus 1 to mamy teraz sprawdzamy t1 dlaczego? dlatego, że rekursja ma zagłębienie 2 Więc od czego się musimy zacząć? Od jakichś dwóch początkowych kawałków Teraz nas pytają, czy jest prawdziwe t1 Bez wątpienia, 1 jest równe alfa minus beta przez alfa minus beta To teraz chcemy wykazać, że wszystkie aż do miejsca n minus 1 implikują tn I chcemy to zrobić dla n większych równych 2
Bo dla n równego 0 i 1 mamy tn zagwarantowane, bo sprawdziliśmy ręcznie. Tak więc implikacja jest tym bardziej prawdziwa, jak następnik jest prawdziwy. Nic prostszego. Chcemy wykazać tn, czyli chcemy coś policzyć o fn. Czyli nasz tn nam mówi, że fn jest równy alfa do n tej minus beta do n tej przez alfa minus beta. I zastanawiamy się, czy to jest prawda. Teraz będziemy pisać równoważności. To jest równoważne z Fn-1 plus Fn-2. Dlaczego? Bo to jest równe Fn z definicji samego ciągu F.
Jak na razie to jeszcze nie jest indukcja. Teraz pojawia się pierwszy moment, w którym robimy indukcję. To znaczy, przypominamy sobie, że z założenia indukcyjnego Fn-1 wyraża się wzorem. To jest tn-1, fn-1 ja mogę przetłumaczyć na alfa do n-1 minus beta do n-1 przez alfa minus beta. Plus fn-2 tak samo, z tn-2 przetłumaczę na wzorki. Więc skorzystaliśmy nie z całego założenia indukcyjnego, ale i tak zistotnie więcej niż nam pozwalała taka zwykła słaba indukcja.
Teraz to są już rachunki. teraz to mnożymy przez alfa minus beta które jest różne od zera i dostajemy napis taki i dalej jest już taka algebra która w zasadzie sama się narzuca jak policzyć na jedną stronę możemy wrzucić bety drugą stronę alfy i naszym oczom ukazuje się coś z tym wielomianem kwadratowym jest bardzo na rzeczy teraz myślimy sobie taką heurystyką gdyby to znaczy myślimy taką heurystyką że to jest równoważne
Z tym, co mamy udowodnić. Co by było nam potrzebne do tego, żeby to była prawda? Zauważcie, że jak ja to przeniosę tu, to tutaj, to mam beta przez alfa do n minus drugi równa się liczba niezależna od n. To trochę zonk, bo to by znaczyło, że beta przez alfa musi być równe 1 albo 0. One ani nie są równe, ani żadne nie jest 0. Więc zonk był w tym momencie, w którym chciałem podzielić przez to. Podobny zonk bym dostał, gdybym podzielił przez to. To znaczy, że zapewne powód, dla którego ta nierówność jest prawdziwa, jest taki, że te dwa są równe 0. No ale zaraz, to znaczy, że alfa i beta są pierwiastkami konkretnego równania kwadratowego.
Co zresztą nie trudno sprawdzić. Jak ja napiszę równanie, dokładnie to, które tam się napisało, x kwadrat minus x minus 1 równa się 0, no to mniej lub bardziej gołym okiem widać, że one są pierwiastkami tego równania. Każde dziecko umie policzyć deltę, która wychodzi 5 i stąd ten paskudny pierwiastek z 5.
No i już. To jest równoważne z tym, że 0 jest równoległe do 0. Czyli to prawda. Czyli mając wiedzę o Tn-1 i Tn-2 wykazaliśmy Tn. Czyli już jesteśmy zrobieni. To w literaturze ma swoją nazwę. To się nazywa wzór Bineta. Tego samego co odtwierdzenie kosz jego Bineta o liczeniu wyznaczników, o którym też być może usłyszycie. Normalnie się go pisze w jakiejś takiej formie, z tym alfa i beta podstawionymi, wtedy to jest wielki, straszny wzór, a z tego widać, że to jest bardzo taki oswojony wzór.
To, co też warto zauważyć, to to, że moduł bety jest mniejszy od 1. Pierwiastek z 5 to jest 2 z kawałkiem. Więc jak od tego odejmę 1, to mam 1 z kawałkiem, podziewę przez 2, to jest akurat trochę mniej niż 1. To chyba jest jakieś minus 0,60 coś. Alfa to jest to normalnie, to co się nazywa lirbą złotego podziału, to jest dokładnie 1,60 coś tam. więc jak n jest duże to to nie ma znaczenia alfa minus beta z kolei to jest pierwiastek z pięciu więc fn jest równy w znakomitym przybliżeniu do pierwiastek z pięciu tu nasze alfa, gdzie błąd maleje wykładniczo mógł już sam fakt, że jak ja wezmę n tą potęgę czegoś takiego
I n tą potęgę czegoś takiego i potem jeszcze podzielę przez pierwiastek z pięciu to wychodzi mi nierwa całkowita to się wydaje na pierwszy rzut oka nietrywialny akurat o tym się można przekonać rachując na symbolach Newtona ale tutaj to wyszło za darmo co ja wam jeszcze obiecałem a obiecałem wam wytłumaczyć się z tego dlaczego ta zasada indukcji w ogóle jest prawdziwa oprócz tego, że chłopski rozum i intuicja mówią że tak się propaguje COVID no więc są trzy rzeczy są te dwie zasady indukcji i jest jeszcze zasada minimum to jest najprostsze dla wszystkich to znaczy, jeśli ja mam zbiór pusty, znaczy zbiór niepusty, który jest pozbierany liczb naturalnych, to wtedy on ma element najmniejszy.
Pamiętamy, że jaką niepusty pozbiór liczb rzeczywistych, jeszcze ograniczony z dołu, to on ma kres dolny. Tutaj się nie trzeba uciekać do takiej finezji, to jest po prostu brutalnie element najmniejszy, który jest elementem zbioru. No i to jest takie w sumie self-explanatory. Po prostu tyle, że jak ktoś mi wylistuje ileś liczb, nawet nie skończę niewiele, to mogę wśród nich pokazać najmniejszą. Często nie pokażę największej, ale najmniejszą już tak. Liczby naturalne kończą się z lewej strony. Między tymi trzema twierdzeniami jest równoważność, czyli jest zasada minimum.
Tak naprawdę to, my tam jeszcze piszemy jakieś rzeczy drobnym druczkiem, że to wszystko jest przy założeniach akcjomatyki Peano, że dodawanie jeden działa w liczbach naturalnych. To jest już ten grunt podstaw matematyki, w który mamy zapuszczone fundamenty. Silna indukcja jest lepszym twierdzeniem niż słaba. Ona implikuje zasadę minimum, a ona implikuje silną. Powiedzmy, że to jest 1, to jest 2, to jest 3.
1 to jest oczywiste. Jeśli jakiś ciąg zdań, my chcemy udowodnić, że jeśli ciąg zdań spełnia założenie słabej indukcji, to spełnia jej tezę przy założeniu, że mamy silną indukcję jako twierdzenie. Jeśli on spełnia założenia słabej indukcji, to spełnia też silnej. Tak, bo założenia silnej indukcji są słabsze. To, co jest to, co jest tutaj, to jest słabszy claim.
To jest mniej wiedzy, że mamy te implikacje przy większym założeniu. Więc też spełnia tezę silnej indukcji, czy inaczej słabej. Po prostu to jest za darmo. Implikacja numer 3 na przykład, to ona działa jakoś tak. Mamy zasadę minimum. Chcemy udowodnić silną indukcję. To udowodnijmy silną indukcję dla zbiorów, bo tak będzie o tym prościej myśleć. Niech założenia silnej indukcji.
No i chcemy udowodnić, że a to jest wszystko. Udowodnić, że o taki zbiór jest pusty. Jak zwykle to jest dowód przez zaprzeczenie. I teraz to jest ten moment, w którym korzystamy z założeń tej implikacji 3.
To jest ten moment, w którym korzystamy z zasady minimum. Niech b to będzie minimum b. No to świetnie. to mamy zlokalizowany najmniejszy element naszego zbioru złoczyńców i ja mogę napisać że B jest różny od 0 dlaczego? bo B należy do B oraz 0 należy do A z faktu, że A spełnia założenie tamte co jeszcze chcemy wiedzieć?
Chcemy wiedzieć, że jaka jest mi jakąkolwiek liczbę od 0 do B-1 B jest przynajmniej 1, bo nie jest 0 więc ten zbiór jest niepusty C jest mniejsze niż minimum B, więc C nie należy do B. C nie należy do B, C należy do A. Przychodzimy z pomocą faktu, że A spełnia założenie silnej indukcji.
Za każdym razem, jak A spełnia dwie rzeczy. To, że mamy początek i to, że jak mamy jakikolwiek niepusty, porządkowy kawałek, który cały siedzi w A, to możemy go rozszerzyć dalej. To jest B kultystów na wysepce i przyjeżdża nowy. Całe towarzystwo siedzi w A, w tej indukcji również B należy do A.
No, a to jest sprzeczność, bo B to w ogóle było minimum zbioru, który był rozłączny z A. Trochę masło maślane, natomiast znaczki tak mają, że się opisuje prostą ideę i ona się zaczyna wydawać trudna. Tak naprawdę to gist polega na tym, że indukcja mówi tyle, że możemy się przesuwać do przodu, a zasada minimum mówi tyle, że wszystko ma swój początek.
Jest to bardziej widać na tej implikacji 2. W tej implikacji 2 to jest tak, że ja chcę udowodnić zasadę minimum ze słabej indukcji. Znaczy, nie, źle mówię. Tak, to bardziej taki klasyczny był ten dowód tutaj. Chcieliśmy, jak chcemy udowodnić zasadę silnej indukcji z tej fabrycznej zasady minimum, to patrzymy, gdzie dzieje się źle. Jeśli gdziekolwiek dzieje się źle, to gdzieś to zło się zaczyna. No, ale przed tym złem wszystko musiało być dobre. A jak wszystko do tego miejsca było dobre, to następne też musi być dobre.
Czyli to zło nie ma gdzie się zacząć. Żeby zrobić tę dwójkę, to trzeba to zrobić trochę inaczej. Ja myślę, żeby to robić tak, że ja udowodnię twierdzenie. Dla każdego n zachodzi takie tn. Tn mówi, że dla każdego dla każdego podzbiornicz naturalnych tak nie muszę zakładać dla każdego podzbiornicz naturalnych jeśli n należy do a to A posiada element najmniejszy. Po polsku minimum.
Minimum równa się element najmniejszy, nie mylić z elementem minimalnym. Dlaczego jest taka terminologia? Ponieważ matematycy Was nienawidzą. Jak dla każdego N udowodnimy takie zdanie, to będziemy zrobieni. Bo my chcemy udowodnić, że każdy niepusty zbiór ma minimum, każdy niepusty zbiór ma jakiś element. zbiorę niepusty zbiór, znajduję w nim n-a, stosuję to zdanie dla tego n-a i mam, że w tym zbiorze jest minimum. No to świetnie. Mam udowodnić takie coś. Mam zasadę indukcji, takiej słabej indukcji. To mi wystarczy. No to dowodzę.
T0, ono mówi, że co? Że każdy zbiór, który jest po zbiorem liczb naturalnych, który ma 0, posiada minimum. No raczej. Jak 0 należy do a, no to po prostu 0 jest minimum a. Lepiej się nie da, a 0 już jest w zbiorze. No to ja teraz chcę udowodnić to n plus 1. To n plus 1 mówi mi co? Dla każdego podzbioru liczb naturalnych. Jeśli n plus 1 należy do a, to istnieje minimum. Jak ja to chcę udowodnić?
Jak ja chcę to udowodnić? Jeśli n plus 1 należy do a. O, na przykład tak to zrobię. Dowolny podzbior liczb naturalnych, taki, że n plus 1 do niego należy. No to są dwa przypadki. jeśli 0 należy do a to jesteśmy zrobieni po prostu 0 jest minimum jeśli 0 nie należy do a to jak od każdego elementu a odejmę jedynkę to jest to po zbioru liczb naturalnych tak, bo nie wrzuciłem tej minus jedynki oraz n należy do zbioru a minus 1 więc więc co, więc jakieś alfa jest minimum zbioru a minus 1
Znaczy alfa należy do zbioru a minus 1 oraz dla każdego x, który należy do zbioru a minus 1 alfa jest mniejsze równe niż no to ja twierdzę, że alfa plus 1 jest równe minimum a bo po pierwsze z tego wynika, że alfa plus 1 należy do a jak należy do a to y minus 1 należy do a minus 1 więc wtedy alfa jest mniejsze równe niż alfa jest mniejsze równe niż y minus 1 czyli alfa plus 1 jest mniejsze równe y dla każdego y należącego do a czyli udowodniłem dwie rzeczy
Alfa plus 1 jest w zbiorze a oraz jest mniejsze równe niż każdy inny element zbioru a pokazałem minimum palca to samo rozumowanie można zrobić trochę eleganciej mówiąc, że tn tn mówi, że przykład mówiąc, że Tn mówi, że jeśli A ma cokolwiek ze zbioru od 1 do n, od 0 do n, to A posiada minimum. Więc tak, przekonaliśmy się, że ta zasada indukcji to jest tak naprawdę podstawowe prawo fizyki.
Tak podstawowa jak zasada minimum. Jest jeszcze taka szkoła, żeby najpierw zapostulować aksjomatycznie liczby rzeczywiste, dokładnie tak jak Wam opisałem, a potem wyróżnić liczby naturalne przez zasadę indukcji jako aksjomat. Jak powiedzieć, że to jest najmniejszy zbiór, który zawiera 0 oraz propaguje się o 1 w prawo. I wtedy to właśnie zasada minimum jest twierdzeniem. To ma pewne zalety i ma pewne wady. Na przykład ja udowodnię w ten sposób, że są co najwyżej jedne liczby rzeczywiste z dokładnością do izomorfizmu, ale nie udowodnię, że istnieją, bo ja skądś muszę wziąć te liczby naturalne, prędzej czy później, jak chcę konstruować matematykę.
Dlatego wolimy tę konstrukcję, że teoria mnogości produkuje liczby naturalne, algebra produkuje z nich liczby wymierne. a potem topologia z nich liczby rzeczywiste. Zobaczyliśmy, jak działają różne warianty indukcji. To zobaczymy jeszcze taki najbardziej odjechany wariant indukcji. Taki, który jest stajlerowany do konkretnego zadania, ale też bywa, że się go używa do innych. To będzie dowód nierówności między średnią geometryczną i arytmetyczną przez zwariowaną indukcję.
Twierdzenie mówi tyle, że jak ja mam n naturalnego, Tutaj dodatniego, bo dla zaroby to nie miało sensu. I mamy liczby, które będą nieujemne. Średnia arytmetyczna jest większa również niż średnia geometryczna. Dowodów tego twierdzenia jest mnóstwo. Moim ulubionym jest dowód, który przechodzi przez wypukłość.
Tylko dlatego trzeba mieć technologię. Tu pokażemy taki dowód z najmniejszym efortem. Wydaje się zrobić mniejszy. Zależy. Ja jestem w stanie pokazać dowód z trochę mniejszym efortem, ale jak mamy... Nie, nie, nie, trzeba jeszcze więcej technologii. Niezłe jest ten najwrozczyk, który jest. To się też daje zrobić taką zwykłą indukcją, ale tam trzeba wpaść na sztuczkę rachunkową. Tutaj sztuczką jest bardziej idea.
Idea jest taka, że my tego będziemy najpierw dowodzić dla n-ów, które są potęgą dwójki, a potem schodzić w dół. To znaczy najpierw twierdzimy słabszą wersję. To znaczy najpierw ustalenia uwagi będę sumował od najpierw to działa dla n-ów, które są w postaci 2 do k-tej. Pierwiastek 2 do k-tej razy iloczy.
I o ile to jest zdanie tn, to niech to się nazwie zdanie... No to jak ja to zrobię? Dla k-równego 0 to ma bardzo mało sensu, a i tak potem chcemy to zrobić dla k-równego 1. Dla k-równego to jest oczywiste, bo tu mam jedną liczbę przez 1 i tutaj mam pierwiastek pierwszego stopnia z tej liczby.
Dla k-równego 1 tu jest napisane, że A1 plus A2 przez 2 jest większe, równe niż pierwiastek drugiego stopnia w A1 razy A2. No a to jest znakomicie nam znana nierówność. Lewa strona minus prawa strona to jest jedna druga pierwiastek z A1 minus pierwiastek z A2. Teraz, jak ja chcę z PK udowodnić PK plus 1, to ja się i tak będę podpierał P1. Mogę twierdzić, że to jest słaba indukcja i P1 udowodnię na boku. Mogę twierdzić, że mocna indukcja, która korzysta z od P1 do PK minus 1, jak kto woli.
Zrobimy to tak, że jak ja mam a1 plus plus plus plus a do potęgi 2 do k plus pierwszej przez pierwszej, to to rozbijemy na dwa kawałki. Tu będzie suma pierwszej połowy składników, to jest 2 do k tej. Tu będzie drugie 2 do k tej składników, to jest 2 do k plus pierwszej. Tutaj jedynka jest na poziomie k, a tu jedynka jest na poziomie dwójki. To jeszcze ja tutaj podzielę przez ich lirbę. tutaj tak samo, jak bym zrobił wspólny mianownik to by wyszło 2 do k, czyli 2 razy mniej niż tu czyli jeszcze muszę uzupełnić mianownik skorzystam po prostu z pk tu ich jest 2 do k sztuk, tu też to tu mogę napisać pierwiastek stopnia 2 do k i tutaj tak samo tu jeszcze jest plus, prawda?
I teraz z p1 to jest suma dwóch rzeczy przez 2 to jest większe równo niż pierwiastek z iloczynu czyli tu mam pierwiastek z iloczynu Pierwszy ten pierwiastek to jest a1 razy razy To potęgi 1 przez 2 do k A ten drugi to jest i o czym pozostałych To jest tylko zupa iloczynowa W której pływają wszystkie a Z tą samą potęgą Tu są w potędze 1 przez 2 do k A potem jest jeszcze pierwiastek, czyli raz 1 drug To jest to co mieliśmy do powodu Ten krok indukcyjny to jest takie rozdrzewianie tego 2 do k Teraz co ja chcę zrobić teraz ja chcę udowodnić, że tn implikuje tn-1, tak?
To nie jest typo, to jest tn-1. I jak to zrobię? Jak ja to zrobię? Zapewne zrobię tak, że ja wezmę jakieś n-1 liczb. Ja bym chciał udowodnić takie coś. A ja mam tn, ja umiem odpalić tę nierówność na n liczbach.
Mam n-1, czyli skądś muszę wziąć skądś muszę wziąć ostatnie. No więc, czy ja pamiętam jak to się dowodzi tak średnio, ale spróbujmy niech to się nazywa g od średniej geometrycznej no to ja teraz spróbuję napisać tn dla ciągu który składa się z tego całego towarzystwa oraz g to już jest n inputów to jak mi to wyjdzie? wyjdzie mi a1++++ plus a n-1 plus g przez n większe równe niż I teraz tu będzie pierwiastek n tego stopnia z a1 razy razy an-1 razy g.
Może tak nie wyjdzie, zaraz zobaczymy. No bo, spójrzcie, tu jest jedna nta, a tu jest iloczyn wszystkich a. Iloczyn wszystkich a to jest gden minus pierwszej. A, to wyjdzie w ten sposób. Dobrze pamiętam. I tu jest dokładnie n sztuk. I tu jest dokładnie jedna nta, czyli tu jest dokładnie g.
Morał? Tak samo jak dopisanie do n-1 liczb x średniej arytmetycznej nie zmieni średniej arytmetycznej całości, tak samo dopisanie do tych n-1 liczb x średniej geometrycznej nie zmieni średniej geometrycznej całego ciągu. No więc jak mamy taki napis, to już w ogóle wygraliśmy, bo tu jest napisane, że suma a jest większa równa niż ng-g. pomnożę tutaj, odejmę 1g czyli jak podzielę przez n-1 i już, dokładnie to co mieliśmy udowodnić czyli umiemy pójść do przodu dowolnie daleko i umiemy się cofać jakby ktoś chciał takiego bardzo, bardzo dowodu takiego, żeby teściowa z białą rękawiczką nie znalazła kurzu to jeszcze trzeba udowodnić, że możemy pójść dowolnie daleko na szczęście nierówność Bernoulliego nam mówi że 1 plus 1 to k tej jest większe niż 1 plus 1 razy k
I w związku z powyższym w związku z powyższym jeśli ja chcę coś udowodnić dla n to jak ja robię ja mówię, że niech n będzie jakieś ustalone wtedy wtedy 2 do n tej jest większe, równe niż 1 plus n w szczególności większe, równe niż n Z pierwszej części t2 do n-tej jest prawdziwe.
Zdanie to jest to samo, co klib, że zdanie jest prawdziwe, więc ja często piszę z czegoś tam jakieś zdanie. No to teraz przez indukcję t2 do n-tej minus j jest prawdziwe. Jest zawsze prawdą to lub j jest większy niż 2 do n-tej. Takie zdanie ewidentnie jest prawdziwe dla j równego 0, propagacja o 1 w prawo to tutaj tutaj to jest cofanie się z indeksem t a to jest warunek po to żeby się nie cofnąć poniżej 0 j równego 2 do n tej minus n który jak widzimy jest większy równe 0, jakie?
I mniejsze niż 2 do n tej zachodzi 2 do n tej minus 2 do n tej minus n równa się t to jest tylko tak przesadnie wymęczone mieć pewność, że to nie zostało nigdzie oszukane. Tak w szczególności tu korzystamy z nierówności Bernoulliego, żeby się przekonać, że potęgi dwójki zajdą dowolnie daleko. To niby jest oczywiste, ale kiedyś trzeba to udowodnić, na przykład teraz.
Także tak, to jest w zasadzie cała indukcja, którą, wszystkie sposoby stosowania indukcji, które powinniście znać przynajmniej na tym etapie edukacji. Oczywiście ich jest dużo więcej, natomiast każdy się w jakiś sposób sprowadza do zasady minimum. Tak samo można robić indukcję po kracie. Także, jak jest krata, to jak ja wiem, że ja mogę, że ja z tego punktu mogę pójść dowolnie w tę stronę, albo dowolnie w tę stronę, oraz, że z tych dwóch mogę zrobić ten, to też to udowodni dla całej kraty.
Natomiast to jest głupie, bo po prostu się dowodzi kolejne po takich kreseczkach. To jest wszystko jednowmierowa indukcja. Prawdziwy czadu to jest indukcja poza skończona, o której być może coś usłyszycie na podstawach matematyki. Indukcja poza skończona służy do tego, że jak już tak dojdziemy do nieskończoności takim i tak dalej, to potem, żeby zrobić taką jeszcze jedną nieskończoność i potem jeszcze drugą nieskończoność, potem jeszcze trzecią i tak dalej. Taka żonglerka nieskończonościami się wydaje trochę szemrana, ale temu się daje nadać formalne rany. To myślę, że tyle.