Santa Claus — modified 2021-10-08 18:45 (453 days ago) — edit — reply
Využijeme větu z přednášky, a sice že výraz $X$
$X = p_1p_2...p_{n-1} + 1$
dělí nějaké prvočíslo $p$, pričemž $p$ musí být prvočíslo indexu vyššího nebo rovného $n$
($p$ nemůže dělit $p_1p_2...p_{n-1}$, jinak by dělilo také jedničku).
Protože $p|X$, platí
$p \leq X$.
Protože $p_n \leq p$, tranzitivně platí, že
$p_n \leq X$.
Protože $X$ je horní mezí $p_n$, stačí dokázat, že
$p_1p_2...p_{n-1} + 1\leq 2^{2^{n-1}}$
z této věty pak tranzitivně bude platit věta původní
Teď dokažme větu indukcí:
Nejdříve důkaz pro $n = 1$:
$1 + 1\leq 2^{2^{1-1}}$
$2\leq 2$
což platí.
Předpokládejme, že dokazované tvrzení platí pro $n-1$ (indukční předpoklad).
za $p_m$, kde $m \leq n-1$ můžeme dosadit $2^{2^{m-1}}$, protože podle indukčního předpokladu je to horní mez.
$2^{2^{0}}2^{2^{1}}...2^{2^{n-2}} + 1\leq 2^{2^{n-1}}$
součin můžeme zjednodušit
$2^{2^0 + 2^1 + ... + 2^{n-2}} + 1\leq 2^{2^{n-1}}$
A řadu v exponentu můžeme sečíst jako geometrickou řadu
$2^{\sum_{i=0}^{n-2}2^i} + 1\leq 2^{2^{n-1}}$
$a_0 = 1$, $q = 2$
$2^0 + 2^1 + ... + 2^{n-2} = \sum_{i=0}^{n-2}2^i = 1 \cdot \frac{2^{n-2} - 1}{2 - 1} = 2^{n-1} - 1$
zpětným dosazením
$2^{ 2^{n-1} - 1} + 1\leq 2^{2^{n-1}}$
upravíme
$1\leq 2^{2^{n-1}} - \frac{2^{ 2^{n-1}}}{2}$
$1\leq \frac{2^{ 2^{n-1}}}{2}$
$2^1\leq 2^{ 2^{n-1}}$
protože exponenciální funkce je rostoucí pro základy větší jedné, můžeme nerovnici upravit:
$1\leq 2^{n-1}$
$2^0\leq 2^{n-1}$
a opět:
$0\leq n-1$
$1\leq n$
což pro přirozená čísla platí.
Věta tedy platí.