msleziak.com

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.

Veľa príkladov takejto indukcie môžete nájsť online, ak skúsite hľadať názvy Cauchy induction, Foward-Backward induction, Upward-Downward induction.

Príklad, na ktorom sa jej použitie často ilustruje, je nerovnosť medzi aritmetickým a geometrickým priemerom. Takže môžete skúsiť hľadať túto nerovnosť spolu s jedným, druhým či tretím názvom.

Ako obvykle, pridám aj nejaké linky:

• AoPS wiki: Cauchy Induction
• How does backwards induction work to prove a property for all naturals? - Mathematics Stack Exchange
• Wikipédia: Inequality of arithmetic and geometric means § Proof by Cauchy using forward–backward induction (current revision)
• MathOverflow: Is Cauchy induction used for proofs other than for AM–GM?

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.) Sforumulujem, čo ideme dokazovať:

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: Dôkaz: $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: Hint 2: Dôkaz: $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: Hint 2: Dôkaz: