Zadanie
Potom, čo Kubko úspešne zdolal príšeru, ostáva mu len jediné. Musí zadať do trezora s drahokamom správny kód – postupnosť čísel. Aby sa trezor odomkol, musia medzi zadávanými číslami platiť správne nerovnosti.
Majme ľubovoľnú postupnosť kladných reálnych čísel a0, a1, a2, … Dokážte, že nerovnosť 1+an>an−1(1+1n)
Pri takomto type úloh sa nám celkom ponúka to dokázať sporom – budeme predpokladať, že nerovností typu > je v danej postupnosti iba konečný počet. Jediný predpoklad, ktorý v úlohe máme, je, že sa jedná o postupnosť kladných čísel, preto jediný spor, ktorý môžeme dostať je, že v postupnosti (v prípade platnosti opačného tvrdenia k zadaniu) budú nekladné čísla.
Ak je iba konečný počet nerovností >, potom určite existuje nejaká, ktorá je „najďalej“ – t. j. existuje také k, že pre všetky n>k platí an+1≤an−1(1+1n).
Keď niečo chceme dokázať, často sa nám oplatí – ak nám to daná úloha ponúka – uvažovať najhorší možný prípad, aký pre nás môže nastať. Ak dokážeme, že tvrdenie je splnené pre najhorší prípad a zároveň že daný prípad je naozaj najhorší v zmysle platnosti nášho tvrdenia 1, tak sme vyhrali.
Intuitívne, najhorší prípad, aký môže nastať, je, keď pre všetky n nastáva v nerovnosti (1) rovnosť. Pretože potom jednotlivé ai budú „najväčšie možné“, a teda sa najviac budú brániť nekladnosti. Toto samozrejme musíme dokázať nejako poriadne, lebo intuícia môže často klamať. Ukážeme to nasledovne:
Nech B={bi}∞i=k a C={ci}∞i=k sú také postupnosti, že bk=ck>0 a pre obe postupnosti platí (1), avšak pre postupnosť B sú všetky nerovnosti dosahované s rovnosťou. Ukážeme, že potom ∀n>k platí cn≤bn. Opäť sporom, predpokladajme, že existuje také m, pre ktoré cm>bm a nech toto m je najmenšie možné s danou vlastnosťou (kombinácia sporu a extremálneho princípu je opäť veľmi silný a spoľahlivý dôkazový postup). Potom, vďaka (1) môžeme písať: cm−1(1+1m)−1≥cm>bm=bm−1(1+1m)−1.
Stačí nám teda ukážať, že v postupnosti B existuje nekladné číslo. Vyjadrime si teraz člen bn len pomocou bk: 2 bn=bn−1n+1n−1=(bn−2nn−1−1)n+1n−1=bn−2n+1n−1−n+1n−n+1n+1==(bn−3n−1n−2−1)n+1n−1−n+1n−n+1n+1=bn−3n+1n−2−n+1n−1−n+1n−n+1n+1=……=bkn+1k+1−n+1∑i=k+2n+1i.
Sledujme teraz rozdiel bn a bn−1: bn−bn−1=bkn+1k+1−n+1∑i=k+2n+1i−bknk+1+n∑i=k+2ni=bkk+1−1−n∑i=k+21i=bkk+1−1+k+1∑i=11i−n∑i=11i.
Postupnosť S={∑ni=11i}∞i=1 sa nazýva harmonický rad a existuje nespočetné množstvo elegantných, aj neelegantných dôkazov, že táto postupnosť diverguje, t. j., intuitívne povedané, že členy postupnosti S rastú s rastúcim n nad všetky medze až do samého neba. Trochu formálnejšie: limn→∞∑ni=11i=+∞, alebo, kto nevie čo je limita, tak pre všetky c∈R existuje také n0∈N, že pre všetky n>n0: ∑ni=11i>c.
My si ukážeme jeden z nich (asi najznámejší). 3 Myšlienku si ukážeme na ôsmom člene postupnosti: 1+12+13+14+15+16+17+18>1+12+14+14+18+18+18+18=1+1/2+1/2+1/2=3+22.
Vrátiac sa späť k našej úlohe, ukázali sme, že rozdiel bn−bn−1=bkk+1−1+∑k+1i=11i−∑ni=11i (kde prvé tri členy sú iba konštanta) bude klesať a klesať, až raz bude určite záporný a aj potom bude stále len klesať a klesať. To je ale rozdiel dvoch po sebe idúcich členov postupnosti B. Teda postupnosť B, bez ohľadu na veľkosť b0, raz padne pod nulu. Teda aj postupnosť C, čo je len posunutá postupnosť A, raz padne pod nulu, čo je spor s tým, že naša postupnosť je nezáporná. A to je koniec.
Formálne, nech P je predpoklad našej úlohy, nech B je nejaký prípad a nech pre všetky možné prípady C platí (P⇒B)⇒C. Potom (P⇒B)⇒(P⇒C).↩
Pre tých, čo nepoznajú ten zvláštny symbol, ktorý sa nachádza na konci nasledujúceho odvodzovania, odporúčam: https://cs.wikipedia.org/wiki/Sumace↩
https://cs.wikipedia.org/wiki/Harmonick%C3%A1_%C5%99ada↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.