Začiatkom ZS zvykneme prejsť aj nejaké príklady týkajúce sa matematickej indukcie.
Pridám sem jeden (azda aspoň trochu zaujímavý) doplnok.
Cauchyho indukcia funguje zhruba takto:
Overíme, že tvrdenie platí pre $n=1$.
Ukážeme, že ak tvrdenie platí pre $n$ tak platí aj pre $2n$.
Ukážeme, že ak tvrdenie platí pre $n>1$, tak platí aj pre $n-1$.
Prvé dve časti nám zaručia platnosť pre všetky čísla tvaru $n=2^k$. A nie je ťažké rozmyslieť si, že pomocou tretej podmienky už potom vieme dostať platnosť tvrdenia pre všetky prirodzené čísla.
Veľmi podobne by sme mohli uvažovať aj ak by sme namiesto $n=2^k$ vedeli overiť platnosť tvrdenia pre inú nekonečnú množinu prirodzených čísel.
Keď už som teda viackrát spomenul ako typický príklad použitia Cauchyho indukcie AM-GM nerovnosť, tak by som tu mohol naznačiť jej dôkaz. (Aj keď ho určite nájdete na veľa iných miestach.)
Aspoň trochu sa pokúsim urobiť to tak, že tu máte dôkaz nejako naznačený - takže ak si to budete chcieť vyskúšať sami. (Aspoň v prípade, že ste tento dôkaz zatiaľ nevideli niekde inde.) Možno vám to môže pomôcť začať. Ale kým si neodkryjete spoiler, tak nevidíte celé riešenie.
Samozrejme, nijako nezaškodí porozmýšľať aj nad tým, či sa táto nerovnosť dá dokázať nejako inak. (Alebo vyskúšať, či použitie "obvyklej" indukcie a nie Cauchyho indukcie by bolo oveľa ťažšie.)
Spoiler:
Skúsim pridať aj nejaké linky, kde by sa mohli dať nájsť aj iné dôkazy:
Nech $x_1,x_2,\dots,x_n\ge0$ sú nezáporné reálne čísla. Potom platí:
$$\frac{x_1+x_2+\dots+x_n}n \ge \sqrt[n]{x_1\cdot x_2\cdots x_n}.$$
Dá sa dokázať aj to, že rovnosť nastane iba v prípade $x_1=x_2=\dots=x_n$. (T.j. ak sa aspoň jedno z čísel líši od ostatných, tak je nerovnosť ostrá.)
Ja tu budem dokazovať iba platnosť uvedenej nerovnosti. (Nebudem sa zaoberať tým, kedy nastane rovnosť. Samozrejme, môžete sa nad tým skúsiť zamyslieť.)
Ľavá strana nerovnosti je aritmetický priemer čísel $x_1,x_2,\dots,x_n$, pravá strana je ich geometrický priemer.
$1^\circ$ Pre $n=1$ niet čo dokazovať, je to iba nerovnosť $x_1\le x_1$.
Oplatí sa nám dokázať nerovnosť pre $n=2$, bude sa nám hodiť v ďalšej časti dôkazu.
$$\frac{x_1+x_2}2 \ge \sqrt{x_1x_2}$$
Veľmi naivný hint:
Spoiler:
Vyskúšať nejaké ekvivalentné úpravy až kým nezbadáme, že sme dostali nerovnosť, ktorá určite platí.
Dôkaz:
Spoiler:
\begin{align*}
\frac{x_1+x_2}2 &\ge \sqrt{x_1x_2}\\
x_1+x_2 &\ge 2\sqrt{x_1x_2}\\
(x_1+x_2)^2 &\ge 4x_1x_2\\
x_1^2+2x_1x_2+x_2^2 &\ge 4x_1x_2\\
x_1^2-2x_1x_2+x_2^2 &\ge 0\\
(x_1-x_2)^2 &\ge 0
\end{align*}
Uvedené úpravy sú ekvivalentné. (Na jednom mieste sme použili umocnenie na druhú. Ale ak sú obe strany nezáporné, tak takáto úprava je ekvivalentná. A my máme v predpokladoch, že $x_1,x_2\ge0$.)
Zistili sme, že dokazovaná nerovnosť je ekvivalentná s $(x_1-x_2)^2 \ge 0$. Táto nerovnosť určite platí - druhá mocnina reálneho čísla je vždy nezáporná.
$2^\circ$ Teraz chcem skúsiť dokázať, že ak tvrdenie platí pre $n$ tak platí aj pre $2n$.
T.j. predpokladáme platnosť rovnosti
$$\frac{x_1+x_2+\dots+x_n}n \ge \sqrt[n]{x_1\cdot x_2\cdots x_n}$$
pre ľubovoľné $x_1,\dots,x_n\ge0$.
A chceli by sme dokázať, že pre nezáporné čísla platí aj
$$\frac{x_1+x_2+\dots+x_{2n}}{2n} \ge \sqrt[2n]{x_1\cdot x_2 \cdots x_{2n}}.$$
Hint 1:
Spoiler:
Dajú sa výrazy v tejto nerovnosti nejako rozumne rozdeliť?
Hint 2:
Spoiler:
Pomôže, ak si dokazovanú nerovnosť prepíšeme takto?
$$\frac{x_1+\dots+x_n+x_{n+1}+\dots+x_{2n}}{2n} \ge \sqrt[2n]{x_1\cdots x_n x_{n+1} \cdots x_{2n}}$$
Dôkaz:
Spoiler:
\begin{align*}
\frac{x_1+\dots+x_n+x_{n+1}+\dots+x_{2n}}{2n}
&\ge \sqrt{\frac{x_1+\dots+x_n}n \cdot \frac{x_{n+1}+\dots+x_{2n}}n} \\
&\ge \sqrt{ \sqrt[n]{x_1\cdots x_n} \cdot \sqrt[n]{x_{n+1} \cdots x_{2n}} } \\
&= \sqrt[2n]{x_1\cdots x_n x_{n+1} \cdots x_{2n}}
\end{align*}
V jednotlivých krokoch sme vlastne použili AM-GM nerovnosť pre dve čísla -- konkrétne pre $\frac{x_1+\dots+x_n}n$ a $\frac{x_{n+1}+\dots+x_{2n}}n$. (T.j. tu používame prípad $n=2$, ktorý sme overili na začiatku.)
A potom v ďalšom kroku sme použili AM-GM nerovnosť pre $n$-čísel - jednak pre čísla $x_1,\dots,x_n$ a súčasne pre čísla $x_{n+1},\dots,x_{2n}$.
\begin{align*}
\frac{x_1+x_2+\dots+x_n}n &\ge \sqrt[n]{x_1\cdot x_2\cdots x_n}\\
\frac{x_{n+1}+x_{n+2}+\dots+x_{2n}}n &\ge \sqrt[n]{x_{n+1}\cdot x_{n+2}\cdots x_{2n}}
\end{align*}
Potom už len zostávalo upraviť výraz, ktorý nám vyšiel na pravej strane.
$3^\circ$ Ešte by sme chceli ukázať, že ak tvrdenie platí pre $n$, tak platí aj pre ľubovoľné $k\le n$.
(Vlastne by nám stačilo z platnosti pre $n$ dokázať platnosť pre $(n-1)$. Ale argument pre ľubovoľné menšie $k$ je v podstate rovnaký.)
T.j. predpokladáme, že platí $$\frac{x_1+x_2+\dots+x_n}n \ge \sqrt[n]{x_1\cdot x_2\cdots x_n}$$ a chceli by sme dostať pre $k\le n$ platnosť analogickej nerovnosti
$$\frac{x_1+x_2+\dots+x_k}k \ge \sqrt[k]{x_1\cdot x_2\cdots x_k}$$
Hint 1:
Spoiler:
Vedeli by ste k číslam $x_1,x_2,\dots,x_k$ pridať nejaké ďalšie čísla takým spôsobom, že to nezmení aritmetický priemer?
Hint 2:
Spoiler:
Ak si označím ako $a$ aritmetický priemer čisel $x_1,x_2,\dots,x_k$, ako bude vyzerať aritmetický priemer čísel $x_1,x_2,\dots,x_k,a$? (T.j. k pôvodným $k$ číslam som ešte pridal $a$.)
Dôkaz:
Spoiler:
Označme ako $a$ aritmetický priemer čísel $x_1,x_2,\dots,x_k$. Všimnime si, že platí
$$a=\frac{x_1+\dots+x_k}k=\frac{x_1+\dots+x_k+(n-k)a}n,$$
t.j. na to isté číslo ma môžem pozerať aj ako na aritmetický priemer čísel $x_1,x_2,\dots,x_k,x_{k+1},\dots,x_n$, kde $x_{k+1}=\dots=x_n=a$. (T.j. pridal som $(n-k)$-krát $a$-čko.)
Teraz už mám $n$ čísel, pre ne môžem použiť AM-GM nerovnosť.
\begin{align*}
a&=\frac{x_1+\dots+x_k}k \\
&=\frac{x_1+\dots+x_k+(n-k)a}n\\
&\ge\sqrt[n]{x_1\cdots x_k \cdot a^{n-k}}
\end{align*}
Po umocnení dostanem
$$a^n \ge x_1\cdots x_k \cdot a^{n-k},$$
čo môžem upraviť ako
$$a^k \ge x_1\cdots x_k.$$
Dostal som tak nerovnosť
$$\frac{x_1+\dots+x_k}k = a \ge \sqrt[k]{x_1\cdots x_k}.$$
To je presne AM-GM nerovnosť pre čísel $x_1,\dots,x_k$.