\documentclass[11pt,a4paper]{book}
\usepackage{a4wide}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{array}
\usepackage{enumerate}
\usepackage{paralist}


\DeclareMathOperator{\tg}{tg}
\DeclareMathOperator{\cotg}{cotg}
\DeclareMathOperator{\ch}{ch}
\DeclareMathOperator{\sh}{sh}
\DeclareMathOperator{\tgh}{tgh}
\DeclareMathOperator{\cotgh}{cotgh}
\newcommand{\dx}{\,\mathrm{d}x}
\newcommand{\dt}{\,\mathrm{d}t}
\newcommand{\ds}{\,\mathrm{d}s}

\newcommand{\I}{{\rm i}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\ce}[1]{\ensuremath{\left(#1 \right)}}	% definice \ce 	- argument bude v~kulatych zavorkach
\newcommand{\cce}[1]{\ensuremath{\left[#1 \right]}}	% definice \cce	- argument bude v~hranatych zavorkach

\newcommand{\kon}[3]{\ensuremath{{#1} \equiv {#2}\pmod{#3}}}
\newcommand{\imp}{\ensuremath{\Rightarrow}}
\newcommand{\ekv}{\ensuremath{\Leftrightarrow}}
\newcommand{\gon}[1]{\ensuremath{ \cos \frac{2\pi}{#1} + \I \sin \frac{2\pi}{#1}}}

\newcommand{\psl}[1]{\ensuremath{\{{#1 }_n\}_{n=1}^\infty}}


\newtheorem{pr}{Příklad}
\newtheorem{pr*}[pr]{*Příklad}
\newtheorem*{veta}{Věta}
\newtheorem*{lemma}{Lemma}
\theoremstyle{definition}
\newtheorem*{definice}{Definice}
\theoremstyle{remark}
\newtheorem*{pozn}{Poznámka}
\newtheorem*{odb}{Odbočka}


\renewcommand{\qedsymbol}{}		% zmena znaku na konci dukazu

\parindent=0mm
\pagestyle{empty}
\begin{document}
\setcounter{chapter}{6}
\chapter{Posloupnosti}
\begin{definice}
\emph{Posloupností (reálných čísel)} rozumíme zobrazení $a \colon \N \to \R$. Hodnoty se místo $a\ce{n}$ značí obvykle $a_n$. Celou posloupnost zapisujeme $\psl{a}$ nebo jen $\{a_n\}$, případně $\ce{a_n}$. Hodnotu $a_n$ nazýváme \emph{$n$-tý člen posloupnosti}.
\end{definice}
\begin{pozn}
Posloupnost lze zadat rekurentním vzorcem (spolu s tzv. počátečními podmínkami), například
\begin{gather*}
a_1 = 1,\\
a_{n+1} = 2\cdot a_n +1,
\end{gather*}
explicitním vzorcem pro $n$-tý člen, například
\[
a_n = 2^n - 1.
\]
\end{pozn}
\section{Aritmetická posloupnost}
\begin{definice}
Posloupnost $\psl{a}$ se nazývá aritmetická, jestliže $\exists\,d \in \R~\forall\,n \in \N\colon a_{n+1} = a_n + d$. Číslo $d$ se nazývá diferencí aritmetické posloupnosti $\psl{a}$.
\end{definice}
\begin{veta}
Nechť $\psl{a}$ je aritmetická posloupnost s diferencí $d$. Pak platí:
\begin{itemize}
\item $\forall\,n \in \N \colon a_n = a_1 + \ce{n-1}d$
\item $\forall\,r,s \in \N \colon a_r = a_s + \ce{r-s}d$
\item označíme-li $s_n = a_1 + a_2 + \dots + a_n$ součet prvních $n$ členů, pak
\[
s_n = n\cdot\frac{a_1 + a_n}{2}
\]
\end{itemize}
\end{veta}
\begin{veta}
Posloupnost $\psl{a}$ je aritmetická právě tehdy, když $\forall\,n\in \N\setminus\{1\}$ platí 
\[
a_n = \frac{a_{n+1} + a_{n-1}}{2}.
\]
\end{veta}
%
%\section{Limita posloupnosti}
%\begin{definice}
%Nechť je dána posloupnost $\psl{a}$ a číslo $A \in \R$. Řekneme, že posloupnost $\psl{a}$ \emph{má vlastní limitu} $A$, jestliže ke každému $\epsilon > 0 $ existuje $n_0 \in \N$ takové, že pro každé $n \geq n_0$ platí $|a_n - a| < \epsilon$. V tomto případě říkáme, že posloupnost $\psl{a}$ \emph{konverguje}, značíme
%\[
%\lim\limits_{n \to \infty} a_n = A.
%\]
%Řekneme, že posloupnost $\psl{a}$ \emph{má nevlastní limitu} $+\infty$ (respektive $-\infty$), jestliže ke každému $A \in \R$ existuje $n_0 \in \N$ takové, že pro každé $n \geq n_0$ platí, že $a_n > A$ (respektive $a_n < A$). V tomto případě říkáme, že posloupnost $\psl{a}$ \emph{diverguje}, značíme 
%\[
%\lim\limits_{n \to \infty} a_n = \infty \quad (\text{respektive} \lim\limits_{n \to \infty} a_n = -\infty).
%\]
%\end{definice}
%\begin{veta}
%Každá posloupnost má nejvýše jednu limitu.
%\end{veta}
%\begin{veta}
%Nechť $\lim\limits_{n \to \infty} a_n = 0$ a posloupnost $\psl{b}$ je ohraničená. Pak $\lim\limits_{n \to \infty} a_n \cdot b_n = 0$.
%\end{veta}
%\begin{veta}
%Nechť $\lim\limits_{n \to \infty} a_n = a$, $\lim\limits_{n \to \infty} b_n = b$, kde $a, b \in \R$. Pak
%\begin{itemize}
%\item $\lim\limits_{n \to \infty} |a_n| = |a|$,
%\item $\lim\limits_{n \to \infty} \ce{a_n \pm b_n} = a\pm b$,
%\item $\lim\limits_{n \to \infty} \ce{a_n \cdot b_n} = a \cdot b$,
%\item Pokud $b, b_n \neq 0$, tak $\lim\limits_{n \to \infty} \frac{a_n}{b_n} = \frac{a}{b}$,
%\item $\lim\limits_{n \to \infty} c \cdot a_n = c\cdot\lim\limits_{n \to \infty} a_n$.
%\end{itemize}
%\end{veta}
%\begin{pozn}
%Eulerovo číslo $e$ se často definuje jako limita posloupnosti $\lim\limits_{n \to \infty} \ce{1 + \frac{1}{n}}^n$.
%\end{pozn}
%\section{Nekonečné řady}
%\begin{definice}
%Nechť $\{a_n\}_{n=1}^{\infty}$ je posloupnost reálných čísel. Formální výraz
%\[
%\sum_{n=1}^{\infty} a_n
%\]
%nazýváme \emph{nekonečnou číselnou řadou}. Posloupnost $\{s_n\}_{n=1}^{\infty}$, kde
%\[
%s_1 = a_1, \quad s_2 = a_1 + a_2, \quad s_n = \sum_{i=1}^n a_i
%\]
%nazýváme \emph{posloupnost částečných součtů} této řady. Existuje-li limita $\lim_{n \to \infty}s_n = s \in \R$, řekneme, že řada $\sum_{n=1}^{\infty}$ \emph{konverguje} a má součet $s$. Jestliže vlastní limita neexistuje, řekneme, že řada \emph{diverguje}.
%\end{definice}
%\begin{pozn}
%\emph{Geometrická řada} je tvaru $a + aq + aq^2 + \dots = \sum_{i=1}^{\infty} aq^{n-1}$, kde $a,q \neq 0$. Číslo $q$ se nazývá \emph{kvocient} geometrické řady.\\
%Snadno rozmyslíme, že pro $q \neq 1$ je $s_n = a + aq + \dots + a q^{n-1} = a\frac{1-q^n}{1-q}$.
%\end{pozn}
%
\section{Diferenční rovnice}
Diference $\Delta y(n)=y(n+1)-y(n)$. Opakem je sumace: $\Delta a(n)= b(n)$ pak $\sum b(n)=a(n)$. Obecně je výsledkem sumace množina všech řešení, lišící se o~konstantu, podobně jako u~integrálu.\\
Vlastnosti diference a sumace:
\begin{align*}
\Delta (a_n+b_n)&= \Delta a_n + \Delta b_n &\sum (a_n+b_n)&= \sum a_n + \sum b_n\\
\Delta (c\cdot a_n)&= c\cdot \Delta a_n& \sum (c\cdot a_n)&= c \sum a_n\\
\Delta (a_n\cdot b_n)&= (\Delta a_n)\cdot b_{n+1} + a_n\cdot \Delta b_n&  \sum a_n\cdot \Delta b_n &= a_n\cdot b_n - \sum  (\Delta a_n)\cdot b_{n+1}\\
\Delta \left(\frac{a_n}{b_n}\right)&= \frac{(\Delta a_n)\cdot b_{n} - a_n\cdot \Delta b_n}{b_n b_{n+1}}
\end{align*}
Vztahy ($q\neq1$, $P_k,Q_k$ polynomy stupně $k$):
\begin{align*}
\Delta c&=0\\
\Delta n&=1\\
\Delta n^k&=\sum_{i=0}^{k-1} {k\choose i} n^i\\
\Delta P_k (n)&=Q_{k-1}(n) &\sum P_k(n)&=Q_{k+1}(n)+c\\
\Delta q^n&=(q-1)q^n & \sum q^n &= \frac{q^n}{q-1}+c\\
\Delta q^n P_k (n)&=q^n Q_k(n)& \sum q^n P_k (n)&=q^n Q_k(n)+c
\end{align*}

Homogenní diferenční rovnice 1.~řádu
$$y(n+1)=p(n)y(n)\text.$$
Řešení $y(n)=y(1) \prod\limits_{k=1}^{n-1} p(k)= c\prod\limits_{k=1}^{n-1} p(k)$.\\
Nehomogenní
\begin{compactenum}
\item $\Delta y(n) = y(n+1)-y(n)=r(n)$, pak $y(n)=\sum r(n) +c$;
\item $y(n+1)-p(n)y(n)=r(n)$, pak řešení je ve~tvaru řešení příslušné zhomogenizované rovnice $u(n+1)=p(n)u(n)$ a~jednoho řešení partikulárního, které hledáme ve~tvaru $y_p(n)=u(n)v(n)$.
\end{compactenum}
Homogenní diferenční rovnice 2.~řádu s~konstantními koeficienty
$$y(n+2)+ay(n+1)+by(n)=0\text.$$
Charakteristická rovnice $\lambda^2+a\lambda+b=0$ má
\begin{compactenum}
\item dva různé reálné kořeny $\lambda_1\neq \lambda_2$, pak $y(n)=c_1\lambda_1^n + c_2\lambda_2^n$;
\item reálný dvojnásobný kořen $\lambda$, pak $y(n)=c_1\lambda^n + c_2n\lambda^n$;
\item komplexní kořeny $\lambda_{1,2}=\alpha \pm \I\beta =r(\cos \varphi \pm\I \sin\varphi)$, pak $y(n)=r^n(c_1\cos n\varphi + c_2\sin n\varphi)$.
\end{compactenum}

Součet prvních $n$ členů posloupnosti
\begin{align*}
s_n&=a_1+a_2+\dots+a_n\\
s_{n+1}&=a_1+a_2+\dots+a_n+a_{n+1}\\
\Delta s_n&=s_{n+1} -s_n=a_{n+1}\\
s_n&= \sum a_{n+1},\quad s_1=a_1
\end{align*}
%
\newpage
\section{Příklady}
\begin{pr}%[A58i-4]
Nechť $\psl{a}$ značí aritmetickou posloupnost přirozených čísel.
\begin{itemize}
\item Nalezněte příklad posloupnosti $\psl{a}$, která obsahuje nekonečně mnoho $k$-tých mocnin přirozených čísel pro všechna $k = 2,3,\dots$
\item Nalezněte příklad posloupnosti $\psl{a}$, která neobsahuje žádnou $k$-tou mocninu přirozeného čísla pro žádné $k = 2,3,\dots$
\item Nalezněte příklad posloupnosti $\psl{a}$, která neobsahuje žádnou druhou mocninu přirozeného čísla, ale obsahuje nekonečně mnoho třetích mocnin přirozených čísel.
\item Dokažte, že pro libovolnou posloupnost $\psl{a}$ a všechna přirozená čísla $k \geq 2$ platí: Posloupnost $\psl{a}$ buď neobsahuje žádnou $k$-tou mocninu přirozeného čísla, nebo jich obsahuje nekonečně mnoho.
\end{itemize}
\end{pr}
\begin{pr}%[A54s-1]
Nechť $\psl{a}$ značí aritmetickou posloupnost celých čísel. Kolik existuje aritmetických posloupností $\psl{a}$ takových, že $a_i = 1$, $a_j = 2015$ pro nějaké indexy $i,j \in \{1,2,\dots,20\}$?
\end{pr}
\begin{pr}%[A54i-4]
Uvažujme dvě aritmetické posloupnosti reálných čísel $\psl{x}$ a $\psl{y}$, které mají stejný první člen (tj. $x_1 = y_1$) a existuje index $k \in \N \setminus \{1\}$ takový, že
\begin{itemize}
\item $x_k^2 - y_k^2 = 53$,
\item $x_{k-1}^2 - y_{k-1}^2 = 78$,
\item $x_{k+1}^2 - y_{k+1}^2 = 27$.
\end{itemize}
Nalezněte všechny přípustné hodnoty indexu $k$.
\end{pr}
%%%%%
\begin{pr*}
Vypočtěte limity posloupností $\psl{a}$, které jsou zadané vzorcem pro $n$-tý člen
\begin{itemize}
\item $a_n = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n\cdot \ce{n+1}}$
\item $a_n = \frac{1-2+3-4+\dots +2n-1 - 2n}{\sqrt{n^2 + 1}}$
\item $a_n = n \cdot \ce{\sqrt{n^2 +1} - n}$
\end{itemize}
\end{pr*}
%%%%%
\begin{pr}%[A57i-4]
Určete počet konečných rostoucích posloupností přirozených čísel $a_1, a_2, \dots, a_k$ všech možných délek $k$, pro které platí:
\begin{itemize}
\item $a_1 = 1$,
\item $a_i \mid a_{i+1}$ pro $i = 1,2,\dots,k-1$,
\item $a_k = 255\,255$.
\end{itemize}
\end{pr}
\begin{pr}%[A50i-2]
Buď $\psl{a}$ posloupnost přirozených čísel a pro každé $n \in \N \setminus \{1\}$ je $a_{n+1}$ o~1 větší než největší lichý dělitel součtu $a_n + a_{n-1}$. Dokažte, že posloupnost $\psl{a}$ je (od určitého členu počínaje) periodická.
\end{pr}
%%%
\newpage
\begin{pr}%[A55i-3]
Nechť $\psl{a}$ je posloupnost nenulových celých čísel a pro každé $n \in \N$ platí $a_{n+1} = a_n - b_n$, kde číslo $b_n$ má stejné znaménko jako číslo $a_n$, ale opačné pořadí číslic. \begin{itemize}
\item Dokažte, že posloupnost $\psl{a}$ je (od určitého členu počínaje) periodická.
\item Dokažte, že první člen $a_1$ musí být alespoň čtyřciferné číslo.
\end{itemize}
\end{pr}
\begin{pr}%[A55iii-1]
Nechť $\psl{a}$ je posloupnost přirozených čísel a pro každé $n \in \N$ platí $a_{n+1} = a_n + b_n$, kde číslo $b_n$ má opačné pořadí číslic než číslo $a_n$ (v dekadickém zápise). Dokažte, že $a_7$ nemůže být prvočíslo. S výhodou lze využít kritéria dělitelnosti jedenácti.
\end{pr}
\begin{pr}%[A55ii-2]
Posloupnost reálných čísel $\psl{a}$ splňuje pro každé $n\in\N$ rovnost
\[
\frac{a_{n+3} - a_{n+2}}{a_n - a_{n+1}} = \frac{a_{n+3} + a_{n+2}}{a_n + a_{n+1}}
\]
a navíc platí $a_{11} = 4$, $a_{22} = 2$, $a_{33} = 1$. Dokažte, že pro každé $k \in \N$ je součet
\[
a_1^k + a_2^k + \dots + a_{100}^k
\]
druhou mocninou přirozeného čísla.
\end{pr}
\begin{pr*}
Na spořicí účet s úrokovou sazbou 5\% za rok ukládáme na začátku každého roku po dobu deseti let 20\,000 korun.
\begin{itemize}
\item Kolik korun bude na účtu na konci desátého roku?
\item Odvoďte obecný vztah pro velikost úložky $x$, úrokovou sazbu $i$ a délku spoření $n$ (roků).
\end{itemize}
\end{pr*}
\begin{pr}
Řešte rovnici $$y(n+1)-ny(n)=(n+1)!,\qquad y(1)=5\text.$$
\end{pr}


\begin{pr}
Kolik slov délky $n$ lze sestavit z~písmen A, B, C tak, aby žádné z~nich neobsahovalo podslovo AC nebo BC?
\end{pr}


\begin{pr}
Řešte rovnice
\begin{compactenum}[\quad a)]
\item $y(n+2)-9y(n+1)+18y(n)=0$;
\item $y(n+2)-8y(n+1)+16y(n)=0$;
\item $y(n+2)-2y(n+1)+2y(n)=0$.
\end{compactenum}
\end{pr}


\begin{pr}
Určete explicitní vyjádření Fibonacciho posloupnosti.
\end{pr}


\begin{pr}
Kolik slov délky $n$ lze sestavit z~písmen A, B, C tak, aby žádné z~nich neobsahovalo podslovo AA, AB, BA, BB?
\end{pr}


\begin{pr}
Určete součet prvních $n$ členů posloupnosti $a_n=n^2$.
\end{pr}

\begin{pr}
Určete součet prvních $n$ členů posloupnosti $y_n={\left( -\frac13\right)}^n n$.
\end{pr}
%%%%%%%%%%
\newpage
\subsection*{Řešení}
\begin{proof}[Řešení 1]
\begin{itemize}
\item Stačí uvážit například posloupnost $a_1 = 1$, $d = 1$.
\item Stačí uvážit například posloupnost $a_1 = 2$, $d = 4$. Pro $n$-tý člen dostáváme $a_n = 2 + 4(n-1) = 2 \cdot (2n-1)$. V rozkladu na prvočísla je dvojka vždy v první mocnině, proto žádný člen nemůže být $k$-tou mocninou přirozeného čísla.
\item Stačí uvážit například posloupnost $a_1 = 8$, $d = 16$. Pro $n$-tý člen dostáváme $a_n = 8 + 16(n-1) = 8 \cdot (2n-1)$. V rozkladu na prvočísla je dvojka vždy v třetí mocnině, proto žádný člen nemůže být druhou mocninou přirozeného čísla. Protože $2n-1$ pro $n \in \N$ proběhne všechna lichá čísla, jistě bude v této posloupnosti nekonečně mnoho (dokonce všechny) třetích mocnin přirozených čísel.
\item Nechť posloupnost obsahuje nějakou $k$-tou mocninu přirozeného čísla $m$, tj. pro vhodné $n \in \N$ platí $m^k = a_1 + n\cdot d$. Ukažme, že v této posloupnosti budou ležet i čísla $\ce{m+d}^k$, $\ce{m+2d}^k, \dots$ Uvažme obecný člen z těchto $k$-tých mocnin a s využitím binomické věty ho rozepišme:
\[
\ce{m+td}^k = \sum_{i = 0}^k \binom{k}{i}m^{k-i}\ce{td}^i = m^k + d\underbrace{\cdot \sum_{i = 1}^k \binom{k}{i}m^{k-i}t^id^{i-1}}_{N} = m^k + dN = a_1 + \ce{n+N}d.
\]
\end{itemize}
\end{proof}
%
\begin{proof}[Řešení 2]
Nejprve určeme všechny možné diference. Protože $\psl{a}$ je posloupnost celých čísel, musí být diference $d \in \Z$. Víme, že $a_i = a_j + \ce{i-j}d$, odtud $d = \frac{a_i - a_j}{i-j} = \frac{2014}{i-j}$. Vidíme, že $d \mid 2014 = 2 \cdot 19 \cdot 53$, navíc $1 \leq |i-j| \leq 19$. Odtud $d \in \{\pm 2014, \pm 1007, \pm 106\}$. Jednotlivé případy rozebereme
\begin{itemize}
\item $d = 2014$, pak $j = i+1$. Aby $i,j \in \{1,2,\dots,20\}$, musí $i \in \{1,\dots, 19\}$. Podobně pro $d = -2014$ je $j = i-1$ a tedy $i \in \{2,\dots,20\}$.
\item $d = 1007$, pak $j = i+2$. Podobně jako výše dostáváme $i \in \{1,\dots 18\}$. Pro $d = -1007$ máme $i \in \{3,\dots, 20\}$.
\item $d = 106$, pak $j = i+19$, nutně tedy $i = 1$, $j = 20$. Pro $d = -106$ máme $i = 20$ a $j = 1$.
\end{itemize}
Celkem dostáváme 76 možných posloupností.
\end{proof}
%
\begin{proof}[Řešení 3]
Označme $c,d$ diference zadaných posloupností. Dostáváme vyjádření
\[
x_i = x_1 + \ce{i-1}c \qquad y_i = x_1 + \ce{i-1}d.
\]
Vypočtemě rozdíl $x_i^2 - y_i^2$
\begin{multline*}
x_i^2 - y_i^2 = \ce{x_1^2 + 2x_1\ce{i-1}c + \ce{i-1}^2c^2} - \ce{x_1^2 + 2x_1\ce{i-1}d + \ce{i-1}^2d^2} =\\
= 2x_1\ce{i-1}\ce{c-d} + \ce{i-1}^2\ce{c^2-d^2}.
\end{multline*}
Ze zadání tak dostáváme soustavu rovnic
\begin{align*}
53 &= 2x_1\ce{k-1}\ce{c-d} + \ce{k-1}^2\ce{c^2-d^2},\\
78 &= 2x_1\ce{k-2}\ce{c-d} + \ce{k-2}^2\ce{c^2-d^2},\\
27 &= 2x_1k\ce{c-d} + k^2\ce{c^2-d^2},
\end{align*}
což je vlastně soustava tří nelineárních rovnic o třech neznámých $x_1\ce{c-d}$, $c^2 - d^2$ a $k$, z nichž nám stačí určit jen tu poslední. Jednoduše se dokážeme zbavit proměnné $x_1\ce{c-d}$, když od dvojnásobku první rovnice odečteme rovnice zbývající. Dostáváme
\[
1 = \ce{2\ce{k-1}^2 - \ce{k-2}^2 - k^2}\cdot\ce{c^2 - d^2} = -2 \cdot \ce{c^2 - d^2}
\]
Odtud $c^2 - d^2 = -\frac{1}{2}$. Dosazením do druhé a třetí rovnice dostáváme
\begin{align*}
78 &= 2x_1\ce{k-2}\ce{c-d} - \frac{1}{2}\ce{k-2}^2,\\
27 &= 2x_1 k \ce{c-d} - \frac{1}{2}k^2.
\end{align*}
Opět se zbavme členů s $x_1\ce{c-d}$.
\begin{align*}
78k - 27\ce{k-2} &= -\frac{1}{2}\ce{k\ce{k-2}^2 - k^2\ce{k-2}}\\
102k + 108 &= k^3 - 2k^2 - k^3 + 4k^2 -4k\\
0 &= k^2 - 53k - 54\\
0 &= \ce{k+1}\ce{k-54}
\end{align*}
Protože $k \in \N$, je jediným řešením $k = 54$.
\end{proof}
%
\begin{proof}[Řešení 4]
\begin{itemize}
\item 
Protože $\frac{1}{n\cdot \ce{n+1}} = \frac{1}{n} - \frac{1}{n+1}$, můžeme limitu zadané posloupnosti psát jako
\[
\lim_{n \to \infty} \frac{1}{1\cdot 2} + \dots + \frac{1}{n \cdot \ce{n+1}} = \lim_{n \to \infty} 1 - \frac{1}{2} + \frac{1}{2} - \frac{1}{3} + \dots + \frac{1}{n} - \frac{1}{n-1} = \lim_{n \to \infty} 1 - \frac{1}{n+1} = 1.
\]
\item Nejprve spočítejme
\begin{gather*}
1+3+\dots + \ce{2n-1} = n\frac{2n-1+1}{2} = n^2,\\
2+4+\dots + 2n = n\frac{2n+2}{2} = n^2 + n.
\end{gather*}
Nyní spočtěme samotnou limitu
\[
\lim_{n \to \infty} \frac{1-2+3-4+\dots + \ce{2n-1} - 2n}{\sqrt{n^2 + 1}} = \lim_{n \to \infty} \frac{-n}{\sqrt{n^2 + 1}} = \lim_{n\to\infty} \frac{-1}{\sqrt{1 + \frac{1}{n^2}}} = -1
\]
\item 
\[
\lim_{n \to \infty} n \cdot \ce{\sqrt{n^2 +1} - n} = \lim_{n \to \infty} n \frac{n^2 + 1 - n^2}{\sqrt{n^2 + 1} + n} = \lim_{n \to \infty} \frac{1}{\sqrt{1+\frac{1}{n^2}}+1} = \frac{1}{2}.
\]
\end{itemize}
\end{proof}
%
%%%%%%%%%%%%%%%
\newpage
%%%%%%%%%%%%%%%
\begin{proof}[Řešení 5]
Nejprve rozložme číslo 255\,255 na prvočísla
\[
255\,255 = 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17.
\]
Z podmínky $a_i \mid a_{i+1}$ dostáváme, že každý člen obsahuje v prvočíselném rozkladu stejná prvočísla jako člen předchozí a alespoň jeden navíc (aby posloupnost byla rostoucí). Stačí se tedy dívat, jaká prvočísla přibudou v rozkladu dalšího členu (vždy bude alespoň jedno) oproti členu předchozímu. Chceme tedy množinu $X = \{3,5,7,11,13,17\}$ rozdělit do neprázdných podmnožin $X_1, X_2, \dots$, kde $X_i$ značí, která prvočísla přibudou v rozkladu při přechodu od $a_i$ k $a_{i+1}$.\\
Označme $P\ce{n}$ počet rozdělení $n$-prvkové množiny do neprázdných podmnožin. Hodnotu $P\ce{n}$ vyjádříme rekurentním vztahem. Každé rozdělení lze vyjádřit jako počet možností pro $X_1$ krát rozdělení zbytku. Musíme uvážit všechny možné velikosti $j$ množiny $X_1$. Tím dostáváme vztah
\[
P\ce{n} = 1 + \sum_{j=1}^{n-1} \binom{n}{j}P\ce{n-j},
\]
kde jednička na začátku odpovídá situaci, kdy $X = X_1$ a není co dál rozdělovat, index $j$ odpovídá velikosti množiny $X_1$ a $\binom{n}{j}$ je počet možností jak těchto $j$ prvků do $X_1$ vybrat. Nyní snadno dopočítáme $P\ce{6}$.\\
$P\ce{1} = 1$, $P\ce{2} = 3$, $P\ce{3} = 13$, $P\ce{4} = 75$, $P\ce{5} = 541$ a konečně $P\ce{6} = 4\,683$.
\end{proof}
%
\begin{proof}[Řešení 6]
Označme $a^*$ největšího lichého dělitele čísla $a$.
\begin{itemize}
\item Pro každé $n \geq 3$ je $a_n$ číslo sudé (vždyť je to číslo o 1 větší než lichý dělitel nějakého čísla).
\item Pro každé $n \geq 4$ je $a_{n+1} \leq \max\{a_{n}, a_{n-1}\}$.
\[
a_{n+1} = 1 + \ce{a_{n} + a_{n-1}}^* \leq 1 + \frac{a_{n} + a_{n-1}}{2} \leq 1 + \max\{a_n + a_{n-1}\}.
\]
První nerovnost plyne ze sudosti čísel $a_n$ a $a_{n-1}$, druhá je triviální. Proto je posloupnost $\psl{a}$ ohraničená. Její největší člen je totiž jeden z prvních čtyř.
\item Protože každý člen závisí pouze na dvou předchozích, dostáváme hned, že existence dvojic $\ce{a_n, a_{n+1}} = \ce{a_m, a_{m+1}}$ pro $n < m$ nám dá periodicitu. Označíme-li $M$ největší člen posloupnosti, pak každá dvojice \ce{a_n, a_{n+1}} je tvaru $\ce{a,b}$ pro $a,b \in \{1,\dots,M\}$. Těchto dvojic je pouze $M^2$, a proto se nějaká dvojice jistě bude muset opakovat.
\end{itemize}
\end{proof}
%
\begin{proof}[Řešení 7]
\begin{itemize}
\item Protože hodnota $n$-tého člene závisí jen a pouze na členu předchozím, stačí nám ukázat, že se v posloupnosti nacházejí dvě stejná čísla. Odtud už hned plyne periodicita. Ukážeme, že posloupnost je ohraničená. Protože hodnoty jsou celá čísla, bude jen konečně mnoho hodnot, kterých mohou členy posloupnosti nabývat. Proto se v této nekonečné posloupnosti budou nacházet dvě stejná čísla. Jestliže začneme s $k$-ciferným číslem, jistě bude každý člen posloupnosti nejvýše $k$-ciferné číslo, tedy $-10^k < a_n < 10^k$. Tímto máme dokázánu periodicitu.
\item Žádný člen posloupnosti nemůže být číslem, které čteme zepředu stejně jako zezadu (zejména tedy ani jednociferným číslem), druhý člen by pak byl nulový, což nelze (máme posloupnost nenulových celých čísel).\\
Jestliže začneme s dvouciferným číslem $10a+b$ bude druhý člen tvaru $9\ce{a-b}$. Nyní stačí uvážit posloupnost kroků
\[
90 - 9 \to 81-18 \to 63-36 \to 27-72 \to -45+54 \to 9
\]
Máme-li tedy v posloupnosti dvojciferné číslo dělitelné devíti, po několika krocích dostaneme jednociferné číslo, o kterém jsme ukázali, že v posloupnosti ležet nemůže. Celkem tedy nemůže být $a_1$ ani dvouciferné číslo.\\
Uvažme, že $a_1$ je libovolné trojciferné číslo tvaru $100a + 10b + c$, pak $a_2 = 99\ce{a-c}$. Uvážíme posloupnost kroků
\[
900 - 9 \to 891-198 \to 693-396 \to 297-792 \to -495 + 594 \to 99
\]
V posloupnosti se tedy nesmí nacházet ani trojciferné číslo.
\end{itemize}
Pro úplnost dodejme, že nejmenší přípustné přirozené číslo $a_1$ je $1012$.
\end{proof}
%
\begin{proof}[Řešení 8]
\begin{itemize}
\item Podívejme se na číslo $x = 10^k x_k + 10^{k-1} x_{k-1} + \dots + 10^1 x_1 + 10^0 x_0$ modulo~11
\[
x = 10^k x_k + 10^{k-1} x_{k-1} + \dots + 10^1 x_1 + 10^0 x_0 \equiv \ce{-1}^k x_k + \ce{-1}^{k-1}x_{k-1} + \dots -x_1 + x_0 \pmod{11}
\]
Jestliže $y$ má opačné pořadí čísel než $x$, pak $x \equiv \pm y \pmod{11}$, přičemž znaménko plus nastává, právě když má $x$ lichý počet cifer. Má-li $x$ sudý počet cifer, pak
\[
x \equiv -y \pmod{11} \quad \Rightarrow \quad 11 \mid x+y.
\]
Což nám s výjimkou $x = 10$ dává v dalším členu posloupnosti složené číslo dělitelné jedenácti. Navíc platí, že jakmile je jeden člen posloupnosti dělitelný jedenácti, budou jedenácti dělitelné také všechny další.
\item Nyní ukážeme, že pro libovolné $a_1 \in \N$ má nejpozději člen $a_6$ sudý počet cifer. Protože $a_6 > 10$, bude pak jistě $a_7$ složené číslo dělitelné jedenácti. Předpokládejeme tedy sporem, že $a_1, \dots, a_6$ mají lichý počet cifer. Protože je posloupnost rostoucí, musí i počet cifer růst. Jistě ale součet dvou nejvýše $k$-ciferných čísel nemůže dát číslo $k+2$-ciferné. Proto $a_1, \dots, a_6$ mají stejný počet cifer. Označme $c_i$ první a $d_i$ poslední cifru čísla $a_i$. Pak 
\begin{align*}
c_2 &\geq c_1+d_1 & d_2 &\geq c_1+d_1\\
c_3 &\geq 2\ce{c_1+d_1} &  d_3 &\geq 2\ce{c_1+d_1}\\
c_4 &\geq 4\ce{c_1 + d_1} & d_4 &\geq 4\ce{c_1+d_1}\\
c_5 &\geq 8\ce{c_1 + d_1} & d_5 &\geq 8\ce{c_1+d_1}\\
c_6 &\geq 16\ce{c_1 + d_1} & d_6 &\geq 16\ce{c_1+d_1}
\end{align*}
Protože je ale $\ce{c_1 + d_1} \geq 1$, tak číslo $16\ce{c_1 + d_1}$ nemůže být cifrou v dekadickém zápisu. Dostáváme spor. Proto má nejpozději číslo $a_6$ sudý počet cifer a tedy číslo $a_7$ nemůže být prvočíslem.\\
Pro úplnost doplňme, že číslo $a_6$ být prvočíslem může. Pro $a_1 = 10\,220$ vyjde číslo $a_6 = 185\,767$.
\end{itemize}
\end{proof}
%
\begin{proof}[Řešení 9]
\begin{itemize}
\item Nejprve ukažme, že $a_n = 0 \Leftrightarrow a_{n+3} = 0$.\\
\uv{$\Rightarrow$} Dosaďme do zadané rovnosti $a_n = 0$
\begin{align*}
\frac{a_{n+3} - a_{n+2}}{- a_{n+1}} &= \frac{a_{n+3} + a_{n+2}}{a_{n+1}}\\
-a_{n+3} + a_{n+2} &= a_{n+3} + a_{n+2}\\
a_{n+3} &= 0
\end{align*}
\uv{$\Leftarrow$} Obdobně dosaďme za $a_{n+3} = 0$
\begin{align*}
\frac{- a_{n+2}}{a_n - a_{n+1}} &= \frac{a_{n+2}}{a_n + a_{n+1}}\\
a_n + a_{n+1} &= -a_n + a_{n+1}\\
a_n &= 0
\end{align*}
Odtud z podmínek $a_{11}, a_{22}, a_{33} \neq 0$ plyne, že žádný člen posloupnosti $\psl{a}$ není nulový.
\item Zadanou rovnost roznásobíme a zjednodušíme, čímž dostáváme
\[
a_{n+3}a_{n+1} = a_{n+2}a_n.
\]
Totéž můžeme uvážit pro $n+1$ místo $n$, což dává
\[
a_{n+4}a_{n+2} = a_{n+3}a_{n+1}.
\]
Vynásobením obou rovností a vykrácení (nenulovým) číslem $a_{n+1}a_{n+2}a_{n+3}$ dostáváme
\[
a_{n+4} = a_n.
\]
Posloupnost $\psl{a}$ je tedy periodická s periodou 4. Dostáváme
\[
a_1 = a_{33} = 1, \quad a_2 = a_{22} = 2, \quad a_3 = a_{11} = 4, \quad a_4 = a_3a_1/a_2 = 2,
\]
a odtud
\[
a_1^k + a_2^k + a_{100}^k = 25\ce{1^k + 2^k + 4^k + 2^k} = \ce{5 \ce{1+2^k}}^2.
\]
\end{itemize}
\end{proof}
%
\begin{proof}[Řešení 10]
Odvodíme nejprve obecný vztah, do kterého potom dosadíme. Označme $S$ částku, která bude na účtu na konci. Platí
\[
S = x\ce{1+i} + x\ce{1+i}^2 + \dots + x\ce{1+i}^n = x\ce{1+i}\frac{\ce{1+i}^n - 1}{i}.
\]
Přitom člen $x\ce{1+i}$ odpovídá poslední úložce (která se úročí jen poslední rok), člen $x\ce{1+i}^n$ první úložce (která se úročí všech $n$ let), ostatní analogicky.\\
Dosazením za $x = 20\,000$, $n = 10$ a $i = 0,05$ dostáváme výsledek první části úlohy:
\[
S = 20\,000 \cdot 1,05 \frac{\ce{1,05}^{10} - 1}{0,05} \approx 264\,135,74.
\]
\end{proof}

\begin{proof}[Řešení 11]
Homogenní: $y(n+1)=n y(n)=n(n-1)y(n-1) =\dots= c\cdot n!\;\imp\; y(n)=c\cdot (n-1)!$.\\
Partikulární řešení ve tvaru $y_p(n)=c(n)\cdot (n-1)!$.
\begin{align*}
c(n+1)\cdot n! -n c(n)\cdot (n-1)!&=(n+1)!\\
n! [ c(n+1)-c(n)]&=(n+1)!\\
\Delta c(n) &= n+1\\
c(n)&= \sum (n+1) = an^2+bn\\
n+1&= a(2n+1)+b\\
n^1\colon\quad 1&= 2a \,\imp\, a=\frac12\\
n^0\colon\quad 1&= a+b \,\imp\, b=\frac12
\end{align*}
\begin{align*}
y_p(n)&= \left( \frac12 n^2 +\frac12n\right) (n-1)!=\frac12 (n+1)!\\
y(n)&= \frac12 (n+1)! + c\cdot (n-1)!\\
y(1)&=\frac12 \cdot 2  + c =1+c=5\;\imp\; c=4\\
y(n)&= \frac12 (n+1)! + 4(n-1)!
\end{align*}
\end{proof}

\begin{proof}[Řešení 12]
Libovolné slovo můžeme prodloužit připojením A,B, připojením C jen v~případě, že jde o~slovo ze samých C. Slova délky jedna jsou 3. Takže $$y(n+1)=2y(n)+1\text.$$
Homogenní: $y(n+1)=2y(n)=2\cdot 2 y(n-1) = \dots = 2^n u(1)=2 = c2^n \;\imp\; y(n)=c2^{n-1}$.\\
Partikulární řešení ve tvaru $y_p(n)=c(n)2^{n-1}$.
\begin{align*}
c(n+1)2^{n} -2c(n)2^{n-1}&=1\\
2^n [ c(n+1)-c(n)]&=1\\
\Delta c(n) &= {\left( \frac12 \right)}^n\\
c(n)&= \sum {\left( \frac12 \right)}^n = \frac{{\left( \frac12 \right)}^n}{\frac12-1} = -2 \frac1{2^n}=-2^{1-n}\\
y_p(n)&=-2^{1-n}\cdot 2^{n-1} = -2^0=-1
\end{align*}
\begin{align*}
y(n)&=c2^{n-1} -1\\
y(1)&=c2^0 -1=c-1=3\;\imp\; c=4\\
y(n)&=4\cdot 2^{n-1} -1=2^{n+1} -1
\end{align*}
\end{proof}

\begin{proof}[Řešení 13]
\begin{compactenum}[\quad a)]
\item \begin{align*}
\lambda^2-9\lambda+18&=0\\
(\lambda-3)(\lambda-6)&=0\\
\lambda_1=3&\phantom{=} \lambda_2=6\\
y(n)&=c_1 3^n +c_2 6^n
\end{align*}
\item \begin{align*}
\lambda^2-8\lambda+16&=0\\
(\lambda-4)^2&=0\\
\lambda&=4\\
y(n)&=c_1 4^n +c_2 n 4^n
\end{align*}
\item \begin{align*}
\lambda^2-2\lambda+2&=0\\
D&=4-8=-4\\
\lambda_{1,2}&=\frac{2\pm2\I}{2}=1\pm\I = \sqrt{2}\left(\cos\frac\pi4 \pm\sin\frac\pi4\right)\\
y(n)&={\big(\sqrt{2}\big)}^n \left(c_1\cos n\frac\pi4 + c_2\sin n\frac\pi4\right)
\end{align*}
\end{compactenum}
\end{proof}

\begin{proof}[Řešení 14]
$$y(n+2)=y(n+1)+y(n),\qquad y(1)=y(2)=1$$
\begin{align*}
y(n+2)-y(n+1)-y(n)&=0\\
\lambda^2-\lambda-1&=0\\
\lambda_{1,2}&=\frac{1\pm\sqrt5}{2}\\
y(n)&= c_1 {\left(\frac{1+\sqrt5}{2}\right)}^n + c_2 {\left(\frac{1-\sqrt5}{2}\right)}^n
\end{align*}
\begin{align}
y(1)=1\colon\quad c_1 {\left(\frac{1+\sqrt5}{2}\right)} + c_2 {\left(\frac{1-\sqrt5}{2}\right)} &=1\label{fib1} \\
y(2)=1\colon\quad c_1 {\left(\frac{1+\sqrt5}{2}\right)}^2 + c_2 {\left(\frac{1-\sqrt5}{2}\right)}^2 &=1\label{fib2}\\
\frac{1+\sqrt5}{2} \eqref{fib1} - \eqref{fib2}\colon\quad  c_2 \left[ \frac{1-5}4 - \frac{1-2\sqrt5+5}{4} \right] &= \frac{1+\sqrt5}{2} -1 \notag\\
c_2 \left[ \frac{-5+\sqrt5}{2} \right] &= \frac{-1+\sqrt5}{2} \notag\\
c_2 = \frac{-1+\sqrt5}{-5+\sqrt5}& = -\frac{1}{\sqrt5} \notag\\
c_1 {\left(\frac{1+\sqrt5}{2}\right)} &= \frac{1}{\sqrt5}  {\left(\frac{1-\sqrt5}{2}\right)} +1 \notag \\
c_1 {\left(\frac{1+\sqrt5}{2}\right)} &= \frac{1+\sqrt5}{2\sqrt5} \notag \\
c_2 & = \frac{1}{\sqrt5} \notag
\end{align}
$$y(n)= \frac{1}{\sqrt5}\left[ {\left(\frac{1+\sqrt5}{2}\right)}^n - {\left(\frac{1-\sqrt5}{2}\right)}^n \right]$$
\end{proof}


\begin{proof}[Řešení 15]
Slovo délky $n+2$ končící A nebo B můžeme vytvořit ze~slov délky~$n$ připojením CA nebo CB, končící C ze~slov délky $n+1$ připojením~C, takže $y(n+2)=2y(n)+y(n+1)$. Slov délky jedna je 3, délky dva 5. Takže $$y(n+2)-y(n+1)-2y(n)=0,\qquad y(1)=3,y(2)=5 \text.$$
\begin{align*}
y(n+2)-y(n+1)-2y(n)&=0\\
\lambda^2-\lambda-2&=0\\
(\lambda-2)(\lambda+1)&=0\\
\lambda_1=2&\phantom{=} \lambda_2=-1\\
y(n)&=c_1 2^n +c_2 (-1)^n\\
y(1)=3\colon\quad 2c1-c_2&=3\\
y(2)=5\colon\quad 4c1+c_2&=5\\
6c_1=8\;&\imp\; c_1=\frac43\\
c_2&=2c_1-3 = -\frac13
\end{align*}
\begin{align*}
y(n)&= \frac43\cdot 2^n -\frac13\cdot (-1)^n\\
y(n)&= \frac13\Big[ 2^{n+2} +(-1)^{n+1}\Big]
\end{align*}
\end{proof}


\begin{proof}[Řešení 16]
$$s_n=1^2 +2^2 +\dots +n^2,\qquad s_1=1$$
$$s_n=\sum (n+1)^2 = \sum (n^2+2n+1)=an^3 bn^2+cn+d$$
$$n^2+2n+1=a(3n^2+3n+1)+ b(2n+1)+c$$
\begin{align*}
n^2\colon\quad 1&=3a \,\imp\, a=\frac13\\
n^1\colon\quad 2&=3a+2b=1+2b \,\imp\, b=\frac12\\
n^0\colon\quad 1&=a+b+c=\frac13+\frac12+c \,\imp\, c=\frac16
\end{align*}
\begin{align*}
s_n&=\frac13 n^3 +\frac12 n^2 +\frac16 n +d\\
s_1&=\frac13  +\frac12 +\frac16 +d=1+d=1\,\imp\, d=0\\
s_n&=\frac13 n^3 +\frac12 n^2 +\frac16 n =\frac{n(2n^2+3n+1)}{6}=\frac{n(2n+1)(n+1)}{6}
\end{align*}
\end{proof}


\begin{proof}[Řešení 17]
\begin{align*}
s_n&=\sum {\left( -\frac13\right)}^{n+1} (n+1) = \begin{vmatrix}a_n=n+1 & \Delta b_n ={\left( -\frac13\right)}^{n+1}\\ \Delta a_n=1 & b_n= \frac{{\left( -\frac13\right)}^{n+1}}{-\frac13-1}=-\frac34 {\left( -\frac13\right)}^{n+1} \end{vmatrix} =\\
&= (n+1) \left(-\frac34\right) {\left( -\frac13\right)}^{n+1} + \frac34 \sum {\left( -\frac13\right)}^{n+2} =\\
&= (n+1) \left(-\frac34\right) {\left( -\frac13\right)}^{n+1} + \frac34 \frac{{\left( -\frac13\right)}^{n+2}}{-\frac13-1}+c =\\
&= (n+1) \left(-\frac34\right) {\left( -\frac13\right)}^{n+1} -  \frac9{16} {\left( -\frac13\right)}^{n+2}+c\\
&= \frac1{16} {\left( -\frac13\right)}^n (4n+3)
\end{align*}
\begin{align*}
s_1&=-\frac{7}{48}+c =-\frac13\,\imp\,c=-\frac3{16}\\
s_n&= \frac1{16} {\left( -\frac13\right)}^n (4n+3) -\frac3{16}
\end{align*}
\end{proof}
\end{document}