01ZTGA:Kapitola3 1

PDF	[ znovu generovat,	výstup z překladu ]	Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly	[ znovu generovat,	výstup z překladu ]	Přeložení pouze této kaptioly.
ZIP			Kompletní zdrojový kód včetně obrázků.
Součásti dokumentu 01ZTGA

součást	akce		poslední editace			soubor
Hlavní dokument	editovat	Hlavní stránka dokumentu 01ZTGA	Karel.brinda	15. 1. 2012	23:45
Řídící stránka	editovat	Definiční stránka dokumentu a vložených obrázků	Admin	7. 9. 2015	13:51
Header	editovat	Hlavičkový soubor	Karel.brinda	15. 1. 2012	12:34	header.tex
Kapitola0	editovat	Úvod	Karel.brinda	15. 1. 2012	12:36	cast0.tex
Kapitola1_1	editovat	Základní pojmy	Karel.brinda	15. 1. 2012	12:46	cast1_kapitola1.tex
Kapitola1_2	editovat	Souvislost	Karel.brinda	15. 1. 2012	12:49	cast1_kapitola2.tex
Kapitola1_3	editovat	Bipartitní grafy	Karel.brinda	15. 1. 2012	12:50	cast1_kapitola3.tex
Kapitola1_4	editovat	Stromy	Kubuondr	5. 1. 2019	09:06	cast1_kapitola4.tex
Kapitola1_5	editovat	Hledání minimální kostry grafu	Karel.brinda	15. 1. 2012	12:51	cast1_kapitola5.tex
Kapitola1_6	editovat	Jednotažky	Karel.brinda	15. 1. 2012	12:53	cast1_kapitola6.tex
Kapitola1_7	editovat	Hamiltonovské kružnice a grafy	Karel.brinda	15. 1. 2012	13:34	cast1_kapitola7.tex
Kapitola1_8	editovat	Párování v grafech	Karel.brinda	15. 1. 2012	13:40	cast1_kapitola8.tex
Kapitola1_9	editovat	Toky v sítích	Karel.brinda	15. 1. 2012	13:44	cast1_kapitola9.tex
Kapitola1_10	editovat	Hranové obarvení grafu	Karel.brinda	15. 1. 2012	13:48	cast1_kapitola10.tex
Kapitola1_11	editovat	Vrcholové obarvení grafu	Karel.brinda	15. 1. 2012	13:52	cast1_kapitola11.tex
Kapitola1_12	editovat	Planární grafy	Karel.brinda	15. 1. 2012	13:56	cast1_kapitola12.tex
Kapitola1_13	editovat	Vlastní čísla adjacenční matice grafu	Karel.brinda	15. 1. 2012	13:57	cast1_kapitola13.tex
Kapitola2_1	editovat	Brouwerova věta o pevném bodě	Karel.brinda	15. 1. 2012	14:11	cast2_kapitola1.tex
Kapitola2_2	editovat	Pravděpodobnostní důkazy v teorii grafů	Karel.brinda	15. 1. 2012	14:12	cast2_kapitola2.tex
Kapitola2_3	editovat	Extremální teorie grafů	Karel.brinda	15. 1. 2012	14:16	cast2_kapitola3.tex
Kapitola2_4	editovat	Ramseyovská čísla	Karel.brinda	15. 1. 2012	14:18	cast2_kapitola4.tex
Kapitola3_1	editovat	Obyčejné mocninné řady	Karel.brinda	15. 1. 2012	14:22	cast3_kapitola1.tex
Kapitola3_2	editovat	Exponenciální generující funkce	Karel.brinda	15. 1. 2012	14:22	cast3_kapitola2.tex
Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\section{Obyčejné mocninné řady}
 
Připomeňme si nejprve definici číselné řady.
 
\begin{defn*}
Nechť $\left(a_{n}\right)_{n=1}^{\infty}$ je číselná posloupnost.
Nechť $s_{n}=\sum\limits _{k=0}^{n}a_{k}$. \textbf{Číselnou řadou}
nazýváme dvojici posloupností $\left(\left(a_{n}\right)_{n=0}^{\infty},\left(s_{n}\right)_{n=0}^{\infty}\right)$,
kterou označujeme zkráceně jako $\sum\limits _{n=1}^{\infty}a_{n}$.
Číslo $a_{n}$ se nazývá $n$-tý \textbf{člen} řady, $s_{n}$se nazývá
$n$-tý \textbf{částečný součet} řady. Jestliže existuje limita $s=\lim\limits _{n\to\infty}s_{n}$,
potom $s$ se nazývá \textbf{součet} řady a často se označuje též
jako $\sum\limits _{n=1}^{\infty}a_{n}$.
\end{defn*}
\begin{defn}
\label{def:OPS}Nechť $z\in\C$, $\left(a_{n}\right)_{n=0}^{\infty}$
je číselná posloupnost. \textbf{Obyčejnou mocninnou řadou} (angl.
\emph{ordinary power series}, OPS) rozumíme číselnou řadu\[
\sum_{n=0}^{\infty}a_{n}z^{n}\]
a její součet (pokud existuje) nazýváme \textbf{generující funkcí}
této řady. Tento součet je funkcí proměnné $z$. Korespondenci posloupnosti
koeficientů OPS a generujcí funkce $f(z)$ této OPS zapisujeme jako\[
\left(a_{n}\right)_{n=0}^{\infty}\xrightarrow{OPS}f(z).\]
 
\end{defn}
\begin{example*}
\[
\left(1\right)_{n=1}^{\infty}\xrightarrow{OPS}\frac{1}{1-z}=\sum_{n=0}^{\infty}z^{n}\]
 
\end{example*}
 
\subsection{Pravidla pro počítání s OPS\label{sub:Pravidla-pro-pociani-s-OPS}}
 
Jestliže \[
\left(a_{n}\right)_{n=0}^{\infty}\xrightarrow{OPS}f(z),\;\left(b_{n}\right)_{n=0}^{\infty}\xrightarrow{OPS}g(z),\]
tak potom lze odvodit následující vztahy:
 
\begin{enumerate}
\item Pro posunutí indexu o 1 platí\[
\boxed{\left(a_{n+1}\right)_{n=0}^{\infty}\xrightarrow{OPS}\frac{1}{z}\left(f(z)-f(0)\right)},\]
protože\[
\left(a_{n+1}\right)_{n=0}^{\infty}\xrightarrow{OPS}h(z)=\sum_{n=0}^{\infty}a_{n+1}z^{n}=\frac{1}{z}\sum_{n=0}^{\infty}a_{n+1}z^{n+1}=\frac{1}{z}\sum_{n=1}^{\infty}a_{n}z^{n},\]
přičemž zřejmě poslední výraz je roven $\left(f(z)-f(0)\right)$,
protože $f(0)=a_{0}z^{0}=a_{0}$.
\item Pro násobení mocninou konstanty platí\[
\boxed{\left(c^{n}a_{n}\right)_{n=0}^{\infty}\xrightarrow{OPS}f(cz)},\]
 což je zřejmé.
\item Pro násobení indexem $n$ platí\[
\boxed{\left(na_{n}\right)_{n=0}^{\infty}\xrightarrow{OPS}zf'(z)},\]
protože platí $f'(z)=\sum_{n=0}^{\infty}na_{n}z^{n-1}$, ale my potřebujeme
$h(z)=\sum_{n=0}^{\infty}na_{n}z^{n}$.
\item Zřejmě platí\begin{equation}
\boxed{\left(a_{n}\pm b_{n}\right)_{n=0}^{\infty}\xrightarrow{OPS}f(z)\pm g(z)}.\label{eq:Soucet-rozdil-OPS}\end{equation}
 
\item Podle vzorce pro násobení mocninných řad platí\[
\boxed{\left(\sum_{k=0}^{n}a_{k}b_{n-k}\right)_{n=0}^{\infty}\xrightarrow{OPS}f(z)g(z)},\]
protože\[
\left(\sum_{n=0}^{\infty}a_{n}z^{n}\right)\left(\sum_{n=0}^{\infty}b_{n}z^{n}\right)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}a_{k}b_{n-k}\right)z^{n}.\]
 
\item Pro posloupnost částečných součtů platí \[
\boxed{\left(\sum_{k=0}^{n}a_{k}\right)_{n=0}^{\infty}\xrightarrow{OPS}\frac{1}{1-z}f(z)},\]
protože jde o aplikaci předchozího bodu při volbě $b_{n}=1$, a tedy
$g(z)=\frac{1}{1-z}$.
\item Podle předchozích pravidel platí\[
\boxed{\left(\frac{a_{n}+(-1)^{n}a_{n}}{2}\right)_{n=0}^{\infty}\xrightarrow{OPS}\frac{f(z)+f(-z)}{2}},\]
kde ovšem \[
\frac{a_{n}+(-1)^{n}a_{n}}{2}=\begin{cases}
a_{n} & n\textrm{ sudé}\\
0 & n\textrm{ liché}\end{cases},\]
čemuž odpovídá řada pouze ze sudých členů\[
\sum_{k=0}^{\infty}a_{2k}z^{2k}.\]
 
\end{enumerate}
 
\subsection{Jednoduché příklady}
 
\begin{example}
\label{exa:OPS-simple-example-1}Vypočítejte součet $\sum\limits _{k=0}^{n}(-1)^{k}k^{2}$.
 
Pokusíme se daný součet vyjádřit jako $n$-tý koeficient OPS. Používáním
právě odvozených pravidel dostáváme postupně:\[
\left(1\right)_{n=0}^{\infty}\xrightarrow{OPS}\frac{1}{1-z},\]
\[
\left(n\cdot1\right)_{n=0}^{\infty}\xrightarrow{OPS}z\left(\frac{1}{1-z}\right)'=\frac{z}{\left(1-z\right)^{2}},\]
\[
\left(n\cdot n\right)_{n=0}^{\infty}\xrightarrow{OPS}z\left(\frac{z}{\left(1-z\right)^{2}}\right)'=...=z\frac{1+z}{\left(1-z\right)^{3}},\]
\[
\left(\left(-1\right)^{n}n^{2}\right)_{n=0}^{\infty}\xrightarrow{OPS}-z\frac{1-z}{\left(1+z\right)^{3}},\]
\[
\left(\sum_{k=0}^{n}\left(-1\right)^{k}k^{2}\right)_{n=0}^{\infty}\xrightarrow{OPS}\frac{1}{1-z}\left(-z\frac{1-z}{\left(1+z\right)^{3}}\right)=\frac{-z}{\left(1+z\right)^{3}}=\sum_{n=0}^{\infty}A_{n}z^{n}.\]
Částečné součty $\sum\limits _{k=0}^{n}(-1)^{k}k^{2}$ lze nyní najít
pomocí rozvoje funkce $\frac{-z}{\left(1+z\right)^{3}}$ do mocninné
řady, neboť tento rozvoj je vždy jednoznačný. Jestliže tedy jakkoliv
nalezneme koeficienty rozvoje $A_{n}$, tak potom platí\[
A_{n}=\sum\limits _{k=0}^{n}(-1)^{k}k^{2}.\]
 
 
Nejprve si odvodíme ještě jedno užitečné pravidlo pro počítání s OPS.
Postupně derivujeme:\begin{eqnarray*}
f(z)=\frac{1}{1-z} & = & \sum_{n=0}^{\infty}z^{n},\\
f'(z)=\frac{1}{\left(1-z\right)^{2}} & = & \sum_{n=1}^{\infty}nz^{n-1},\\
f''(z)=\frac{2}{\left(1-z\right)^{3}} & = & \sum_{n=2}^{\infty}n(n-1)z^{n-2},\\
f'''(z)=\frac{6}{\left(1-z\right)^{4}} & = & \sum_{n=3}^{\infty}n(n-1)(n-2)z^{n-3},\\
 & \vdots\\
f^{(k)}(z)=\frac{k!}{\left(1-z\right)^{k+1}} & = & \sum_{n=k}^{\infty}\binom{n}{k}k!z^{n-k}.\end{eqnarray*}
Z toho plyne, že\[
\frac{1}{\left(1-z\right)^{k+1}}=\sum_{n=k}^{\infty}\binom{n}{k}z^{n-k}=\sum_{n=0}^{\infty}\binom{n+k}{k}z^{n}\]
 a tedy pro každé $k\in\N$ máme\begin{equation}
\boxed{\left(\binom{n+k}{k}\right)_{n=0}^{\infty}\xrightarrow{OPS}\frac{1}{\left(1-z\right)^{k+1}}}.\label{eq:OPS_pravidlo_komb}\end{equation}
 
 
Jestliže nyní dosadíme $k=2$ a za proměnnou $z$ dosadíme $-z$,
pak dostaneme\[
\frac{-z}{\left(1+z\right)^{3}}=(-z)\sum_{n=0}^{\infty}\binom{n+2}{2}(-z)^{n}=\sum_{n=0}^{\infty}\underbrace{\binom{n+2}{2}\left(-1\right)^{n+1}}_{A_{n+1}}z^{n+1}.\]
Nalezli jsme tedy (jednoznačně určené) koeficienty rozvoje funkce
$\frac{-z}{\left(1+z\right)^{3}}$ do mocninné řady, a proto platí\[
\sum\limits _{k=0}^{n}(-1)^{k}k^{2}=A_{n}=\binom{n+1}{2}\left(-1\right)^{n}.\]
 
\end{example}
\begin{rem*}
Všimněme si, že vzorec (\ref{eq:OPS_pravidlo_komb}) jsme použili
pouze na funkci $\frac{1}{\left(1+z\right)^{3}}$ a teprve výsledek
jsme vynásobili $\left(-z\right)$. Tím na pravé straně zůstala mocninná
řada, kterou jsme nakonec vhodně upravili posunutím indexů.
\end{rem*}
 
 
\begin{rem*}
Získaný výsledek si můžeme ověřit pro $n$ sudé, kdy lze hledanou
sumu sečíst i jednodušším způsobem:
 
\begin{multline*}
-1^{2}+2^{2}-3^{2}+4^{2}-5^{2}+6^{2}-...-(n-1)^{2}+n^{2}=\\
=\sum_{i=1}^{\frac{n}{2}}-(2i-1)^{2}+(2i)^{2}=\sum_{i=1}^{\frac{n}{2}}\left(4i-1\right)=4\frac{\frac{n}{2}\left(\frac{n}{2}+1\right)}{2}-\frac{n}{2}=\\
=\frac{n^{2}}{2}+\frac{n}{2}=\frac{n(n+1)}{2}=\binom{n+1}{2}\underbrace{\left(-1\right)^{n}}_{1}\end{multline*}
 
\end{rem*}
\begin{example}
Vypočítejte $n$-tý člen Fibonacciho posloupnosti, která je definována
rekurentním vztahem\[
F_{0}=0,\  F_{1}=1,\  F_{n+2}=F_{n+1}+F_{n}.\]
 
 
Opět považujeme $F_{n}$ za $n$-tý koeficient určité OPS a najdeme
její generující funkci. Při tom využijeme rekurentní vztah z definice
posloupnosti $\left(F_{n}\right)$. Platí\begin{eqnarray*}
\left(F_{n}\right)_{n=0}^{\infty} & \xrightarrow{OPS} & f(z)=\sum_{n=0}^{\infty}F_{n}z^{n},\\
\left(F_{n+1}\right)_{n=0}^{\infty} & \xrightarrow{OPS} & \frac{f(z)-f(0)}{z}=\frac{1}{z}f(z),\\
\left(F_{n+2}\right)_{n=0}^{\infty} & \xrightarrow{OPS} & \frac{\frac{1}{z}f(z)-\overbrace{\frac{1}{0}f(0)}^{=1}}{z}=\frac{f(z)-z}{z^{2}}.\end{eqnarray*}
V posledním řádku je třeba vysvětlit formální zápis $\frac{1}{0}f(0)$.
Generující funkce OPS dané posloupností $\left(F_{n+1}\right)_{n=0}^{\infty}$
je $h(z)=\frac{1}{z}f(z)$, ale podle příslušného pravidla pro počítání
s OPS (viz. část \ref{sub:Pravidla-pro-pociani-s-OPS}) je hodnota
$h(0)$ rovna nultému koeficientu řady, což je $F_{1}=1$. Nyní podle
pravidla (\ref{eq:Soucet-rozdil-OPS}) můžeme převést rovnost posloupností
\[
F_{n+2}=F_{n+1}+F_{n}\]
 na rovnost generujících funkcí\[
\frac{f(z)-z}{z^{2}}=\frac{1}{z}f(z)+f(z),\]
z čehož snadno vyjádříme generující funkci $f(z)$ jako\[
f(z)=\frac{z}{1-z-z^{2}}.\]
Jestliže nyní $f(z)$ rozvineme do mocninné řady, budou koeficienty
u mocnin $z^{n}$ právě hledaná Fibonacciho čísla. Abychom si rozvoj
usnadnili, uvědomíme si, že funkci $f(z)$ lze rozložit na parciální
zlomky\[
f(z)=\frac{z}{1-z-z^{2}}=\frac{A}{r_{1}-z}+\frac{B}{r_{2}-z},\]
kde $r_{1},r_{2}$ jsou kořeny polynomu $1-z-z^{2}$. Nyní stačí rozvinout
jednotlivé parciální zlomky, což je snadné, neboť se jedná jen o substituci
v geometrické řadě. Například můžeme uvažovat takto:\begin{eqnarray*}
\left(1\right)_{n=0}^{\infty} & \xrightarrow{OPS} & \frac{1}{1-z},\\
\left(\left(\frac{1}{r}\right)^{n}\right)_{n=0}^{\infty} & \xrightarrow{OPS} & \frac{1}{1-\frac{z}{r}}=r\frac{1}{r-z},\\
\left(\frac{A}{r}\left(\frac{1}{r}\right)^{n}\right)_{n=0}^{\infty} & \xrightarrow{OPS} & \frac{A}{r-z}.\end{eqnarray*}
Proto\[
f(z)=\frac{A}{r_{1}-z}+\frac{B}{r_{2}-z}=\frac{A}{r_{1}}\sum_{n=0}^{\infty}\frac{1}{r_{1}^{n}}z^{n}+\frac{B}{r_{2}}\sum_{n=0}^{\infty}\frac{1}{r_{2}^{n}}z^{n}\]
a tedy\[
F_{n}=\frac{A}{r_{1}^{n+1}}+\frac{B}{r_{2}^{n+1}}.\]
 
\end{example}
 
 
\begin{example}
Dokažte rovnost\[
\underbrace{\sum_{k\geq0}\binom{m}{k}\binom{n+k}{m}}_{a_{n}}=\underbrace{\sum_{k\geq0}\binom{m}{k}\binom{n}{k}2^{k}}_{b_{n}}\;\textrm{pro }m,n\geq0.\]
 
 
Dokážeme, že levá a pravá strana jsou koeficienty dvou OPS, které
mají stejné generující funkce. Z jednoznačnosti rozvoje se pak musí
rovnat i tyto koeficienty. Jak se ukáže, nemusíme ani znát konkrétní
hodnotu těchto koeficientů.
 
Nejprve hledejme generující funkci příslušnou posloupnosti $\left(a_{n}\right)_{n=0}^{\infty}$:\[
\sum_{n=0}^{\infty}a_{n}z^{n}=\sum_{n=0}^{\infty}\left(\sum_{k\geq0}\binom{m}{k}\binom{n+k}{m}\right)z^{n}=\sum_{k\geq0}\binom{m}{k}\sum_{n=0}^{\infty}\binom{n+k}{m}z^{n}=\]
... meze u sum omezíme na rozsah, kde jsou kombinační čísla $\binom{m}{k}$
a $\binom{n+k}{m}$ nenulová ...\[
=\sum_{k=0}^{m}\binom{m}{k}\sum_{n=0}^{\infty}\binom{n+k}{m}z^{n}=\sum_{k=0}^{m}\binom{m}{k}\sum_{n=m-k}^{\infty}\binom{n+k}{m}z^{n}=\]
... další úpravy směřujeme k použití rovnosti (\ref{eq:OPS_pravidlo_komb}).
Označme $j=n+k-m$ ...\[
=\sum_{k=0}^{m}\binom{m}{k}z^{m-k}\sum_{n=m-k}^{\infty}\binom{n+k-m+m}{m}z^{n+k-m}=\sum_{k=0}^{m}\binom{m}{k}z^{m-k}\underbrace{\sum_{j=0}^{\infty}\binom{j+m}{m}z^{j}}_{\frac{1}{\left(1-z\right)^{m+1}}}=\]
\[
=\frac{1}{\left(1-z\right)^{m+1}}\cdot\sum_{k=0}^{m}\binom{m}{k}1^{k}z^{m-k}=\frac{1}{\left(1-z\right)^{m+1}}\cdot\left(1+z\right)^{m}=\frac{\left(1+z\right)^{m}}{\left(1-z\right)^{m+1}}.\]
 
 
Nyní obdobným způsobem vypočítáme generující funkci příslušnou posloupnosti
$\left(b_{n}\right)_{n=0}^{\infty}$:
 
\[
\sum_{n=0}^{\infty}b_{n}z^{n}=\sum_{n=0}^{\infty}\left(\sum_{k\geq0}\binom{m}{k}\binom{n}{k}2^{k}\right)z^{n}=\sum_{k\geq0}\binom{m}{k}2^{k}\sum_{n=0}^{\infty}\binom{n}{k}z^{n}=\]
\[
=\sum_{k=0}^{m}\binom{m}{k}2^{k}\sum_{n=k}^{\infty}\binom{n}{k}z^{n}=\sum_{k=0}^{m}\binom{m}{k}2^{k}\underbrace{\sum_{n=0}^{\infty}\binom{n+k}{k}z^{n+k}}_{\frac{z^{k}}{\left(1-z\right)^{k+1}}}=\sum_{k=0}^{m}\binom{m}{k}2^{k}\frac{z^{k}}{\left(1-z\right)^{k+1}}=\]
\[
=\frac{1}{1-z}\sum_{k=0}^{m}\binom{m}{k}\left(\frac{2z}{1-z}\right)^{k}\cdot1^{m-k}=\frac{1}{1-z}\left(\frac{2z}{1-z}+1\right)^{m}=\frac{1}{1-z}\left(\frac{1+z}{1-z}\right)^{m}=\frac{\left(1+z\right)^{m}}{\left(1-z\right)^{m+1}}.\]
Obě generující funkce jsou si tedy skutečně rovny a proto platí i
$a_{n}=b_{n}$ pro každé $n\in\N_{0}$.
\end{example}
 
\subsection{Rozměňovací problém}
 
\begin{example}
\label{exa:money-chg}Hledejme počet různých řešení rovnice\begin{equation}
k_{1}+2k_{2}+3k_{3}=R,\label{eq:rovnice-money-chg-intro}\end{equation}
kde $k_{1,2,3}\in\N$ jsou neznámé a $R\in\N$. Jestliže vynásobíme
geometrické řady s kvocienty $q=x$,$q=x^{2}$ a $q=x^{3}$, dostaneme
součin\[
\left(x^{0}+x^{1}+x^{2}+x^{3}+...\right)\left(x^{0}+x^{2}+x^{4}+x^{6}+...\right)\left(x^{0}+x^{3}+x^{6}+x^{9}+...\right)=\]
\[
=\frac{1}{1-x}\cdot\frac{1}{1-x^{2}}\cdot\frac{1}{1-x^{3}}=\sum_{n=0}^{\infty}a_{n}x^{n}.\]
Výsledkem je opět mocninná řada, jejíž generující funkci známe. Koeficient
$a_{R}$ u členu $x^{R}$ pak udává počet řešení rovnice (\ref{eq:rovnice-money-chg-intro}),
neboť $x^{R}$ vznikne v daném součinu řad vždy jako součin\[
x^{R}=x^{k_{1}}x^{2k_{2}}x^{3k_{3}},\]
a tato mocnina $x$ se vyskytne ve výsledné řadě právě tolikrát, kolik
je různých řešení rovnice (\ref{eq:rovnice-money-chg-intro}).
\end{example}
Uvedený příklad je speciálním případem tzv. \textbf{rozměňovacího
problému} (angl. \emph{money changing problem}). Zabýváme se otázkou,
zda a případně kolika způsoby je možné zaplatit danou částku pouze
s pomocí mincí (nebo bankovek) určitých hodnot. Matematicky tento
problém definujeme následovně:
 
\begin{notation*}
\textbf{Největší společný dělitel} (NSD) množiny přirozených čísel
$\left\{ a_{1},...,a_{M}\right\} $ označujeme jako $\delta(a_{1},...,a_{M})$.
Jestliže $\delta(a_{1},...,a_{M})=1$, tak říkáme, že čísla $a_{1},...,a_{M}$
jsou \textbf{nesoudělná}.
\end{notation*}
\begin{defn}
Nechť jsou dána přirozená čísla $a_{1}<a_{2}<a_{3}<\cdots<a_{M}$
taková, že $\delta(a_{1},...,a_{M})=1$. Potom definujeme množinu\[
S(a_{1},...,a_{M})=\left\{ \left.\sum_{i=1}^{M}\alpha_{i}a_{i}\right|\alpha_{i}\in\N_{0}\right\} .\]
 
\end{defn}
\begin{rem*}
Množina $S$ obsahuje právě ty částky, které lze zaplatit pomocí $M$
různých druhů mincí s hodnotami $a_{1},...,a_{M}$. Je zřejmé, že
pokud by $\delta(a_{1},...,a_{M})>1$, tak by množina $S$ obsahovala
pouze (ale nikoliv právě) násobky $\delta(a_{1},...,a_{M})$.
\end{rem*}
\begin{thm}
\label{thm:money-chg}$\left(\exists n_{0}\right)\left(\forall n\geq n_{0}\right)\left(n\in S(a_{1},...,a_{m})\right)$.
\end{thm}
\begin{rem*}
Věta říká, že pro daný počet a hodnoty mincí lze od určité výše zaplatit
s jejich pomocí libovolnou částku. Tuto větu dokážeme později pomocí
OPS, ovšem dříve se zaměříme pouze na případ $M=2$, kdy lze o množině
$S$ říci něco více (například explicitně určit $n_{0}$). Pro tento
případ OPS potřebovat nebudeme.
\end{rem*}
 
\subsubsection{Rozměňovací problém pro $M=2$}
 
\begin{thm}
Nechť $a,b\in\N$, $a<b$, $\delta(a,b)=1$. Nechť $\kappa=(a-1)(b-1)$.
Potom
\begin{itemize}
\item $\left(\forall n\geq\kappa\right)\left(n\in S(a,b)\right)$,
\item $\kappa-1\notin S(a,b)$,
\item Právě polovina čísel z množiny $\{0,1,2,...,\kappa-1\}$ patří do
$S(a,b)$.
\end{itemize}
\end{thm}
\begin{rem*}
$S(a,b)=\left\{ \left.\alpha_{1}a+\alpha_{2}b\right|\alpha_{1},\alpha_{2}\in\N_{0}\right\} $.
Proto lze říci, že přirozené číslo $R\in S(a,b)$ právě tehdy, když
rovnice\[
ak_{1}+bk_{2}=R\]
 má řešení $k_{1},k_{2}\in\N_{0}$. Podle příkladu \ref{exa:money-chg}
nás tedy pro dané $R$ zajímá jen to, zda je koeficient u $x^{R}$
v určité mocninné řadě kladný nebo je roven nule.
\end{rem*}
\begin{proof}
Z algebry víme, že pro každá $a,b\in\Z$ existují $x,y\in\Z$ tak,
že $\delta(a,b)=ax+by$. V našem případě tedy $\exists x,y\in\Z$
taková, že\[
ax+by=1.\]
Díky tomu rovněž $\left(\forall n\in\N\right)\left(\exists\tilde{x},\tilde{y}\in\Z\right)\left(a\tilde{x}+b\tilde{y}=n\right)$.
Každé přirozené číslo tedy můžeme napsat jako lineární kombinaci čísel
$a,b$ s celočíselnými koeficienty. Nás však zajímá, kdy lze volit
tyto koeficienty jako nezáporné.
 
Nejprve si uvědomíme, že obecné řešení rovnice $ax+by=n$, $x,y\in\Z$,
má tvar\begin{equation}
(x,y)=(x_{p},y_{p})+(x_{0},y_{0}),\label{eq:partikul-reseni}\end{equation}
kde $(x_{0},y_{0})$ řeší homogenní rovnici $ax+by=0$ a $(x_{p},y_{p})$
představuje partikulární řešení. Vzhledem k nesoudělnosti čísel $a,b$
platí pro řešení homogenní rovnice $ax+by=0$ $\Leftrightarrow$ $ax=-by$
$\Rightarrow\begin{cases}
a|y & \Rightarrow y=r\cdot a\\
b|x & \Rightarrow x=s\cdot b\end{cases}$. Po dosazení máme $asb=-bra$ a tedy $s=-r$. Tím jsme ukázali, že
obecné řešení $(x,y)$ homogenní rovnice má tvar\[
(x,y)=(-rb,ra)=r(-b,a),\]
kde $r\in\Z$.
 
Stále zbývá otázka, kdy existují $x,y\geq0$ taková, že $ax+by=n$.
Abychom odpověděli, vyřešíme nejprve tuto rovnici v oboru celých čísel.
Je zřejmé, že složky řešení nebudou obě záporné, protože $a,b$ i
$n$ jsou přirozená čísla. Získali jsme tedy partikulární řešení rovnice
s pravou stranou, ke kterému můžeme přičíst $r(-b,a)$ a získat jiné
řešení naší rovnice. Naše otázka tedy přešla na otázku, kdy existuje
$r\in\Z$ takové, že výsledné řešení (\ref{eq:partikul-reseni}) je
nezáporné.
 
Zřejmě existuje právě jedno řešení $(\bar{x},\bar{y})$ takové, že
$\bar{x}\in\left\{ 0,1,2,...,b-1\right\} $ (skutečně, pomocí volby
$r$ můžeme $x$ posouvat po krocích o velikosti $b$). Takové $\bar{x}$
je nejmenší nezáporné, tj. \[
\bar{x}=\min\left\{ \left.x\right|ax+by=n\wedge x,y\in\Z\wedge x\geq0\right\} .\]
 $\bar{y}$ je pak dané jednoznačně a je největší možné, tj.\[
\bar{y}=\max\left\{ \left.y\right|ax+by=n\wedge x,y\in\Z\wedge x\geq0\right\} .\]
Proto $n\in S(a,b)$ právě tehdy, když (k němu jednoznačně příslušné)
$\bar{y}\geq0$.
 
Nyní již přímo dokážeme první tvrzení věty. Nechť $n\geq\kappa$.
Potom\begin{eqnarray*}
a\bar{x}+b\bar{y}=n & \geq & ab-a-b+1,\\
b\bar{y} & \geq & ab-a-a\bar{x}-b+1=\\
 &  & =a\underbrace{(b-1-\bar{x})}_{\geq0}-b+1,\\
\bar{y} & \geq & -1+\frac{1}{b}\;\;\leftarrow\left(\bar{y}\in\Z\textrm{, a tak platí také...}\right)\\
\bar{y} & \geq & 0.\end{eqnarray*}
To znamená, že $(\bar{x},\bar{y})$ je nezáporné a $n\in S(a,b)$.
 
Nyní nechť $n\in\left\{ 0,1,2,...,\kappa-1\right\} $. Potom $n\in S(a,b)$,
právě když \[
ax+by=n,\; x,y\geq0,x\in\left\{ 0,...,b-1\right\} ,\]
což je ekvivalentní s \[
\kappa-1-n=ab-a-b-ax-by=a\underbrace{(b-1-x)}_{=\tilde{x}\in\left\{ 0,...,b-1\right\} }+b\underbrace{(-1-y)}_{=\tilde{y}<0}.\]
Číslo $\tilde{x}$ je opět nejmenší nezáporné, takže poslední vztah
znamená, že $\kappa-1-n\notin S(a,b)$. Pro $n\in\left\{ 0,1,2,...,\kappa-1\right\} $
tedy v $S(a,b)$ leží vždy právě jedno z čísel $n$ a $\kappa-1-n$,
což dokazuje poslední bod.
 
Zbývá dokázat, že $\kappa-1\notin S(a,b)$, ale to je snadné s použitím
předchozího. Platí totiž $0=0\cdot a+0\cdot b\in S(a,b)$, takže $\kappa-1=\kappa-1-0\notin S(a,b)$.
\end{proof}
Nyní se vrátíme k OPS a s jejich pomocí odhadneme počet způsobů nakombinování
určité částky pomocí (stále jen) dvou typů mincí o různých hodnotách
$a,b$, $\delta(a,b)=1$. Z předchozí věty víme, že pro $n\geq\kappa=(a-1)(b-1)$
musí být tento počet kladný. \emph{Dovoluji si upozornit, že i když
následující řádky nepředstavují důkaz žádné věty, jsou velmi důležité
pro pochopení dalšího výkladu.}
 
Víme, že počet způsobů nakombinování částky $n$ je roven počtu nezáporných
celočíselných řešení rovnice\[
ax+by=n,\]
a podle příkladu \ref{exa:money-chg} též víme, že tento počet je
roven koeficientu i $x^{n}$ v mocninné řadě, která vznikne jako součin
řad\[
(1+x^{a}+x^{2a}+x^{3a}+...)\cdot(1+x^{b}+x^{2b}+x^{3b}+...),\]
protože $x^{n}$ vznikne jako $x^{ak_{1}}\cdot x^{bk_{2}}$. Mocninné
řady umíme sečíst, a tak víme, že generující funkce výsledné OPS je\[
f(x)=\frac{1}{1-x^{a}}\cdot\frac{1}{1-x^{b}}.\]
 
 
Jestliže chceme tuto funkci rozvinout do mocninné řady, bude třeba
provést její rozklad na parciální zlomky. Kořeny jmenovatelů jsou
řešeními binomické rovnice $\omega^{a}=1$, resp. $\omega^{b}=1$,
a jsou to tedy (v prvním případě) čísla $\left\{ \left.\e^{k\frac{2\pi}{a}i}\right|k=0,1,...,a-1\right\} $.
 
Kořeny celého jmenovatele, tj. $(1-x^{a})(1-x^{b})$, jsou tedy uvedeného
tvaru, přičemž $1$ je dvojnásobný kořen a ostatní kořeny jsou už
jednoduché. To dokážeme sporem. Nechť se rovnají kořeny\[
\e^{k_{1}\frac{2\pi}{a}i}=\e^{k_{2}\frac{2\pi}{b}i}.\]
Potom se rovnají i příslušné exponenty, takže\[
\frac{k_{1}}{a}=\frac{k_{2}}{b}=\frac{t}{s},\]
kde $\frac{t}{s}$ je zlomek ve zkráceném tvaru, a přitom (z definice
$k_{1},k_{2}$) je $\frac{t}{s}<1$, což znamená, že $s\geq2$. Protože
zlomek je ve zkráceném tvaru, tak $s|a$ a zároveň $s|b$, z čehož
plyne $s|\delta(a,b)$, ale $\delta(a,b)=1$, což je spor.
 
Rozklad na parciální zlomky má tedy tvar%
\footnote{Přirozenější tvar zlomků v sumách vpravo je asi $\frac{\tilde{C}_{\omega}}{\omega-x}$,
resp. $\frac{\tilde{D}_{\xi}}{\xi-x}$, kde $\tilde{C}_{\omega}=\omega C_{\omega}$
a $\tilde{D}_{\xi}=\xi D_{\xi}$. Pro rozvoj do mocninné řady pomocí
vztahu (\ref{eq:rozvoj-1-x-na-k-plus-1}) (viz. dále) se však spíše
hodí tvar použitý v (\ref{eq:rozklad-na-parc-zlomky}).%
}\begin{equation}
\frac{1}{(1-x^{a})(1-x^{b})}=\underbrace{\frac{A}{(1-x)^{2}}+\frac{B}{1-x}}_{\textrm{pro 2-násobný ko\v{r}en }1}+\sum_{\substack{\omega^{a}=1\\
\omega\neq1}
}\frac{C_{\omega}}{1-\frac{x}{\omega}}+\sum_{\substack{\xi^{b}=1\\
\xi\neq1}
}\frac{D_{\xi}}{1-\frac{x}{\xi}},\label{eq:rozklad-na-parc-zlomky}\end{equation}
kde koeficienty $A,B,C_{\omega},D_{\xi}$ zatím neznáme. Jak se dále
ukáže, bude pro naše účely stačit, pokud zjistíme hodnoty koeficientů
$A$ a $B$. To provedeme velmi šikovně.
 
Rovnost (\ref{eq:rozklad-na-parc-zlomky}) vynásobíme výrazem $(1-x)^{2}$
a provedeme limitu pro $x\to1$. Dostaneme tak\[
\lim_{x\to1}\frac{1-x}{1-x^{a}}\cdot\frac{1-x}{1-x^{b}}=A.\]
Limitu pravé strany jsme zde vypočítali rovnou, neboť je zřejmá na
první pohled. Pro výpočet limity nalevo použijeme l'Hospitalovo pravidlo
na jednotlivé zlomky, takže nakonec vyjde\[
A=\frac{1}{ab}.\]
 
 
Pro získání hodnoty $B$ opět vynásobíme (\ref{eq:rozklad-na-parc-zlomky})
výrazem $(1-x)^{2}$ a následně zderivujeme. Na pravé straně dostaneme
$-B$ plus sumu výrazů s koeficienty $C_{\omega}$ a $D_{\xi}$, z
nichž každý má tvar (uvedeme jen pro $C_{\omega}$)\[
\left(\frac{C_{\omega}}{1-\frac{x}{\omega}}(1-x)^{2}\right)'=\left(\frac{C_{\omega}}{1-\frac{x}{\omega}}\right)'(1-x)^{2}-2\frac{C_{\omega}}{1-\frac{x}{\omega}}(1-x).\]
Pokud nyní opět provedeme limitu pro $x\to1$, bude limita všech těchto
výrazů rovna nule, protože pro $x\to1$ je $\frac{C_{\omega}}{1-\frac{x}{\omega}}\to konst\neq0$.
Dostaneme tedy rovnost\[
\lim_{x\to1}\left(\frac{(1-x)^{2}}{(1-x^{a})(1-x^{b})}\right)'=B.\]
Limitu na pravé straně vypočítáme s dvojnásobným použitím l'Hospitalova
pravidla, až nakonec vyjde\[
B=\frac{a+b-2}{2ab}.\]
 
 
Nyní si vzpomeneme na příklad \ref{exa:OPS-simple-example-1}, kde
jsme odvodili rozvoj\begin{equation}
\frac{1}{(1-x)^{k+1}}=\sum_{n=0}^{\infty}\binom{n+k}{k}x^{n}.\label{eq:rozvoj-1-x-na-k-plus-1}\end{equation}
Jednotlivé členy rozkladu na parciální zlomky tedy rozvineme do řady
a obdržíme\[
\frac{1}{(1-x^{a})(1-x^{b})}=A\sum_{n=0}^{\infty}(n+1)x^{n}+B\sum_{n=0}^{\infty}x^{n}+\sum_{\substack{\omega^{a}=1\\
\omega\neq1}
}C_{\omega}\sum_{n=0}^{\infty}\frac{x^{n}}{\omega^{n}}+\sum_{\substack{\xi^{b}=1\\
\xi\neq1}
}D_{\xi}\sum_{n=0}^{\infty}\frac{x^{n}}{\xi^{n}}.\]
Jak jsme již uvedli, počet způsobů vyplacení částky $n$ je roven
koeficientu u $x^{n}$ v uvedené mocninné řadě, a tento koeficient
je roven (po dosazení hodnot $A,B$)\[
\frac{n+1}{ab}+\frac{a+b-2}{2ab}+\underbrace{\sum_{\substack{\omega^{a}=1\\
\omega\neq1}
}\frac{C_{\omega}}{\omega^{n}}+\sum_{\substack{\xi^{b}=1\\
\xi\neq1}
}\frac{D_{\xi}}{\xi^{n}}}_{\textrm{per}(n)}=\frac{n+1}{ab}+\frac{a+b-2}{2ab}+\textrm{per}(n).\]
Člen $\textrm{per}(n)$ je periodický s periodou $ab$ a součtet $\textrm{per}(n)$
přes periodu je $0$. Proto je uvedený počet způsobů od jistého $n$
určitě kladný.
 
Zbývá vysvětlit periodicitu členu $\textrm{per}(n)$. Protože $\omega^{a}=1$
a $\xi^{b}=1$, tak výraz $\frac{1}{\omega^{n}}$ má periodu $a$
a výraz $\frac{1}{\xi^{n}}$ má periodu $b$. Proto i celá suma $\sum_{\substack{\omega^{a}=1\\
\omega\neq1}
}\frac{C_{\omega}}{\omega^{n}}$ má periodu $a$ a suma $\sum_{\substack{\xi^{b}=1\\
\xi\neq1}
}\frac{D_{\xi}}{\xi^{n}}$ má periodu $b$. Celý součet má tedy periodu $ab$.
 
Nulový součet přes periodu zdůvodníme takto: Když $\omega^{a}=1$,
tak i $\frac{1}{\omega^{a}}=1$. Čísla $\frac{C_{\omega}}{\omega^{n}}$
jsou proto vrcholy pravidelného $a$-úhelníku, které leží v komplexní
rovině na kružnici o poloměru $C_{\omega}$. Jejich součet (přes periodu
o velikosti $a$) je těžištěm tohoto $a$-úhelníku, a toto těžiště
leží v nule. Stejně pro $\frac{D_{\xi}}{\xi^{n}}$ a součet přes periodu
o velikosti $b$.
 
 
\subsubsection{Rozměňovací problém pro obecné $M$}
 
Nyní se vrátíme k rozměňovacímu problému pro obecný počet typů mincí.
Pomocí OPS dokážeme větu \ref{thm:money-chg} a ještě něco navíc.
 
\begin{thm}
Nechť jsou dána přirozená čísla $1<a_{1}<a_{2}<\cdots<a_{M}$ taková,
že $\delta(a_{1},a_{2},...,a_{M})=1$. Potom\[
\left(\exists n_{0}\right)\left(\forall n\geq n_{0}\right)\left(n\in S(a_{1},...,a_{m})\right)\]
a přitom počet způsobů. kterými lze $n$ nakombinovat, se asymptoticky
blíží číslu\[
\frac{n^{M-1}}{(M-1)!\cdot a_{1}a_{2}\cdots a_{M}},\]
tj. limita podílu skutečného počtu způsobů a uvedeného výrazu pro
$n\to\infty$ je rovna $1$.
\end{thm}
\begin{rem*}
Speciálně pro $M=2$ vychází počet způsobů podle této věty přibližně
$\frac{n}{a_{1}a_{2}}=\frac{n}{ab}$ a v předchozím odvození jsme
dospěli k číslu $\frac{n+1}{ab}+\frac{a+b-2}{2ab}$ (až na periodický
člen). Pro $n\to\infty$ jde podíl obou výrazů skutečně k jedné.
\end{rem*}
\begin{proof}
Prostředky důkazu této věty budou velmi podobné myšlenkám, které jsme
předvedli v předchozím odvození pro $M=2$. Označme $h_{n}$ hledaný
počet způsobů pro dané $n$, tj. počet nezáporných celočíselných řešení
$(k_{1},...,k_{M})$ rovnice\[
\sum_{i=1}^{M}a_{i}k_{i}=n.\]
Potom (stále podle stejné úvahy) je $h_{n}$ rovněž koeficientem u
$x^{n}$ v mocninné řadě, která vznikne jako součin mocninných řad\[
(1+x^{a_{1}}+x^{2a_{1}}+...)(1+x^{a_{2}}+x^{2a_{2}}+...)\cdots(1+x^{a_{M}}+x^{2a_{M}}+...)=\frac{1}{1-x^{a_{1}}}\cdot\frac{1}{1-x^{a_{2}}}\cdots\frac{1}{1-x^{a_{M}}}.\]
Provedeme-li opět rozklad na parciální zlomky, podobně jako v předchozím
odvození zjistíme, že jmenovatel má kořeny určitého tvaru, přičemž
jediný $M$-násobný kořen je $1$. Ostatní kořeny (již nemusí mít
nutně násobnost $1$, ale) mají násobnost menší než $M$. Při ověření
tohoto tvrzení opět postupujeme sporem a využíváme předpokladu $\delta(a_{1},a_{2},...,a_{M})=1$.
 
Rozklad na parciální zlomky můžeme tedy zapsat ve tvaru\[
\frac{1}{1-x^{a_{1}}}\cdot\frac{1}{1-x^{a_{2}}}\cdots\frac{1}{1-x^{a_{M}}}=\frac{A}{(1-x)^{M}}+\sum_{\eta}\sum_{j=1}^{\nu(\eta)\leq M-1}\frac{C_{\eta,j}}{(1-\frac{x}{\eta})^{j}},\]
kde suma přes $\eta$ znamená sumu přes všechny kořeny jmenovatele
kromě kořenu $1$ a $\nu(\eta)$ označuje násobnost kořenu $\eta$.
Jediný koeficient rozkladu, který pro důkaz věty potřebujeme, je koeficient
$A$. Jestliže uvedenou rovnost vynásobíme výrazem $(1-x)^{M}$ a
provedeme limitu pro $x\to1$, dostaneme rovnost\[
\frac{1}{a_{1}a_{2}\cdots a_{M}}=A,\]
přičemž pro výpočet limity nalevo jsme museli použít l'Hospitalovo
pravidlo na každý zlomek $\frac{1-x}{1-x^{a_{i}}}$ zvlášť.
 
Nyní provedeme rozvoje jednotlivých sčítanců do mocninné řady podle
(\ref{eq:rozvoj-1-x-na-k-plus-1}), takže získáme\[
A\sum_{n=0}^{\infty}\binom{n+M-1}{M-1}x^{n}+\sum_{\eta}\sum_{j=1}^{\nu(\eta)\leq M-1}C_{\eta,j}\sum_{n=0}^{\infty}\binom{n+j-1}{j-1}\frac{x^{n}}{\eta^{n}}.\]
Koeficient u $x^{n}$, neboli $h_{n}$, je tedy roven\[
h_{n}=A\binom{n+M-1}{M-1}+\underbrace{\sum_{\eta}\sum_{j=1}^{\nu(\eta)\leq M-1}C_{\eta,j}\binom{n+j-1}{j-1}\frac{1}{\eta^{n}}}_{P(n)}.\]
$P(n)$ je polynom v proměnné $n$ stupně nejvýše $M-2$, protože
index $j$ dosahuje hodnoty nejvýše $M-1$. Pokud nyní provedeme limitu
pro $n\to\infty$ podílu $h_{n}$ a odhadu z dokazované věty, dostaneme\[
\lim_{n\to\infty}\frac{h_{n}}{\frac{n^{M-1}}{(M-1)!\cdot\underbrace{a_{1}a_{2}\cdots a_{M}}_{1/A}}}=\lim_{n\to\infty}\frac{\frac{(n+M-1)(n+M-2)\cdots(n+1)}{(M-1)!}+P(n)}{\frac{n^{M-1}}{(M-1)!}}=\]
\[
=\underbrace{\lim_{n\to\infty}\frac{(n+M-1)(n+M-2)\cdots(n+1)}{n^{M-1}}}_{=1}+(M-1)!\underbrace{\lim_{n\to\infty}\frac{P(n)}{n^{M-1}}}_{=0}=1.\]
 
\end{proof}
\begin{rem*}
Několik zajímavostí o rozměňovacím problému:
\begin{itemize}
\item Pro $M=3$, $a_{1}<a_{2}<a_{3}$ je od roku 1970 známa minimální částka,
kterou lze vyplatit.
\item Od roku 1942 je známa minimální částka, kterou lze zaplatit, pokud
$a_{1}<a_{2}<...<a_{M}$ tvoří aritmetickou posloupnost.
\item Pro $M\geq4$ ukázali Erdös a Graham, že maximální částka, kterou
nelze vyplatit, je $\leq2a_{M-1}\left\lfloor \frac{a_{M}}{M}\right\rfloor -a_{M}$.
\end{itemize}
\end{rem*}
 
\subsection{Tvrzení z teorie čísel dokazatelná pomocí OPS}
 
\begin{thm}
Množinu přirozených čísel nelze zapsat jako konečné disjunktní sjednocení
aritmetických posloupností s různými diferencemi.
\end{thm}
\begin{rem*}
Pokud připustíme shodné diference u alespoň dvou posloupností, tak
věta neplatí. Snadno si lze představit $\N$ jako sjednocení všech
sudých a lichých přirozených čísel, nebo jako\[
\N=\left\{ \left.2k\right|k\in\N\right\} \cup\left\{ \left.4k-3\right|k\in\N\right\} \cup\left\{ \left.4k-1\right|k\in\N\right\} .\]
 
\end{rem*}
\begin{proof}
Mějme posloupnosti $\left(a_{1}+nd_{1}\right)$,$\left(a_{2}+nd_{2}\right)$,...,$\left(a_{M}+nd_{M}\right)$
kde $M\geq2$ a nechť platí\[
1<d_{1}<d_{2}<...<d_{M}.\]
Předpokládejme, že tyto posloupnosti pokrývají celé $\N$. Sečteme-li
řady\[
x^{a_{1}}+x^{a_{1}+d_{1}}+x^{a_{1}+2d_{1}}+x^{a_{1}+3d_{1}}+...\]
\[
x^{a_{2}}+x^{a_{2}+d_{2}}+x^{a_{2}+2d_{2}}+x^{a_{2}+3d_{2}}+...\]
\[
\vdots\]
 \[
x^{a_{M}}+x^{a_{M}+d_{M}}+x^{a_{M}+2d_{M}}+x^{a_{M}+3d_{M}}+...,\]
musíme dostat řadu\[
x^{1}+x^{2}+x^{3}+x^{4}+...\left(=\sum\limits _{n=1}^{\infty}x^{n}\right)\]
Pokud nejprve vypočítáme součet každé řady zvlášť (všechny řady jsou
pro $x\in(0,1)$ absolutně konvergentní) a dosadíme do rovnosti mezi
součtem $M$ řad na levé straně a řadou $\sum\limits _{n=1}^{\infty}x^{n}$
na straně pravé, dostaneme rovnost\[
\frac{x^{a_{1}}}{1-x^{d_{1}}}+\frac{x^{a_{2}}}{1-x^{d_{2}}}+...+\frac{x^{a_{M}}}{1-x^{d_{M}}}=\frac{x}{1-x}.\]
Jmenovatel posledního sčítance nalevo má kořen $\e^{\frac{2\pi}{d_{M}}i}$
(kořen s nejmenším argumentem). Žádný jiný jmenovatel tento kořen
nemá, protože podle předpokladu je $d_{M}$ největší ze všech diferencí.
Pokud nyní v rovnosti provedeme limitu pro $x\to\e^{\frac{2\pi}{d_{M}}i}$,
dostaneme napravo konečné číslo a nalevo součet $M-1$ konečných čísel
a (komplexního) nekonečna, které je limitou posledního sčítance. To
je ale spor.
\end{proof}
\begin{thm}
Označme jako $r_{n}$ počet způsobů, jak zapsat číslo $n\in\N$ jako
součet přirozených čísel (bez ohledu na pořadí), kde sčítance jsou
různé. Podobně označme jako $l_{n}$ počet způsobů, jak zapsat číslo
$n\in\N$ jako součet přirozených čísel (bez ohledu na pořadí), kde
sčítance jsou liché. Potom $r_{n}=l_{n}$.
\end{thm}
\begin{example*}
V následujícím seznamu možností zápisu čísla $6$ jsou písmenem L
vyznačeny zápisy pomocí součtu lichých čísel a písmenem R zápisy pomocí
součtu různých čísel.\begin{eqnarray*}
\textrm{L }6 & = & 1+1+1+1+1+1\\
6 & = & 1+1+1+1+2\\
6 & = & 1+1+2+2\\
6 & = & 2+2+2\\
\textrm{L }6 & = & 1+1+1+3\\
\textrm{R }6 & = & 1+2+3\\
\textrm{L }6 & = & 3+3\\
6 & = & 1+1+4\\
\textrm{R }6 & = & 2+4\\
\textrm{LR }6 & = & 1+5\\
\textrm{R }6 & = & 6\end{eqnarray*}
 
\end{example*}
\begin{proof}
Nejprve ukážeme, že $r_{n}$ je koeficient u $x^{n}$ v mocninné řadě,
která vznikne po roznásobení výrazu\begin{equation}
(1+x)(1+x^{2})(1+x^{3})\cdots=\prod_{k=1}^{\infty}(1+x^{k}).\label{eq:vyraz-pro-rn}\end{equation}
To je ale v podstatě vidět, protože každý člen v této mocninné řadě
je tvaru $A\cdot x^{a_{1}}\cdot x^{a_{2}}\cdot x^{a_{3}}\cdots x^{a_{M}}$,
kde $M\in\N$ a $a_{1},a_{2},...,a_{M}$ jsou navzájem různé. Pokud
máme pochybnosti o konvergenci nekonečného součinu, můžeme jej zlogaritmovat:\begin{equation}
\ln\prod_{k=1}^{\infty}(1+x^{k})=\sum_{k=1}^{\infty}\ln(1+x^{k})\label{eq:zlogaritmovana-rada}\end{equation}
a přitom\[
\lim_{x\to0}\frac{\ln(1+x^{k})}{x^{k}}=1.\]
Řada (\ref{eq:zlogaritmovana-rada}) má tedy stejný poloměr konvergence
jako řada $\sum\limits _{k=0}^{\infty}x^{k}$, takže pro $x\in[0,1)$
konverguje. Proto konverguje i původní produkt.
 
Dále platí, že $l_{n}$ je koeficient u $x^{n}$ ve výrazu\begin{equation}
(1+x+x^{2}+x^{3}+...)\cdot(1+x^{3}+x^{6}+x^{9}+...)\cdot(1+x^{5}+x^{10}+x^{15}+...)\cdots=\prod_{k=1}^{\infty}\sum_{j=0}^{\infty}x^{\left(2k-1\right)j}.\label{eq:vyraz-pro-ln}\end{equation}
Pro dané $n$ totiž $x^{n}$ vznikne vždy jako součin\[
x^{n}=x^{k_{1}}\cdot x^{3k_{2}}\cdot x^{5k_{3}}\cdots x^{(2M-1)k_{M}},\]
kde $M\in\N$ a $k_{i}\in\N_{0}$. To je ekvivalentní s rovností\[
n=k_{1}+3k_{2}+5k_{3}+...+(2M-1)k_{M},\]
která však znamená jen to, že $n$ lze zapsat jako součet lichých
čísel\[
n=\underbrace{1+1+...+1}_{k_{1}\textrm{-krát}}+\underbrace{3+3+...+3}_{k_{2}\textrm{-krát}}+\underbrace{5+5+...+5}_{k_{3}\textrm{-krát}}+...+\underbrace{(2M-1)+(2M-1)+...+(2M-1)}_{k_{M}\textrm{-krát}}.\]
 
 
Pokud ověříme, že oba výrazy (\ref{eq:vyraz-pro-rn}) a (\ref{eq:vyraz-pro-ln})
jsou si rovny, bude to znamenat i $r_{n}=l_{n}$. Ve výrazu (\ref{eq:vyraz-pro-ln})
sečteme sumy tvořící jednotlivé činitele, neboť se jedná o geometrické
řady. Dostaneme tak celkem\begin{equation}
\prod_{k=1}^{\infty}\frac{1}{1-x^{2k-1}},\label{eq:vyraz-pro-ln-2}\end{equation}
což se má rovnat výrazu \[
\prod_{k=1}^{\infty}(1+x^{k}).\]
Pokud si rozepíšeme\[
1+x^{k}=\frac{1-x^{2k}}{1-x^{k}},\]
tak potom už je vidět, že skutečně\[
\prod_{k=1}^{\infty}(1+x^{k})=\prod_{k=1}^{\infty}\frac{1-x^{2k}}{1-x^{k}}=\prod_{k=1}^{\infty}\frac{1}{1-x^{2k-1}},\]
protože právě všechny členy se sudými mocninami $x$ se vykrátí (to
je paradox nekonečného součinu...).
\end{proof}
\begin{example}
Mějme čísla $a_{1}<a_{2}<...<a_{n}\in\Z$ a uvažujme všechny rozdíly
$(a_{j}-a_{i})$ , kde $j>i$, což jsou všechno přirozená čísla. Potom
řekneme, že posloupnost $a_{1},a_{2},..,a_{n}$ tvoří \textbf{dokonalé
pravítko}, jestliže\begin{equation}
\left(\forall k,1\leq k\leq\binom{n}{2}\right)\left(\exists i,j\in\hat{n}\right)\left(a_{j}-a_{i}=k\right),\label{eq:def-dokon-pravitko}\end{equation}
tj. když všechna přirozená čísla od $1$ do $\binom{n}{2}$ lze vyjádřit
jako rozdíl vhodné dvojice čísel z posloupnosti $a_{1},a_{2},..,a_{n}$.
 
Například pro $n=4$ je $\binom{4}{2}=6$ a posloupnost $(0,1,4,6)$
tvoří dokonalé pravítko.
\end{example}
\begin{thm}
Pro $n\geq5$ dokonalé pravítko neexistuje.
\end{thm}
\begin{proof}
I tuto větu dokážeme s použitím OPS. Nechť $n\in\N$ a posloupnost
$(a_{1},...,a_{n})$ tvoří dokonalé pravítko. Definujme polynom\[
A(z)=z^{a_{1}}+z^{a_{2}}+...+z^{a_{n}}\]
a uvažujme součin polynomů $A(z)\cdot A(z^{-1})$. Po prostém roznásobení
vznikne celkem $n^{2}$ sčítanců, přičemž mezi nimi bude $\binom{n}{2}=\frac{n(n-1)}{2}$
párů tvaru $z^{a_{i}-a_{j}}$ a $z^{a_{j}-a_{i}}$, kde $i\neq j$
(neboť tolika způsoby lze vybrat dvě různá čísla z $\hat{n}$ \emph{bez
ohledu} na pořadí), a zbylých $n$ sčítanců budou jednotky ($z^{0}$).
 
Z vlastnosti dokonalého pravítka (\ref{eq:def-dokon-pravitko}) nalezneme
každé číslo od $1$ do $\binom{n}{2}$ jako rozdíl $a_{j}-a_{i}$
pro nějaké $i<j$. Součin $A(z)\cdot A(z^{-1})$ je tedy roven\begin{equation}
A(z)\cdot A(z^{-1})=\boxed{(n-1)}+z^{-\binom{n}{2}}+z^{-\left(\binom{n}{2}-1\right)}+...+z^{-1}+\boxed{z^{0}}+z^{1}+z^{2}+...+z^{\binom{n}{2}-1}+z^{\binom{n}{2}}.\label{eq:soucin-dok-prav}\end{equation}
Čísla v rámečku dohromady tvoří výše zmíněných $n$ jednotek v roznásobení
součinu. Označme nyní\[
N=\binom{n}{2}.\]
Součin (\ref{eq:soucin-dok-prav}) bez konstanty $n-1$ tvoří geometrickou
řadu, kterou sečteme podle známého vzorce, když vytkneme $z^{-N}$:\[
A(z)\cdot A(z^{-1})=(n-1)+z^{-N}\frac{z^{2N+1}-1}{z-1}=(n-1)+\frac{z^{N+\frac{1}{2}}-z^{-N-\frac{1}{2}}}{z^{\frac{1}{2}}-z^{-\frac{1}{2}}}.\]
 
 
Pokud nyní dosadíme speciálně $z=\e^{i\varphi}$, dostaneme\[
A\left(\e^{i\varphi}\right)A\left(\e^{-i\varphi}\right)=(n-1)+\frac{\e^{i\varphi\left(N+\frac{1}{2}\right)}-\e^{-i\varphi\left(N+\frac{1}{2}\right)}}{\e^{\frac{i\varphi}{2}}-\e^{-\frac{i\varphi}{2}}}=(n-1)+\frac{\sinh\left(i\varphi\left(N+\frac{1}{2}\right)\right)}{\sinh\left(i\frac{\varphi}{2}\right)}=(n-1)+\frac{\sin\left(\varphi\left(N+\frac{1}{2}\right)\right)}{\sin\left(\frac{\varphi}{2}\right)}.\]
Čísla $\e^{i\varphi}$ a $\e^{-i\varphi}$ jsou však komplexně sdružená,
takže platí i $A\left(\e^{-i\varphi}\right)=\overline{A\left(\e^{i\varphi}\right)}$,
a tedy\[
A\left(\e^{i\varphi}\right)A\left(\e^{-i\varphi}\right)=\left|A\left(\e^{i\varphi}\right)\right|^{2}\geq0,\]
Pro každé $\varphi$ tak musí platit\[
A\left(\e^{i\varphi}\right)A\left(\e^{-i\varphi}\right)=(n-1)+\frac{\sin\left(\varphi\left(N+\frac{1}{2}\right)\right)}{\sin\left(\frac{\varphi}{2}\right)}\geq0.\]
Z této nerovnosti již získáme omezení na $n$. Jinými slovy ukážeme,
že pro $n\geq5$ již tato nerovnost neplatí. Zvolme $\varphi$ tak,
aby $\sin\left(\varphi\left(N+\frac{1}{2}\right)\right)=-1$, tj.
$\varphi\left(N+\frac{1}{2}\right)=\frac{3}{2}\pi$, takže\[
\varphi=\frac{\frac{3}{2}\pi}{N+\frac{1}{2}}=\frac{\frac{3}{2}\pi}{\frac{n(n-1)}{2}+\frac{1}{2}}=\frac{3\pi}{n^{2}-n+1}.\]
I pro toto $\varphi$ musí postupně platit\begin{eqnarray*}
(n-1)-\frac{1}{\sin\frac{3\pi}{2\left(n^{2}-n+1\right)}} & \geq & 0,\\
\sin\frac{3\pi}{2\left(n^{2}-n+1\right)} & \geq & \frac{1}{n-1},\\
\frac{3\pi}{2\left(n^{2}-n+1\right)} & \geq & \frac{1}{n-1},\\
\underbrace{\frac{3\pi}{2}}_{\approx4.71} & \geq & \frac{n^{2}-n+1}{n-1}=n+\frac{1}{n-1},\end{eqnarray*}
přičemž jsme využili, že $x\geq\sin x$ pro $x\in\left(0,\frac{\pi}{2}\right)$.
Je však vidět, že pro $n\geq5$ již tato nerovnost splněna není.
\end{proof}
\begin{example}
Mějme naměřená data $d_{1},...,d_{N-1}$ a hledejme hodnoty neznámé
veličiny $y_{1},...,y_{N-1}$, jestliže je znám rekurentní vztah\begin{equation}
ay_{i+1}+by_{i}+cy_{i-1}=d_{i}\qquad\forall i=1,2,3,...,N-1\label{eq:prikl-OPS-rekurence}\end{equation}
a hodnoty (okrajové podmínky) $y_{0},y_{N}$. Koeficienty $a,b,c$
jsou známé a předpokládáme $a,c\neq0$, jinak by byla úloha triviální.
 
Definujme polynomy\begin{eqnarray*}
D(x) & = & \sum_{i=1}^{N-1}d_{i}x^{i},\\
Y(x) & = & \sum_{i=1}^{N-1}y_{i}x^{i}.\end{eqnarray*}
Nyní všechny rovnosti (\ref{eq:prikl-OPS-rekurence}) vynásobíme $x^{i}$
a sečteme přes $i$ od $1$ do $N-1$. Dostaneme\[
a\sum_{i=1}^{N-1}y_{i+1}x^{i}+b\sum_{i=1}^{N-1}y_{i}x^{i}+c\sum_{i=1}^{N-1}y_{i-1}x^{i}=D(x).\]
Podle definice polynomu $Y(x)$ lze tuto rovnost dále přepsat na\[
\frac{a}{x}\left(Y(x)-y_{1}x+y_{N}x^{N}\right)+bY(x)+cx\left(Y(x)-y_{N-1}x^{N-1}+y_{0}\right)=D(x).\]
Celou rovnost vynásobíme $x$ a po vytknutí $Y(x)$ dostaneme\[
Y(x)\left(a+bx+cx^{2}\right)=x\left(ay_{1}+cy_{N-1}x^{N}+D(x)-ay_{N}x^{N-1}-cy_{0}x\right).\]
Nechť $r_{1}.r_{2}$ jsou kořeny rovnice $cx^{2}+bx+a=0$, pro jednoduchost
různé. Potom platí\begin{eqnarray*}
0 & = & ay_{1}+cy_{N-1}r_{1}^{N}+D(r_{1})-ay_{N}r_{1}^{N-1}-cy_{0}r_{1},\\
0 & = & ay_{1}+cy_{N-1}r_{2}^{N}+D(r_{2})-ay_{N}r_{2}^{N-1}-cy_{0}r_{2},\end{eqnarray*}
což je soustava dvou lineárních rovnic pro $y_{1}$ a $y_{N-1}$ s
determinantem\[
\left|\begin{array}{cc}
a & cr_{1}^{N}\\
a & cr_{2}^{N}\end{array}\right|\neq0,\]
protože $r_{1}\neq r_{2}$. Jejím řešením získáme hodnoty $y_{1},y_{N-1}$
a dospějeme tedy ke stejné úloze, avšak pouze pro $\left(N-1\right)-2$
neznámých $y_{2},...,y_{N-2}$. Rozmyslete si, co se stane, když $r_{1}=r_{2}$.
\end{example}