9. Kódy Musím Stláčať vzorové riešenie

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í \[\label{zaklad} a_n+1\le a_{n-1}(1+\tfrac{1}{n}). \tag{1}\] Dokážeme, že potom existuje také \(l\), že \(a_{l} \le 0\). Odteraz, keď budeme niečo hovoriť o premennej \(n\), tak budeme hovoriť iba o tých \(n\), ktoré sú väčšie ako \(k\).

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 ¹, 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é \(a_i\) 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=\{b_i\}_{i=k}^\infty\) a \(C=\{c_i\}_{i=k}^\infty\) sú také postupnosti, že \(b_k=c_k>0\) a pre obe postupnosti platí (1), avšak pre postupnosť \(B\) sú všetky nerovnosti dosahované s rovnosťou. Ukážeme, že potom \(\forall n>k\) platí \(c_n\le b_n\). Opäť sporom, predpokladajme, že existuje také \(m\), pre ktoré \(c_m > b_m\) 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ť: \[c_{m-1}(1+\tfrac{1}{m})-1\ge c_m > b_m = b_{m-1}(1+\tfrac{1}{m})-1.\] Keď sa pozrieme na krajné strany série nerovností, tak po použití jednoduchých ekvivalentných úprav dostávame \(c_{m-1}>b_{m-1}\), čo je spor s tým, že \(m\) bolo najmenšie číslo s platnosťou danej nerovnosti.

Stačí nám teda ukážať, že v postupnosti \(B\) existuje nekladné číslo. Vyjadrime si teraz člen \(b_n\) len pomocou \(b_k\): ² \[\begin{aligned} b_n &= b_{n-1}\frac{n+1}{n}-1=\left(b_{n-2}\frac{n}{n-1}-1\right)\frac{n+1}{n}-1=b_{n-2}\frac{n+1}{n-1}-\frac{n+1}{n}-\frac{n+1}{n+1}=\\&=\left(b_{n-3}\frac{n-1}{n-2}-1\right)\frac{n+1}{n-1}-\frac{n+1}{n}-\frac{n+1}{n+1}=b_{n-3}\frac{n+1}{n-2}-\frac{n+1}{n-1}-\frac{n+1}{n}-\frac{n+1}{n+1}= \dots \\ \dots &= b_k\frac{n+1}{k+1}-\sum_{i=k+2}^{n+1} \frac{n+1}{i}.\end{aligned}\]

Sledujme teraz rozdiel \(b_{n}\) a \(b_{n-1}\): \[\begin{aligned} b_n-b_{n-1}&=b_k\frac{n+1}{k+1}-\sum_{i=k+2}^{n+1} \frac{n+1}{i} -b_k\frac{n}{k+1}+\sum_{i=k+2}^{n} \frac{n}{i} = \frac{b_k}{k+1}-1-\sum_{i=k+2}^{n} \frac{1}{i}=\frac{b_k}{k+1}-1+\sum_{i=1}^{k+1} \frac{1}{i}-\sum_{i=1}^{n} \frac{1}{i}.\end{aligned}\]

Postupnosť \(S=\{\sum_{i=1}^{n} \frac{1}{i}\}_{i=1}^\infty\) 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: \(\underset{n \xrightarrow{}\infty}{lim} \sum_{i=1}^{n} \frac{1}{i}= +\infty\), alebo, kto nevie čo je limita, tak pre všetky \(c \in \mathbb{R}\) existuje také \(n_0 \in \mathbb{N}\), že pre všetky \(n>n_0\): \(\sum_{i=1}^{n} \frac{1}{i} > c\).

My si ukážeme jeden z nich (asi najznámejší). ³ Myšlienku si ukážeme na ôsmom člene postupnosti: \[\begin{aligned} &1+\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{4}+\tfrac{1}{5}+\tfrac{1}{6}+\tfrac{1}{7}+\tfrac{1}{8}>\\&1+\tfrac{1}{2}+\tfrac{1}{4}+\tfrac{1}{4}+\tfrac{1}{8}+\tfrac{1}{8}+\tfrac{1}{8}+\tfrac{1}{8}=1+1/2+1/2+1/2=\tfrac{3+2}{2}. \end{aligned}\] Vo všeobecnosti (ľahko možno uvidieť): \[1+\tfrac{1}{2}+\tfrac{1}{3}+\dots+\tfrac{1}{2^m}>\tfrac{m+2}{2}.\] Keďže postupnosť \(S\) je rastúca, tak touto hodnotou sú ohraničené aj všetky ďalšie členy \(S\) po nasledujúcu mocninu dvojky. Vidíme teda, že postupnosť rastie nad všetky medze.

Vrátiac sa späť k našej úlohe, ukázali sme, že rozdiel \(b_n-b_{n-1}=\frac{b_k}{k+1}-1+\sum_{i=1}^{k+1} \frac{1}{i}-\sum_{i=1}^{n} \frac{1}{i}\) (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ť \(b_0\), 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.