# Domácí úkoly 1

## SQRTN

Důkaz sporem: Je-li $\sqrt{n} \in \mathbb{Q} \land \sqrt{n} \notin \mathbb{Z}$ (druhá odmocnina není záporná z principu a není ani přirozená vzhledem k zadání), dá se zapsat ve tvaru $\frac{a}{b}$ ($a,b \in \mathbb{N}, b \ne 1$ ) přičemž $a,b$ jsou nesoudělná čísla. Dále upravíme:

- $\sqrt{n}$ = $\frac{a}{b}$.
- $n$ = $\frac{a^2}{b^2}$.
- ${a^2}$ = $nb^2$
Číslo ${a^2}$ je dělitelné $n$, a tedy i $a$ je dělitelné $n$, dá se přepsat na $a = nx$, $x\in \mathbb{N}$ (tzn. dává zbytek 0 při dělení $n$.)
Nahradíme-li $a = nx$ v rovnici o dva řádky výše, dostaneme:
- ${(nx)^2}$ = $nb^2$
- $nx^2$ = $b^2$
Analogicky, jelikož číslo ${b^2}$ je dělitelné $n$, i $b$ je dělitelné $n$, takže čísla $a$ i $b$ musí mít společného dělitele - což je spor s tím, že jsou nesoudělná.

## PRIME
Zjednodušuji zápis pravé strany nerovnice: ($2^n = v, 2^v = C_n$)
Představíme-li si prvočísla a čísla C v grafu ($x$-ové ose odpovídá hodnota $n$), pak
hodnoty $C$ jsou na grafu "cílových" hodnot, ke které se musí graf prvočísel přiblížit a překročit ji. Našim úkolem je dokázat, že tato situace nastat nemůže (tedy že $p_n \geq C_n$).
Platí: $C_{n+1} = C_n^2$, tzn. při každém "nově nalezeném" prvočíslu se hodnota $C$ umocní na druhou.
Jak nalézt nové prvočíslo? Podobně jako vyvrátit tvrzení, že neexistuje nejvyšší prvočíslo. Vynásobím všechna známá prvočísla (tento součin zapíšu jako $X$) a přičtu nebo odečtu 1.
Tím pádem naleznu alespoň dvě nová prvočísla, tzn. $p_{n+1}\leq$$X-1$ a $p_{n+2} \leq$$X+1$. Pokud některé z těchto dvou prvočísel náhodou prvočíslem není, pak existuje alespoň jedno jiné, nižší prvočíslo. Existence těchto čísel není na škodu důkazu, jelikož to pouze dá "náskok" hodnotě $C$.
Zopakujeme-li daný postup, pak dostaneme $X\ast({X-1})\ast(X+1)=X^3-X$. Zde již nemusíme počítat dále (přičítat nebo odečítat jedničku), jelikož hodnota $X$ se umocnila na třetí, zatímco hodnota $C_n$ se umocnila alespoň na čtvrtou (díky dvěma nově nalezeným prvočíslům).
Zbývá dokázat, že $X$ nemůže být nikdy vyšší než $C$. Pro toto nám stačí první krok matematické indukce - $p_1=2, p_2=3, X=6$, ovšem $C_2=2^4=16$ a díky výše uvedenému výpočtu se bude hodnota $C$ vždy zvyšovat rychleji než rozdíl mezi prvočísly.
Důkaz se dá také interpretovat tak, že umocníme-li nějaké prvočíslo $P$ na třetí, nalezneme mezi $P$ a $P^3$ alespoň dvě další prvočísla.
## Elka
Jako vykousnutou šachovnici můžene považovat už i základní dílek ($n=1$), tzn. šachovnice $2\times 2-1$. Při zvýšení $n$ o $1$ se šachovnice zvětší čtyřikrát. Použijeme-li předchozí šachovnici, pak zvětšenou šachovnici můžeme vystavět dvěma způsoby:
- zaplníme díru (v pravém horním rohu), šachovnici okopírujeme čtyřikrát a poté opět odstraníme pravý horní roh
- šachovnici i s vykousnutým rohem okopírujeme čtyřikrát a poté přidáme tři dílky.
Zde použiju druhý způsob.
Z $n=1$ na $n=2$ se dostanu následovně:
- https://ibb.co/hgX5NLV
- Nyní stačí již jen vložit poslední dílek do středu a šachovnice je hotova.

Další šachovnice bude opět složena ze čtyřech menších šachovnic - tzn. tak, že šachovnice nad levou dolní šachovnicí bude otočena o $90$ stupňů po směru hodinových ručiček a pravá dolní šachovnice otočena o $90$ stupňů proti směru. Šachovnice vpravo nahoře bude stejně orientovaná jako ta dolní, čímž opět vznikne pravý horní roh prázdný a uprostřed díra právě pro jeden dílek.

## Identita
Důkaz pomocí indukce v obou případech.
- Dosadím nejnižší možnou hodnotu $n$, ověřím, zda rovnost platí
- Za $n$ dosadím $(n+1)$ a ověřím, zda rovnost platí. Přitom předpokládám, že výrazy v hranaté závorce (původní tvar identity) se rovnají již z principu.
### Identita2
$\sum_{i=1}^{n}(4i+5)=2n^2+7n$
- $n=1$:
levá strana: $4\ast 1 + 5 = 9$
pravá strana: $2 \ast 1^2 + 7 \ast 1 = 9$
Rovnost platí
- $n:= n+1$:
levá strana:
$\sum_{i=1}^{n+1}(4i+5)$=$[\sum_{i=1}^{n}(4i+5)]+4(n+1)+5=[\sum_{i=1}^{n}(4i+5)]+4n+9$
pravá strana:
$2(n+1)^2+7(n+1)=$
$2(n^2+2n+1)+7n+7=[2n^2]+4n+2+[7n]+7=$
$[2n^2+7n]+4n+9$
Rovnost platí
### Identita3
$\prod_{i=2}^{n}\frac{i-1}{i}=\frac{1}{n}$
- $n=2$:
levá strana: $\frac{2-1}{2}=\frac{1}{2}$
pravá strana: $\frac{1}{2}$
Rovnost platí
- $n:=n+1$:
levá strana:
$\prod_{i=2}^{n+1}=[\prod_{i=2}^{n}]\ast\frac{n+1-1}{n+1}=[\frac{1}{n}]\ast\frac{n}{n+1}=\frac{1}{n+1}$
pravá strana:
$\frac{1}{n+1}$
Rovnost platí
## Prunik
$$\bigcap_{i=1}^{n}\bigcup_{j=1}^{m}A_{i,j}=$$
$\{A_{1,1}\cap A_{1,2} \cap \dots \cap A_{1,m}\}\cup \{A_{2,1}\cap A_{2,2} \cap \dots \cap A_{2,m}\}\cup \dots \cup \{A_{n,1}\cap A_{n,2} \cap \dots \cap A_{n,m}\}$