Logika a důkazy. Matematická indukce

1. Je-li $n$ sudé, lze psát $n = 2k$ pro nějaké $k \in \Z$, takže $n+1 = 2k+1$ je liché – implikace platí. Obráceně: je-li $n+1$ liché, je $n+1 = 2k+1$, tedy $n = 2k$ je sudé. Platí tedy i obrácená implikace a lze mluvit o ekvivalenci.
2. Rovnostranný trojúhelník má všechny tři strany stejné, tím spíše dvě – je tedy i rovnoramenný. Obrácená implikace neplatí: protipříkladem je trojúhelník se stranami $2$, $2$, $3$, který je rovnoramenný, ale nikoli rovnostranný.
3. Formulace „k získání zápočtu je třeba chodit na cvičení“ říká, že docházka je nutnou podmínkou zápočtu, tedy $A \implies B$. Obrácená implikace by znamenala, že docházka zápočet už zaručuje, což zjevně neplatí – lze chodit na cvičení a zápočet přesto nezískat.

□

Označme

$$\begin{aligned} J & = \{\textit{Jaderka patří mezi těžší fakulty ČVUT}\}, \\ P & = \{\textit{Je dobrý nápad učit se všechno na poslední chvíli}\}. \end{aligned}$$

Zadaná implikace má tvar $J \implies \neg P$. Obměněná implikace k $A \implies B$ je $\neg B \implies \neg A$, v našem případě tedy

$$\neg(\neg P) \implies \neg J, \qquad \text{tj.} \qquad P \implies \neg J,$$

slovy: „Je-li dobrý nápad učit se všechno na poslední chvíli, pak Jaderka nepatří mezi těžší fakulty ČVUT.“ Tomu odpovídají možnosti C a E (liší se jen slovním obratem).

Zbylé možnosti A, B a D vyjadřují shodně implikaci $\neg P \implies J$, což je implikace obrácená – ta s původní implikací ekvivalentní není.

□

Sestrojíme pravdivostní tabulku:

$A$	$B$	$A \implies B$
$0$	$0$	$1$
$0$	$1$	$1$
$1$	$0$	$0$
$1$	$1$	$1$

Z tabulky plyne, že se jedná výhradně o poslední řádek této tabulky, kde současně $\nu(A) = 1$ a $\nu(A \implies B) = 1$. V tomto řádku vidíme, že $\nu(B) = 1$.

□

$\blacktriangleright$ 1. způsob. Vyjdeme z přirozeného smyslu implikace a disjunkce. Začneme třetím výrokem, který nám nabízí dva (nevýlučné) případy: na přednášce bude Jan nebo Mikuláš.

Pokud půjde Mikuláš, pak z prvního výroku máme, že bude poslouchat přednášku i Vojtěch. Může Jan nejít na přednášku v tomto případě? Druhý výrok říká, že pak by na přednášku nešel Vojtěch, ale ten už tam sedí. Proto všichni tři budou na přednášce.

Pokud půjde Jan, u druhého výroku levá část implikace je nepravdivá. Pak Vojtěch může jít na přednášku nebo ne. Mikuláš nyní svobodně rozhoduje sám. Ale pokud se rozhodne jít, tak se k němu připojí i Vojtěch kvůli první podmínce. Pokud Mikuláš bude mít jiné plány, pak se Vojtěch stále může rozhodnout jít či nejít. Máme tedy následující možnosti: 1) jde na přednášku pouze Jan; 2) jdou na přednášku Jan, Mikuláš, a tedy i Vojtěch; 3) jdou Jan a Vojtěch.

$\blacktriangleright$ 2. způsob. Sestavíme výroky:

Určíme výrokové formule podle zadaných podmínek:

Sestavíme pravdivostní tabulku podle zadaných podmínek:

$J$	$M$	$V$	$\mathcal{A}$	$\neg J$	$\neg V$	$\mathcal{B}$	$\mathcal{C}$	$\mathcal{A} \wedge \mathcal{B} \wedge \mathcal{C}$
$0$	$0$	$0$	$1$	$1$	$1$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$1$	$0$	$0$	$1$	$0$
$0$	$1$	$0$	$0$	$1$	$1$	$1$	$0$	$0$
$0$	$1$	$1$	$1$	$1$	$0$	$0$	$1$	$0$
$1$	$0$	$0$	$1$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$1$	$1$	$0$	$0$	$1$	$1$	$1$
$1$	$1$	$0$	$0$	$0$	$1$	$1$	$1$	$0$
$1$	$1$	$1$	$1$	$0$	$0$	$1$	$1$	$1$

Teď koukněme na jedničky v posledním sloupci. Máme tedy tři možnosti: 1) na přednášku půjde pouze Jan; 2) na přednášku půjde Jan a Vojtěch; 3) na přednášku půjdou všichni tři.

□

Připomeňme definice. Funkce $h$ je lichá, jestliže je její definiční obor souměrný podle nuly a pro každé $x$ z něj platí $h(-x) = -h(x)$; je sudá, jestliže za téhož předpokladu platí $h(-x) = h(x)$.

Nechť tedy $f$ a $g$ jsou liché. Jejich součin $f \cdot g$ je definován na průniku obou definičních oborů, který je opět souměrný podle nuly. Pro každé $x$ z tohoto průniku platí

$$(f \cdot g)(-x) = f(-x) \cdot g(-x) = \bigl(-f(x)\bigr) \cdot \bigl(-g(x)\bigr) = f(x) \cdot g(x) = (f \cdot g)(x),$$

kde jsme ve druhé rovnosti použili lichost obou funkcí a ve třetí to, že součin dvou záporných znamének dá znaménko kladné.

Funkce $f \cdot g$ tedy splňuje definici sudé funkce, což jsme chtěli dokázat.

□

Označme $A$ = {$n^2$ je dělitelné třemi} a $B$ = {$n$ je dělitelné třemi}. Místo implikace $A \implies B$ dokážeme ekvivalentní obměněnou implikaci $\neg B \implies \neg A$, tedy tvrzení: není-li $n$ dělitelné třemi, není třemi dělitelné ani $n^2$.

Nechť tedy $n$ není dělitelné třemi. Podle věty o dělení se zbytkem dává $n$ po dělení třemi zbytek $1$, nebo $2$; rozlišíme proto dva případy (v obou je $k \in \Z$, $k \geq 0$).

1. Je-li $n = 3k+1$, pak

   $$n^2 = 9k^2 + 6k + 1 = 3\left(3k^2+2k\right) + 1,$$

   takže $n^2$ dává po dělení třemi zbytek $1$.

2. Je-li $n = 3k+2$, pak

   $$n^2 = 9k^2 + 12k + 4 = 3\left(3k^2+4k+1\right) + 1,$$

   takže $n^2$ dává po dělení třemi opět zbytek $1$.

V obou případech je zbytek nenulový, tedy $n^2$ není dělitelné třemi. Tím je obměněná implikace dokázána, a s ní i tvrzení původní.

□

Předpokládejme pro spor, že prvočísel je jen konečně mnoho, a označme je všechna

$$p_1, \ p_2, \ \dots, \ p_n.$$

Uvažujme číslo

$$N = p_1 p_2 \cdots p_n + 1.$$

Zřejmě $N > 1$, takže $N$ má alespoň jednoho prvočíselného dělitele; označme jej $p$. Podle našeho předpokladu je $p$ jedním z čísel $p_1, \dots, p_n$, a tedy $p$ dělí i součin $p_1p_2\cdots p_n$.

Pak ale $p$ dělí rozdíl

$$N - p_1p_2\cdots p_n = 1,$$

což je spor: žádné prvočíslo (které je z definice větší než $1$) nemůže dělit jedničku.

Předpoklad, že prvočísel je konečně mnoho, tedy vede ke sporu. Prvočísel je proto nekonečně mnoho.

□

Sestrojíme pravdivostní tabulku pro všech osm kombinací hodnot výroků $A$, $B$, $C$:

$A$	$B$	$C$	$A \implies B$	$B \implies C$	$A \implies C$
$0$	$0$	$0$	$1$	$1$	$1$
$0$	$0$	$1$	$1$	$1$	$1$
$0$	$1$	$0$	$1$	$0$	$1$
$0$	$1$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$0$
$1$	$0$	$1$	$0$	$1$	$1$
$1$	$1$	$0$	$1$	$0$	$0$
$1$	$1$	$1$	$1$	$1$	$1$

Oba předpoklady jsou současně pravdivé právě ve čtyřech řádcích – v prvním, druhém, čtvrtém a osmém. V každém z nich má poslední sloupec hodnotu $1$, tedy $A \implies C$ je pravda. Tím je pravidlo dokázáno.

□

Označme

$$\begin{aligned} S & = \{\textit{Kniha $X$ je v souladu s trestním zákoníkem}\}, \\ Z & = \{\textit{Kniha $X$ je zbytečná}\}, \\ \check{S} & = \{\textit{Kniha $X$ je škodlivá}\}, \\ \check{C} & = \{\textit{Knihu $X$ čteme}\}. \end{aligned}$$

Předpoklady zní

$$S \implies Z, \qquad \neg S \implies \check{S}, \qquad \left(Z \vee \check{S}\right) \implies \neg\check{C}.$$

Podle zákona vyloučeného třetího platí $S \vee \neg S$. Rozlišíme tedy dva případy:

• Je-li $S$ pravda, plyne z prvního předpokladu $Z$, tedy platí i $Z \vee \check{S}$.
• Je-li $S$ nepravda, plyne z druhého předpokladu $\check{S}$, tedy opět platí $Z \vee \check{S}$.

V obou případech tedy platí $Z \vee \check{S}$ a ze třetího předpokladu podle pravidla modus ponens (příklad 4.4) dostáváme $\neg\check{C}$: knihu $X$ opravdu nečteme.

□

Označme jednotlivé výroky:

$$\begin{aligned} M &= \{\textit{Ministr bude vysekán z žaloby}\},\\ A &= \{\textit{Svědek $A$ bude zastrašen}\},\\ B &= \{\textit{Soudce $B$ bude podplacen}\},\\ C &= \{\textit{Osoba $C$ bude uvězněna}\},\\ F &= \{\textit{Firma $F$ bude obsazena}\},\\ E &= \{\textit{Firma $F$ získá zakázku $E$}\},\\ D &= \{\textit{Osoba $D$ bude zabita}\}. \end{aligned}$$

Zadání dává tyto implikace:

$$M \implies (A \vee B), \qquad A \implies C, \qquad B \implies (F \wedge E), \qquad C \implies D, \qquad F \implies D.$$

Předpokládejme, že cíl $M$ nastane. Pak platí $A \vee B$ a rozlišíme dva případy:

• Platí-li $A$, pak podle tranzitivity implikace z platnosti implikací $A \implies C$ a $C \implies D$ vyplývá platnost výroku $D$.
• Platí-li $B$, pak z třetí implikace platí $F \wedge E$, tedy zejména $F$, a odtud $F \implies D$, tedy opět $D$.

V obou případech dostáváme $D$. Celkem tedy $M \implies D$: ano, strana Práce a mír se ke svému cíli neobejde bez trestného činu – zabití osoby $D$.

□

Označme $A$ = {$A$ je vinen}, $B$ = {$B$ je vinen}, $C$ = {$C$ je vinen}. Jednotlivé výpovědi pak zní

$$\mathcal{V}_A \equiv B \wedge \neg C, \qquad \mathcal{V}_B \equiv (A \implies C), \qquad \mathcal{V}_C \equiv \neg C \wedge (A \vee B).$$

1. Předpokládejme, že platí všechny tři výpovědi. Z $\mathcal{V}_A$ (nebo z $\mathcal{V}_C$) plyne pravdivost výroku $\neg C$. Kdyby platilo $A$, dala by $\mathcal{V}_B$ současně pravdivost výroku $C$, což je spor; tedy musí platit $\neg A$. Z $\mathcal{V}_C$ pak $A \vee B$ dává pravdivost $B$. Dostáváme možné pravdivostní hodnoty

   $$\nu(A) = 0, \qquad \nu(B) = 1, \qquad \nu(C) = 0,$$

   při kterých jsou opravdu všechny tři výpovědi pravdivé. Pachatelem je v tomto případě $B$.

2. Dosadíme $\nu(A) = \nu(B) = \nu(C) = 0$:

   $$\nu(\mathcal{V}_A) = 0 \wedge 1 = 0, \qquad \nu(\mathcal{V}_B) = (0 \implies 0) = 1, \qquad \nu(\mathcal{V}_C) = 1 \wedge 0 = 0.$$

   Křivě tedy vypovídaly osoby $A$ a $C$, zatímco $B$ mluvil pravdu.

3. Nyní hledáme ohodnocení, pro které je výpověď každé osoby pravdivá právě tehdy, když je tato osoba nevinná, tedy

   $$\mathcal{V}_A \iff \neg A, \qquad \mathcal{V}_B \iff \neg B, \qquad \mathcal{V}_C \iff \neg C.$$

   Postupným probráním všech osmi možností (nebo úvahou) zjistíme, že vyhovuje jediná trojice

   $$\nu(A) = 1, \qquad \nu(B) = 0, \qquad \nu(C) = 1.$$

   Ověření: $\nu(\mathcal{V}_A) = 0 \wedge 0 = 0$ a $\nu(\neg A) = 0$ – ok; $\nu(\mathcal{V}_B) = (1 \implies 1) = 1$ a $\nu(\neg B) = 1$ – ok; $\nu(\mathcal{V}_C) = 0 \wedge 1 = 0$ a $\nu(\neg C) = 0$ – ok.

   Pachateli jsou tedy osoby $A$ a $C$.

□

1. Základ indukce. Pro $n = 1$ je levá strana rovna $2^1 \cdot 1 = 2$ a pravá $2^2 \cdot 0 + 2 = 2$; rovnost platí.

   Indukční krok. Předpokládejme, že pro jisté $n \in \N$ platí $\sum_{k=1}^n 2^k k = 2^{n+1}(n-1)+2$. Pak

   $$\begin{aligned} \sum_{k=1}^{n+1} 2^k k & = \sum_{k=1}^{n} 2^k k + 2^{n+1}(n+1) \overset{\text{IP}}= \\ & = 2^{n+1}(n-1) + 2 + 2^{n+1}(n+1) = \\ & = 2^{n+1}\bigl((n-1)+(n+1)\bigr) + 2 = 2^{n+1} \cdot 2n + 2 = \\ & = 2^{n+2}\bigl((n+1)-1\bigr) + 2, \end{aligned}$$

   což je přesně dokazovaný vzorec pro $n+1$. Tvrzení tedy platí pro každé $n \in \N$.

2. Základ indukce. Pro $n = 1$ je levá strana rovna $1$ a pravá $\frac13 \cdot 1 \cdot \frac32 \cdot 2 = 1$; rovnost platí.

   Indukční krok. Vzorec nejprve přepíšeme do tvaru bez zlomku uvnitř závorky:

   $$\frac{1}{3}n\left(n+\frac{1}{2}\right)(n+1) = \frac{n(2n+1)(n+1)}{6}.$$

   Předpokládejme, že tato rovnost platí pro jisté $n \in \N$. Pak

   $$\begin{aligned} \sum_{k=1}^{n+1} k^2 &= \sum_{k=1}^n k^2 + (n+1)^2 \overset{\text{IP}}= \frac{n(n+1)(2n+1)}{6} + (n+1)^2 =\\ &= \frac{(n+1)\bigl[n(2n+1) + 6(n+1)\bigr]}{6} =\\ &= \frac{(n+1)\left(2n^2+7n+6\right)}{6} = \frac{(n+1)(n+2)(2n+3)}{6}, \end{aligned}$$

   neboť $2n^2+7n+6 = (n+2)(2n+3)$. Poslední výraz je přesně dokazovaný vzorec pro $n+1$, čímž je indukční krok hotov.

□

1. Základ indukce. Pro $n = 1$ je $\frac{1}{\sqrt1} = 1 \geq 1 = \sqrt1$.

   Indukční krok. Předpokládejme, že pro některé pevné $n \in \N$ platí $\sum_{k=1}^n \frac{1}{\sqrt k} \geq \sqrt n$. Pak

   $$\sum_{k=1}^{n+1} \frac{1}{\sqrt k} = \sum_{k=1}^n \frac{1}{\sqrt k} + \frac{1}{\sqrt{n+1}} \overset{\text{IP}}\geq \sqrt{n} + \frac{1}{\sqrt{n+1}} \overset{?}\geq \sqrt{n+1},$$

   kde poslední nerovnost, označenou otazníkem, teprve chceme dokázat. Jinými slovy, potřebujeme ukázat, že

   $$\frac{1}{\sqrt{n+1}} \geq \sqrt{n+1}-\sqrt{n}.$$

   Pravou stranu usměrníme rozšířením výrazem $\sqrt{n+1}+\sqrt n$:

   $$\sqrt{n+1}-\sqrt{n} = \frac{(n+1)-n}{\sqrt{n+1}+\sqrt{n}} = \frac{1}{\sqrt{n+1}+\sqrt{n}}.$$

   Zkontrolujeme platnost požadované nerovnosti (v prvním kroku přecházíme k převráceným hodnotám kladných čísel, čímž se nerovnost obrací):

   $$\begin{aligned} \frac{1}{\sqrt{n+1}} &\overset{?}\geq \frac{1}{\sqrt{n+1}+\sqrt{n}},\\ \sqrt{n+1} &\overset{?}\leq \sqrt{n+1}+\sqrt{n},\\ 0 &\overset{?}\leq \sqrt{n}. \end{aligned}$$

   Poslední nerovnost zjevně platí pro všechna přirozená $n$, což završuje důkaz indukčního kroku.

2. Základ indukce. Pro $n = 1$ je $1! = 1 \leq 1 = \left(\frac{1+1}{2}\right)^1$.

   Indukční krok. Předpokládejme $n! \leq \left(\frac{n+1}{2}\right)^n$ pro jisté $n \in \N$. Pak

   $$(n+1)! = (n+1) \cdot n! \overset{\text{IP}}\leq (n+1)\left(\frac{n+1}{2}\right)^n = \frac{(n+1)^{n+1}}{2^n}.$$

   Stačí tedy dokázat

   $$\frac{(n+1)^{n+1}}{2^n} \leq \left(\frac{n+2}{2}\right)^{n+1} = \frac{(n+2)^{n+1}}{2^{n+1}},$$

   což je po vynásobení číslem $\frac{2^{n+1}}{(n+1)^{n+1}} > 0$ ekvivalentní nerovnosti

   $$2 \leq \left(\frac{n+2}{n+1}\right)^{n+1} = \left(1+\frac{1}{n+1}\right)^{n+1}.$$

   Ta ale plyne z binomické věty: rozvoj $\left(1+\frac{1}{m}\right)^m$ má samé nezáporné sčítance a jeho první dva jsou $1$ a $m \cdot \frac1m = 1$, takže celý součet je alespoň $2$ (zde $m = n+1$).

□

1. Základ indukce. Pro $n = 1$ je $a_1 = 1 = \frac{1}{11^0}$ a pro $n = 2$ je $a_2 = \frac{1}{11} = \frac{1}{11^1}$; v obou případech vzorec platí.

   Indukční krok. Předpokládejme, že vzorec platí pro jisté $n$ a pro $n+1$, tedy

   $$a_n = \frac{1}{11^{n-1}}, \qquad a_{n+1} = \frac{1}{11^{n}}.$$

   Pak z rekurentního vztahu a indukčního předpokladu

   $$\begin{aligned} a_{n+2} & = \frac{34}{11} \cdot \frac{1}{11^{n}} - \frac{3}{11} \cdot \frac{1}{11^{n-1}} = \frac{34}{11^{n+1}} - \frac{3}{11^{n}} = \\ & = \frac{34}{11^{n+1}} - \frac{33}{11^{n+1}} = \frac{1}{11^{n+1}}, \end{aligned}$$

   což je dokazovaný vzorec pro index $n+2$. Tvrzení tedy platí pro každé $n \in \N$.

2. Klíčové pozorování. Pro každé $n \geq 2$ platí podle definice

   $$F_{n+1} = \underbrace{F_1 + F_2 + \ldots + F_{n-1}}_{{}=\,F_n} + F_n = 2F_n.$$

   Základ indukce. Pro $n = 2$ je $F_2 = F_1 = 1 = 2^{2-2}$.

   Indukční krok. Předpokládejme, že pro jisté $n \geq 2$ platí $F_n = 2^{n-2}$. Podle pozorování výše pak

   $$F_{n+1} = 2F_n = 2 \cdot 2^{n-2} = 2^{n-1} = 2^{(n+1)-2},$$

   což je dokazovaný vzorec pro $n+1$.

□

1. Pokusíme se o důkaz matematickou indukcí. Pro $n = 1$ vychází $\frac{1}{2} < 1$, což platí. V indukčním kroku $n \longrightarrow (n+1)$ pak chceme dokázat

   $$\prod_{k=1}^{n+1} \frac{2k-1}{2k} < \frac{1}{\sqrt{n+1}}.$$

   Při platnosti indukčního předpokladu platí

   $$\prod_{k=1}^{n+1} \frac{2k-1}{2k} = \frac{2n+1}{2n+2} \prod_{k=1}^n \frac{2k-1}{2k} \overset{\text{IP}}< \frac{2n+1}{2n+2} \frac{1}{\sqrt{n}}.$$

   Nyní stačí dokázat

   $$\begin{aligned} \frac{2n+1}{2n+2} \frac{1}{\sqrt{n}} & \overset{?}{\leq} \frac{1}{\sqrt{n+1}} \\ \frac{2n+1}{2n+2} & \overset{?}{\leq} \sqrt{\frac{n}{n+1}} \\ \left(\frac{2n+1}{2n+2}\right)^2 & \overset{?}{\leq} \frac{n}{n+1} \\ (2n+1)^2 (n+1) & \overset{?}{\leq} n (2n+2)^2 \\ n+1 & \overset{?}{\leq} 0, \end{aligned}$$

   což bohužel pravda není. Tímto způsobem tedy odhad matematickou indukcí použít nejde. Odhad je totiž příliš hrubý (odhadujeme shora příliš velkým číslem), takže po použití (taktéž hrubého) indukčního předpokladu se nám nepodaří indukční krok dokončit.

   Poučení: Občas nelze dokázat tvrzení indukcí proto, že dokazujeme zbytečně slabší tvrzení, než skutečně platí.

   Pokusíme se zesílit tvrzení na tvar

   $$\prod_{k=1}^n \frac{2k-1}{2k} \leq \frac{1}{\sqrt{2n+1}}.$$

   Pokud se podaří toto dokázat, bude platit i předchozí nerovnost, neboť

   $$\frac{1}{\sqrt{2n+1}} < \frac{1}{\sqrt{n}}.$$

   Postupujeme opět matematickou indukcí. Pro $n = 1$ vychází $\frac{1}{2} \leq \frac{1}{\sqrt{3}}$, což stále platí. V indukčním kroku $n \longrightarrow (n+1)$ pak chceme dokázat

   $$\prod_{k=1}^{n+1} \frac{2k-1}{2k} \leq \frac{1}{\sqrt{2n+3}}.$$

   Při platnosti indukčního předpokladu platí

   $$\prod_{k=1}^{n+1} \frac{2k-1}{2k} = \frac{2n+1}{2n+2} \prod_{k=1}^{n} \frac{2k-1}{2k} \overset{\text{IP}}\leq \frac{2n+1}{2n+2} \frac{1}{\sqrt{2n+1}}.$$

   Nyní stačí dokázat

   $$\begin{aligned} \frac{2n+1}{2n+2} \frac{1}{\sqrt{2n+1}} & \overset{?}{\leq} \frac{1}{\sqrt{2n+3}} \\ \frac{\sqrt{2n+1}}{2n+2} & \overset{?}{\leq} \frac{1}{\sqrt{2n+3}} \\ (2n+1)(2n+3) & \overset{?}{\leq} (2n+2)^2 \\ 0 & \overset{?}{\leq} 1, \end{aligned}$$

   což platí a indukční krok je tím úspěšně dokázán.

2. Přímočará indukce zde nepomůže, a to proto, že dokazované tvrzení je příliš slabé. Kdybychom totiž předpokládali pouze $a_n \leq n$, dostali bychom

   $$a_{n+1} = 2a_n^2 \leq 2n^2,$$

   a nerovnost $2n^2 \leq n+1$ pro $n \in \N$ neplatí – indukční krok tedy uzavřít nelze.

   Podívejme se však, jak se posloupnost skutečně chová:

   $$a_1 = \frac13, \qquad a_2 = 2 \cdot \frac19 = \frac29, \qquad a_3 = 2 \cdot \frac{4}{81} = \frac{8}{81}, \qquad \dots$$

   Členy zjevně klesají a zůstávají malé. Dokážeme proto silnější tvrzení

   $$a_n \leq \frac{1}{2} \qquad \text{pro každé } n \in \N.$$

   Základ indukce. $a_1 = \frac13 \leq \frac12$.

   Indukční krok. Předpokládejme $a_n \leq \frac12$. Protože jsou všechny členy posloupnosti kladné, lze nerovnost z indukčního předpokladu umocnit na druhou, a tedy

   $$a_{n+1} = 2a_n^2 \overset{\text{IP}}\leq 2 \cdot \left(\frac{1}{2}\right)^2 = \frac{1}{2}.$$

   Silnější tvrzení tedy platí pro každé $n \in \N$. Původní tvrzení z něj plyne okamžitě, neboť

   $$a_n \leq \frac{1}{2} \leq 1 \leq n \qquad \text{pro každé } n \in \N.$$

□