statnice:bakalar:b4b01dma

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Vlastnosti celých čísel, Euklidův algoritmus. Binární relace. Matematická indukce, rekurzivní vztahy. ======

[[https://fel.cvut.cz/cz/education/bk/predmety/46/80/p4680906.html|B4B01DMA]] [[https://math.fel.cvut.cz/cz/lide/habala/teaching/dma/dmasch.htm|Webové stránky předmětu]]

  * **Dělitelnost** – definice, základní vlastnosti (například tranzitivita), výpočet gcd(a, b).
  * **Celá čísla modulo n** – definice kongruence, pravidla počítání, inverzní číslo a podmínky jeho existence.
  * **Bezoutova identita** – vyjádření gcd jako lineární kombinace čísel a, b. Využití pro řešení diofantických rovnic a hledání inverzního čísla modulo n.
  * **Euklidův algoritmus** – teorie a praxe výpočtu gcd postupným dělením se zbytkem. Rozšířená verze umožňující získat Bezoutovu identitu.
  * **Binární relace** – definice a příklady. Čtyři základní vlastnosti: reflexivita, symetrie, antisymetrie, tranzitivita. Ilustrace grafem relace nebo příklady ze života.
  * **Indukce** – princip matematické indukce, slabá a silná verze, ilustrace na jednoduchých důkazech.
  * **Rekurentní rovnice** – vlastnosti homogenních lineárních rekurentních rovnic. Řešení jako vektorový prostor s bází určenou kořeny charakteristického polynomu.

===== 1. Dělitelnost =====

==== Definice, základní vlastnosti (tranzitivita a podobně), gcd(a,b). ====

Nechť $a,b\in \mathbb{Z}$. Řekneme, že $a$ dělí $b$, značeno $a \mid b$, jestliže existuje $k \in \mathbb{Z}$ takové, že $b = k \cdot a$. V takovém případě říkáme, že **$a$ je dělitel (faktor) čísla $b$** a že **$b$ je násobek čísla $a$**. Pokud toto není pravda, značíme $a \nmid b$.

Tato relace je:
  * **reflexivní** – každé číslo dělí samo sebe, $a \mid a$.
  * **tranzitivní** – pokud $a \mid b$ a $b \mid c$, pak $a \mid c$.
  * **antisymetrická** – pokud $a \mid b$ a $b \mid a$, pak $|a| = |b|$.
  * **nesymetrická** – obecně neplatí, že $a \mid b \Rightarrow b \mid a$.

Množina $\mathbb{Z}$ je uzavřená na operace sčítání, odčítání i násobení.

==== Společný dělitel a GCD ====

Číslo $d \in \mathbb{N}$ je **společný dělitel** (common divisor) čísel $a$, $b$, pokud $d \mid a$ a $d \mid b$.

Největší společný dělitel (greatest common divisor) čísel $a$ a $b$ označujeme $\text{gcd}(a,b)$ a definujeme jako největší číslo, které dělí obě čísla:

$$
n = \text{gcd}(a,b) \iff n \mid a \land n \mid b \land \forall d \in \mathbb{Z}: (d \mid a \land d \mid b \Rightarrow d \leq n)
$$

Platí:
  * $\text{gcd}(0, 0) = 0$
  * $\text{gcd}(a, 0) = |a|$
  * $\text{gcd}(a, b) = \text{gcd}(|a|, |b|)$ – používáme nezáporné hodnoty

==== Poznámky ====
  * Dvě čísla $a$, $b$ jsou **nesoudělná**, pokud $\text{gcd}(a,b) = 1$.
  * Existuje také pojem **společný násobek**: $m$ je společný násobek čísel $a$, $b$, pokud $a \mid m$ a $b \mid m$.
  * Nejmenší takové $m$ je **nejmenší společný násobek** (lcm), značíme $\text{lcm}(a,b)$.
  * Platí:
    $$
    \text{lcm}(a, b) \cdot \text{gcd}(a, b) = |a| \cdot |b|
    $$
  * pokud $a, b \neq 0$.
  * Pro libovolné $a$: $\text{lcm}(a, 0) = 0$
  * Lze se k tomu dostat přes prvočíslený rozklad  nebo Euklidův algoritmus. 

===== 2. Celá čísla modulo n =====

– co je kongruence, jak se tam počítá, co je inverzní číslo a kdy existuje.

==== Modulo ====

**Modulo** znamená „zbytek po dělení“. Zapisujeme jako $a \bmod n$ a označuje zbytek po celočíselném dělení $a$ číslem $n$.

Příklad: $17 \bmod 5 = 2$, protože $17 = 3 \cdot 5 + 2$.


==== Kongruence ====

Čísla $a,b\in \mathbb{Z}$ jsou **kongruentní modulo** $n$, pokud mají stejný zbytek po dělení $n$.

Formálně:
$$
a \equiv b \pmod{n} \iff n \mid (a - b)
$$
což znamená, že existuje $k \in \mathbb{Z}$ takové, že $a = b + kn$.

Ekvivalentně také platí:
$$
a \bmod n = b \bmod n
$$

Kongruence vytváří **ekvivalenční relaci** na množině $\mathbb{Z}$ a rozděluje ji do tříd zbytků.

Každé číslo $a$ patří do třídy zbytků $[a]_n$, která obsahuje všechna čísla kongruentní s $a$ modulo $n$.

==== Počítání v $\mathbb{Z}_n$ ====

Nechť $n \in \mathbb{N}$, a platí $a \equiv u \pmod{n}$ a $b \equiv v \pmod{n}$, pak:

  * $a + b \equiv u + v \pmod{n}$
  * $a - b \equiv u - v \pmod{n}$
  * $ab \equiv uv \pmod{n}$

Tyto operace v modulo aritmetice definují strukturu **komutativního okruhu** $\mathbb{Z}_n$ (množina všech zbytkových tříd modulo $n$).

Alternativní zápis (například v kryptografii nebo při implementaci):
  * $a \oplus b = (a + b) \bmod n$
  * $a \odot b = (a \cdot b) \bmod n$

==== Inverzní číslo ====

Nechť $a \in \mathbb{Z}$ a $n \in \mathbb{N}$. Číslo $x \in \mathbb{Z}$ je **inverzní k $a$ modulo $n$**, pokud:
$$
a \cdot x \equiv 1 \pmod{n}
$$

Takové $x$ převádí $a$ na jedničku v $\mathbb{Z}_n$, čímž umožňuje dělení (násobení inverzní hodnotou).

**Podmínka existence**: Inverzní číslo existuje právě tehdy, když $\text{gcd}(a,n) = 1$, tj. $a$ a $n$ jsou nesoudělná čísla. Pokud existuje, je v $\mathbb{Z}_n$ jednoznačné.

**Výpočet**:
  * Pomocí **rozšířeného Eukleidova algoritmu** – najdeme $x, y \in \mathbb{Z}$ tak, že $a \cdot x + n \cdot y = 1$, potom $x \bmod n$ je hledané inverzní číslo.
  * Inverzi nelze spočítat, pokud $a$ a $n$ mají společného dělitele většího než 1 (například $2^{-1} \bmod 4$ neexistuje).

==== Prvočísla ====

Prvočísla hrají v počítání modulo důležitou roli. 

**Definice**: Přirozené číslo $p > 1$ je **prvočíslo**, pokud jeho jedinými děliteli jsou $1$ a $p$.

V $\mathbb{Z}_p$ pro prvočíslo $p$ má **každý nenulový prvek inverzi** – $\mathbb{Z}_p$ je tedy pole.

Čísla, která nejsou prvočísla a mají více než dva různé dělitele, nazýváme **složená čísla**.


===== 3. Bezoutova identita ===== 
– Která gcd poskytne jako lineární kombinaci čísel $a,b$. K čemu se dá použít: hledání inverzního čísla ve světě modulo, řešení diofantických rovnic.

Bezoutova identita říká, že největší společný dělitel dvou čísel $a, b \in \mathbb{Z}$ lze zapsat jako jejich lineární kombinaci s celočíselnými koeficienty:

$$
\gcd(a,b) = \alpha a + \beta b \quad \text{pro nějaká } \alpha, \beta \in \mathbb{Z}
$$

Tato identita je základem pro řadu dalších výsledků v teorii čísel, zejména při řešení diofantických rovnic a při hledání inverzního čísla modulo $n$.

Příklad:
$$
\gcd(12, 42) = 6 = (-3) \cdot 12 + 1 \cdot 42
$$

Jedno z možných řešení pro $(\alpha,\beta)=(-3,1)$. 


==== Hledání inverzního čísla ====

Chceme nalézt inverzní prvek $a^{-1} \in \mathbb{Z}_n$, tedy takové $x$, že $a \cdot x \equiv 1 \pmod{n}$.

Postup:
  * Použijeme rozšířený Eukleidův algoritmus na $a$ a $n$.
  * Výsledkem bude rovnost $1 = A \cdot a + B \cdot n$.
  * Z toho plyne $a \cdot A \equiv 1 \pmod{n}$, tedy $A$ je inverzní prvek k $a$ modulo $n$.
  * Inverzní číslo existuje právě tehdy, když $\gcd(a,n) = 1$.

Neboli:
  * Najdeme $\gcd(a, n)$ ve tvaru $1 = A \cdot a + B \cdot n$ (rozšířený Eukleidův algoritmus).
  * Pokud $\gcd(a,n) > 1$, inverzní prvek **neexistuje**.
  * Pokud $\gcd(a,n) = 1$, pak $A$ je právě inverzní prvek $a^{-1} \mod n$, protože:

==== Diofantické rovnice ====

Pojem **lineární diofantická rovnice** označujme libovolnou rovnici typu $ax + by = c$ s neznámými $x,y\in \mathbb{Z}$, kde $a,b,c \in \mathbb{Z}$ jsou konstanty.

**Definice**: Diofantická rovnice je rovnice, jejímž cílem je najít **celočíselná** řešení. Např.:
$$
ax + by = c
$$

Řešení existuje tehdy a jen tehdy, když $c$ je dělitelná $\gcd(a,b)$. Bezoutova identita pak dává způsob, jak jedno řešení najít.

**Řešení diofantických rovnic:**

Nechť $a,b,c\in \mathbb{Z}$. Lineární diofantická rovnice $ax + by = c$ má alespoň jedno řešení právě tehdy, když c je násobkem $gcd(a,b)$ (téměř přímo vychází z Bezoutovy identity).

Jeli daná diofantická rovnice $ax +by = c$, pak definujeme její **přidruženou homogenní rovnici** jako $ax + by = 0$.

**Věta o řešení homogeních rovnic**:

Uvažujme rovnici $ax+by=0$ pro $a,b \in \mathbb{Z}$. Množina všech jejích celočíslených řešení je $$\left\{ \left(k \frac{b}{\gcd(a, b)}, - k \frac{a}{\gcd(a, b)}\right) : k \in \mathbb{Z} \right\} $$


==== Algoritmus řešení diofantických rovnic ====

**Algoritmus** pro nalezení všech celočíselných řešení rovnice $ax+by=c$.
  - Najdeme $gcd(a,b)=A\cdot a + B\cdot b$ (Podobné jako u inverzního čísla, vychází z Bezoutovy identity)
  - Jestliže $c$ není násobkem gcd(a,b), pak neexistuje řešení
  - Jestliže $gcd(a,b)$ dělí c:
    - Zadefinujeme $c'=\frac{c}{gcd(a,b)}$ a získáme partikulární řešení $x_p=Ac'$ a $y_p = Bc'$
    - Pro jednochost zápisu zadefinujeme $a'=\frac{a}{gcd(a,b)}$, $b'=-\frac{b}{gcd(a,b)}$ pro $k\in \mathbb{Z}$(Toto vychází z věty o řešení homogeních rovnic).
    - Sečtením partikulárního a obecného homogenního řešení získáme množinu všech celočíselných řešení $$x = x_p + kb', y = y_p - ka' \text{ pro } k \in \mathbb{Z}$$ Případně lze prohodit $-$ pro získání $$x = x_p - kb', y = y_p + ka' \text{ pro } k \in \mathbb{Z}$$
 
Pro řešení difonatických rovnic musíme najít 2 části řešení, homogenní a partikulární část. Partikulární část řešení najde jedno specifické řešení diofantické rovnice, ale abychom našli všechny řešení tak musíme vyřešit homogenní část ta nám umožní najít všechny řešení.

==== Bonus: Malá Fermatova věta ====

Malá Fermatova věta se často používá při hledání inverzních prvků modulo prvočíslo.

  * Pro každé prvočíslo $p$ a každé celé číslo $a$ platí:
    $$
    a^p \equiv a \pmod{p}
    $$
  * Pokud $a \not\equiv 0 \pmod{p}$, pak:
    $$
    a^{p-1} \equiv 1 \pmod{p}
    $$

Z toho plyne, že inverzní prvek lze vypočítat jako:
$$
a^{-1} \equiv a^{p-2} \pmod{p}
$$
===== 4. Euklidův algoritmus ===== 
– jak funguje, teoreticky (přechod ke zbytku po dělení) i prakticky, jak se pozná kdy končí. Jak funguje jeho rozšířená verze, která umí poskytnout Bezoutovu identitu (prakticky).

Ve své základní verzi slouží k hledání GCD (Největšího společného dělitele).

Postupně počítáme zbytky po dělení, přičemž v každém kroku dělíme předchozí dvě čísla. Vždy odečteme co největší násobek menšího čísla od většího, čímž získáme nové, menší číslo. Algoritmus končí ve chvíli, kdy je zbytek nulový – tehdy je poslední nenulové číslo právě $\gcd(a,b)$.
Níže je uveden příklad pro čísla $408$ a $108$:

<tikzjax>
\usepackage{tikz}
\usetikzlibrary{matrix,arrows.meta,positioning}

\begin{document}
\begin{tikzpicture}
  \matrix (m) [
    matrix of nodes,
    nodes in empty cells,
    nodes={font=\ttfamily, minimum width=0.5em, minimum height=1.2em, align=center},
    column sep=0.1em,
  ] {
    408 & \verb!|! &   & \\
    108 & \verb!|! & $(-3)\times$ & \\
     84 & \verb!|! & $(-1)\times$ &  \\
     24 & \verb!|! & $(-3)\times$ &    \\
     12 & \verb!|! & $(-2)\times$ &   \\
      0 & \verb!|! &    &    \\
  };
  \end{tikzpicture}
\end{document}
  </tikzjax>

Díky postupnému zmenšování čísel má algoritmus logaritmickou časovou složitost, což z něj dělá velmi efektivní metodu i pro velká čísla.

==== Rozšířený Euklidův algoritmus ====

Rozšířený Euklidův algoritmus najde nejen GCD (největší společný dělitel), ale zároveň i lineární kombinaci počátečních čísel ze kterých se GCD skládá, což je kritické pro použití Bezoutovy identity a řešení diofantických rovnic. Pro shrnutí: Nechť $a,b \in \mathbb{N}$, poté Euklidův algoritmus dokáže najít $A,B \in \mathbb{Z}$, tak že $a\cdot A + b\cdot B = gcd(a,b)$. 

Po jeho použití dostaneme rovnou Bezoutovu identitu, zkonstruujeme ho následující tabulkou, kde vedle původních čísel dosadíme jednotkovou matici (zde hledáme $\text{gcd}(408, 108)$ a Bezoutovu identitu $12 = A\cdot408 + B\cdot108$), princip je stejný jako u Euklidova algoritmu:

Každý řádek se skládá z $r_i$ | $x_i$ | $y_i$, kde $r_i = x_i\cdot a + y_i\cdot b$. Pro výpočet řádku $i+1$ hledáme $a = \textbf{floor}(r_{i-1} / r_i)$ poté nový řádek je $r_{i+1}$ | $x_i\cdot (-a) + x_{i-1}$ | $y_i\cdot (-a) + y_{i-1}$

Každý řádek obsahuje tři hodnoty $r_i \;|\; x_i \;|\; y_i$, kde:
  * $r_i$ je aktuální zbytek,
  * $x_i$ a $y_i$ jsou koeficienty, které splňují: $r_i = x_i \cdot a + y_i \cdot b$

<tikzjax>
\usepackage{tikz}
\usetikzlibrary{matrix,arrows.meta,positioning}

\begin{document}
\begin{tikzpicture}
  % set up the matrix
  \matrix (m) [
    matrix of nodes,
    nodes in empty cells,
    nodes={font=\ttfamily, minimum width=1.5em, minimum height=1.2em, align=center},
    column sep=1em,
  ] {
        & \verb!|! & 408 & 108 & \\
    408 & \verb!|! &  1 &   0 &       \\
    108 & \verb!|! &  0 &   1 &  \\
     84 & \verb!|! &  1 &  -3 &  \\
     24 & \verb!|! & -1 &   4 &  \\
     12 & \verb!|! &  4 & -15 &  \\
      0 & \verb!|! &    &     &       \\
  };

  \draw[-{Stealth}] 
    (m-3-5.west) to[out=0,in=0] 
      node[midway, anchor=west, xshift=2pt] {$-3\times$} 
    (m-2-5.west);

  \draw[-{Stealth}] 
    (m-4-5.west) to[out=0,in=0] 
      node[midway, anchor=west, xshift=2pt] {$-1\times$} 
    (m-3-5.west);

  \draw[-{Stealth}] 
    (m-5-5.west) to[out=0,in=0] 
      node[midway, anchor=west, xshift=2pt] {$-3\times$} 
    (m-4-5.west);

  \draw[-{Stealth}] 
    (m-6-5.west) to[out=0,in=0] 
      node[midway, anchor=west, xshift=2pt] {$-2\times$} 
    (m-5-5.west);
    
  \node(eq)[below=1.5em of m] 
    {$12 \;=\; 4\cdot408 \;+\;(-15)\cdot108$};
    
    \draw[-{Stealth}, red, thick]
    (m-6-1.south) to[out=180,in=180] 
    node[midway, anchor=east, xshift=-2pt] {gcd} 
    (eq.west);
    
    
\end{tikzpicture}
\end{document}

</tikzjax>

Rozšířený Euklidův algoritmus vždy vrací koeficienty $\alpha, \beta \in \mathbb{Z}$, které splňují Bezoutovu identitu pro zadaná $a,b$.

===== 5. Binární relace =====
– definice a ilustrace na jednoduchých příkladech. Čtyři základní vlastnosti (reflexivita, symetrie, antisymetrie, tranzitivita): jaký mají význam, umět ilustrovat na grafu relace, popřípadě (alespoň intuitivně) rozpoznat u nějaké relace ze života.

==== Definice ====

Nechť $A, B$ jsou množiny. **Binární relace** $R$ z $A$ do $B$ je libovolná podmnožina kartézského součinu:  
$$
R \subseteq A \times B
$$

Jestliže $(a, b) \in R$, zapisujeme $a \mathcal{R} b$ a říkáme, že **prvek $a$ je v relaci s $b$** vzhledem k relaci $\mathcal{R}$.  
Pokud $(a, b) \notin R$, pak $a$ **není v relaci** s $b$.

Pokud je relace na jedné množině ($A = B$), říkáme, že je **na množině $A$**.

==== Čtyři základní vlastnosti ====

Relace $\mathcal{R}$ na množině $A$ může mít tyto čtyři základní vlastnosti:

  * $\mathcal{R}$ je reflexivní, když $\forall a \in A$ platí $ a\mathcal{R}a$. Každý prvek je v relaci sám se sebou. Např. relace „má stejnou hodnotu jako“.
  * $\mathcal{R}$ je symetrická, když $\forall a, b \in A$ platí $ a\mathcal{R}b \implies b\mathcal{R}a$. Pokud $a$ souvisí s $b$, pak i $b$ souvisí s $a$. Např. „je sourozenec“ nebo „je stejně vysoký jako“.
  * $\mathcal{R}$ je antisymetrická, když $\forall a, b \in A$ platí $ (a\mathcal{R}b \land b\mathcal{R}a) \implies a=b$. Pokud $a$ souvisí s $b$ a zároveň $b$ s $a$, pak musí jít o stejný prvek. Např. relace „je menší nebo rovno“.
  * $\mathcal{R}$ je tranzitivní, když $\forall a, b, c \in A$ platí $ (a\mathcal{R}b \land b\mathcal{R}c) \implies a\mathcal{R}c$. Pokud $a$ souvisí s $b$ a $b$ s $c$, pak $a$ souvisí s $c$. Např. „je předchůdce“ nebo „má stejné příjmení jako“.

==== Ekvivalence ====

Relace $\mathcal{R}$ na množině $A$ je **ekvivalence**, pokud splňuje: reflexivitu, symetrii, tranzitivitu.

Taková relace přirozeně rozdělí množinu $A$ na **třídy ekvivalence** – tedy podmnožiny, kde jsou prvky navzájem v relaci.

**Definice třídy ekvivalence**:  
Pro $a \in A$ definujeme:
$$
[a]_{\mathcal{R}} = \{ b \in A \mid a \mathcal{R} b \}
$$

Každý prvek $a$ náleží právě jedné třídě, množina všech tříd tvoří rozklad $A$.

==== Částečné uspořádání ====

Relace $\mathcal{R}$ na množině $A$ je **částečné uspořádání**, pokud splňuje: reflexivitu, antisymetrii, tranzitivitu.

Takovou relaci značíme často symbolem $\preceq$ nebo $\leq$ (např. „dělitelnost“). Dvojice $(A, \mathcal{R})$ se pak nazývá **částečně uspořádaná množina**.

==== Hasseův diagram ====

**Hasseův diagram** je grafické znázornění částečně uspořádané množiny.

  * Vrcholy představují prvky množiny $A$.
  * Hrana mezi $a$ a $b$ značí relaci $a \mathcal{R} b$, kde $a < b$ a neexistuje $c$, pro které by $a < c < b$.
  * Prvek $a$ je v diagramu **níž** než $b$, pokud $a \mathcal{R} b$.

**Další pojmy v uspořádání**:

  * **Největší prvek** – prvek, ke kterému vede cesta z každého jiného prvku (nemusí existovat).
  * **Maximum** – prvek, nad kterým už není žádný jiný.
  * **Nejmenší prvek** – prvek, ze kterého vede cesta ke všem ostatním (nemusí existovat).
  * **Minimum** – prvek, pod kterým už není žádný jiný.

**Linearizace částečného uspořádání**:  
Z Hasseova diagramu vytvoříme posloupnost prvků (např. zleva doprava, po úrovních), která zachovává uspořádání.

===== 6. Indukce ===== 
– je třeba rozumět principu, vnímat různé verze (slabá, silná), umět případně ilustrovat na nějakém jednoduchém důkazu.

==== Slabý princip matematické indukce ====

Nechť $n_0 \in \mathbb{Z}$, ať $V(n)$ je výrok (vlastnost) pro celá čísla $n \geq n_0$.  
Předpokládejme, že platí:
  * $V(n_0)$  
  * $\forall n \geq n_0: \; V(n) \Rightarrow V(n+1)$  

Pak $V(n)$ platí pro všechna $n \geq n_0$.

==== Příklad (slabá indukce) ====

Dokážeme, že $2^n \ge n+1$ pro každé $n \in \mathbb{N}_0$.

  * **Základ:** $n = 0$: $2^0 = 1 \ge 1$
  * **Indukční krok:** Předpokládáme $2^n \ge n+1$. Pak:
    $$
    2^{n+1} = 2 \cdot 2^n \ge 2(n+1) \ge (n+1)+1
    $$
protože $n+1 \ge 1$

==== Silný princip matematické indukce ====

**Vysvětlení:**  
Na rozdíl od slabé indukce zde při kroku $n+1$ předpokládáme, že tvrzení platí **pro všechna** menší čísla $n_0, n_0\!+\!1,\dots,n$.  
Je to, jako bys stavěl schody a u každého nového stupínku směl využít celou „platformu“ před sebou, nejen poslední schod.

Formálně:  
Pokud platí  
  * $V(n_0)$,  
  * $\forall n \geq n_0:\; \bigl(\forall k,\; n_0\le k\le n \Rightarrow V(k)\bigr)\;\Rightarrow\; V(n+1)$,  
pak $V(n)$ platí pro všechna $n \geq n_0$.

==== Příklad (silná indukce) ====  

Dokážeme, že každé celé číslo $n \ge 2$ lze zapsat jako součin prvočísel.

  * **Základ:** $n = 2$ je prvočíslo, tedy rozklad existuje.
  * **Indukční krok:** Předpokládáme, že tvrzení platí pro všechna $k$ s $2 \le k \le n$.
  * Uvažujme $n+1$:
    - Pokud je $n+1$ prvočíslo, rozklad je hotový.
    - Pokud je složené, existují $a, b$ taková, že $n+1 = a \cdot b$ a $2 \le a,b \le n$.
    - Podle indukčního předpokladu lze $a$ i $b$ rozložit na součin prvočísel.
    - Součinem těchto rozkladů získáme rozklad i pro $n+1$.

**Krátký slovní popis:**  
V kroku $n+1$ můžeme předpokládat platnost tvrzení pro **každé** $k$ s $2\le k\le n$.  
Je-li $n+1$ složené, rozdělíme ho na dva menší činitele $a,b$ (to lze díky tomu že víme, že čísla která nejsou prvočíslo jsou dělitelná ne jen sama sebou a 1) a pro oba už známe rozklad (protože čísla jsou menší než $n$ a pro ty už jsme si to dokázali) → jejich součinem dostaneme
rozklad i pro $n+1$.  

===== 7. Rekurentní rovnice ===== 

 – základní vlastnosti homogenních lineárních rekurentních rovnic (jejich množina řešení tvoří vektorový prostor dimenze rovné řádu rovnice, takže řešení lze generovat pomocí vhodné báze), jak najít vhodnou bázi (pomocí kořenů charakteristického polynomu).

**Definice:** 

Rekurentní (nebo také rekurzivní) vztah pro posloupnost $\{a_k\}$ je libovolná rovnice typu:
$$
F(a_n, a_{n-1}, a_{n-2}, \dots, a_0) = 0
$$
kde $F$ je nějaká funkce.

Například problém Hanojských věží lze vyjádřit vztahem:
$$
H_n = 2 \cdot H_{n-1} + 1
\quad\text{tedy}\quad
H_n - 2H_{n-1} - 1 = 0
$$

====Lineární rekurentní rovnice==== 

Lineární rekurentní rovnice (nebo také lineární rekurzivní rovnice) **řádu $k$** je rovnice tvaru:
$$
a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n
\quad \text{pro všechna } n \geq n_0
$$

  * $k$ je řád rovnice – největší indexový posun v levé straně.
  * Koeficienty $c_i(n)$ jsou funkce $\mathbb{Z} \to \mathbb{R}$ (mohou být konstantní nebo závislé na $n$).
  * $b_n$ je tzv. pravá strana rovnice (např. nulová, nebo jiná posloupnost).

Rovnice se nazývá **homogenní**, pokud platí $b_n = 0$ pro všechna $n \geq n_0$.

  * Množina všech řešení homogenní rovnice tvoří **vektorový prostor** dimenze $k$.
  * Řešení lze vyjádřit pomocí **báze** tohoto prostoru, kterou určujeme z kořenů tzv. charakteristického polynomu.

====Řešení====

Nechť je dána lineární rekurentní rovnice:
$$
a_{n+k} + c_{k-1}(n)a_{n+k-1} + \dots + c_1(n)a_{n+1} + c_0(n)a_n = b_n
$$

**Řešením** rozumíme posloupnost $\{a_n\}_{n=n_0}^\infty$, která po dosazení splňuje rovnici pro všechna $n \geq n_0$.

====Charakteristická rovnice====

**Definice:**
$$
a_{n+k} + c_{k-1}a_{n+k-1} + \dots + c_0a_n = b_n
$$

Pokud je $b_n = 0$ pro všechna $n$, rovnice se nazývá **homogenní** a můžeme k ní přiřadit **charakteristický polynom**:
$$
p(\lambda) = \lambda^k + c_{k-1}\lambda^{k-1} + \dots + c_1\lambda + c_0
$$

Řešením rovnice $p(\lambda) = 0$ (tzv. **charakteristická rovnice**) jsou tzv. **charakteristická čísla** (nebo také **kořeny** či „vlastní čísla“).

  * Každé charakteristické číslo $\lambda$ generuje **jednu základní posloupnost** $a_n=\lambda^n$. Mluvíme-li o „vektorovém prostoru“, nemyslíme tím čísla $\lambda$, ale **množinu všech posloupností** vzniklých lineárními kombinacemi těchto základních posloupností.
  * Pokud má polynom $p$ více různých kořenů $\lambda_1,\dots,\lambda_m$, tvoří **bázi** prostoru řešení posloupnosti $\lambda_1^n,\dots,\lambda_m^n$. Libovolná lineární kombinace
$$
a_n = \alpha_1\lambda_1^n+\dots+\alpha_m\lambda_m^n
$$
    * je také řešením, takže celý prostor řešení má dimenzi $m$.
  * Má-li některý kořen násobnost $r>1$, přidávají se do báze i členy $n\lambda^n,\,n^2\lambda^n,\dots,n^{r-1}\lambda^n$, aby dimenze prostoru zůstala rovna řádu $k$.

Pomocí těchto tvarů sestavíme obecné řešení homogenní rovnice – každý kořen přispívá jedním nebo více lineárně nezávislými členy.

====Příklad 1 – dva různé kořeny====

Homogenní rovnice druhého řádu
$$
a_{n+2}-3a_{n+1}+2a_n=0
$$
má charakteristický polynom $p(\lambda)=\lambda^2-3\lambda+2$  
a kořeny $\lambda_1=1,\;\lambda_2=2$.

  * Základní řešení: $u_n = 1^n = 1$, $v_n = 2^n$.
  * Obecné řešení: $$a_n = \alpha\cdot1 + \beta\cdot2^n.$$
  * Prostor všech řešení je tedy 2-rozměrný a jeho (jednou z možných) bází je $\{\,1,\,2^n\}$.

====Příklad 2 – násobný kořen====

Rovnice
$$
a_{n+2}-2a_{n+1}+a_n=0
$$
má charakteristický polynom $p(\lambda)=(\lambda-1)^2$, kořen $\lambda=1$ s násobností 2.

  * Základní řešení: $u_n = 1^n = 1$, $v_n = n\cdot1^n = n$.
  * Obecné řešení: $$a_n = \alpha + \beta n.$$
  * Znovu dostáváme 2-rozměrný prostor řešení, tentokrát s bází $\{\,1,\,n\}$.
Trace: • b4b39hry • b0b39pgr • be4b39vgo • b4b33rpz • exams • b4m39apg • b0b33opt • b4b35osy
Search

Navigation

Print/export

Tools

QR Code
