Posloupnosti

Tento článek je zápisem přednášky o Posloupnostech pana Dalibora Šmída PhD..


Úvod

Posloupnost je v matematice soubor prvků nějaké množiny, který je lineárně uspořádán a prvky v něm se mohou opakovat. Příklady:

Posloupnost může být i nekonečná, například (2,4,8,16,...)(2,4,8,16,...), což můžeme zapsat jako (2n)n=1\left(2n\right)^{\infty}_{n=1}, případně (2n)nN\left(2n\right)_{n \in \N}. Obecnouposloupnost prvků nějaké množiny XX indexovanou přirozenými čísly zapisujeme jako:

(a1,a2,a3,...)(an)1, kde nN:anX\left( a_1, a_2, a_3, ... \right) \equiv (a_n)^{\infty}_1 , \text{ kde } \forall n \in \N : a_n \in X

Na takovou posloupnost se můžeme dívat jako na zobrazení f:NXf:\N \rightarrow X, které číslu nn přiřazuje prvek ana_n. Můžeme uvažovat i posloupnosti nekonečné na obě strany (an)\left( a_n \right)^{\infty}_{− \infty}, které odpovídají zobrazením množiny ZZ všech celých čísel do množiny XX. Podobným způsobem lze zapsat i konečné posloupnosti:

(a1,a2,a3,...,an)(an)n=1N\left( a_1, a_2, a_3, ... , a_n \right) \equiv \left( a_n \right)^{N}_{n=1}

odpovídá zobrazení f:{1,...,N}X,f(n):=anf:\{1,...,N\} \rightarrow X, f(n) := a_n

V dalším budeme předpokládat, že X=RX=R. Na reálných číslech máme definovány operace sčítání, odčítání a násobení, pomocí nichž můžeme definovat analogické operace na posloupnostech:

(an)1+(bn)1:=(an+bn)1(an)1(bn)1:=(anbn)1(an)1(bn)1:=(an+bn)1λ(an)1:=(λan)1, kde λR\begin{aligned} (a_n)^\infty_1 + (b_n)^\infty_1 &:= (a_n + b_n)^\infty_1 \\ (a_n)^\infty_1 - (b_n)^\infty_1 &:= (a_n - b_n)^\infty_1 \\ (a_n)^\infty_1(b_n)^\infty_1 &:= (a_n + b_n)^\infty_1 \\ \lambda(a_n)^\infty_1 &:= (\lambda a_n)^\infty_1, \text{ kde } \lambda \in \R \end{aligned}

Operace definované člen po členu jsou v souladu sestandardním zavedením operací na reálných funkcích, např. pro ff, g:NRg:\N \rightarrow \R:

(f+g)(n):=f(n)+g(n)(f + g)(n) := f(n) + g(n)

Posloupnost lze zadat explicitně, tedy vlastně předpisem pro funkci ff.

Příklady:


Limity posloupnosti

Limita posloupnosti (an)1(a_n)^{\infty}_1 je reálné číslo LL takové, že libovolně malý interval (Lε,L+ε)(L−ε,L+ε) obsahuje pro určité NN všechny členy posloupnosti s n>Nn > N. Zapisujeme:

limnan=L\lim_{n \rightarrow \infty} a_n =L

Příklady:

Limita posloupnosti částečných součtů nekonečné řady senazývá součtem řady. Základní příklad je geometrická řada s kvocientem q(1,1)q \in (−1,1):

n=1bqn1:=limNn=1Nbgn1=limnbqN1q1=b1q\sum^\infty_{n=1} bq^{n-1} := \lim_{N \rightarrow \infty}\sum^N_{n=1} bg^{n-1} = \lim_{n \rightarrow \infty} \frac{bq^N-1}{q-1} = \frac{b}{1-q}

V druhé rovnosti jsme využili vztah

(1+q+q2+...+qN1)(q1)=qN1,(1 + q + q_2 + ... +q^{N−1})(q−1) = q^{N−1} ,

který se dá ověřit roznásobením levé strany.

Vlastnosti limity, přesná definice, její rozšíření na nevlastnípřípad („L=L=\infty“), sčítání řad a další aplikace a zobecnění limity tvoří klíčový obsah matematické analýzy v prvním ročníku.


Matematická indukce

Vyjádřit rekurentně zadanou posloupnost explicitně může být velmi náročná úloha. Snazší je dokázat, že explicitní vzorec nalezený heuristicky skutečně dané rekurentní posloupnosti odpovídá. Je to jedno z klasických použití matematické indukce.

Příklad:

Součet prvních nn přirozených čísel je popsán rekurencí an+1=an+(n+1)a_{n+1}=a_n + (n+1), a1=1a_1= 1. Z prvních pár součtů odhadneme, že an=(n+12)a_n={n+1 \choose 2}. Pro n=1n=1 vzorec s rekurencí souhlasí. Předpokládejme, že souhlasí pro nNn \in \N. Pak

an+1=(n+12)+(n+1)=(n+1)(n2+1)=(n+22)a_{n+1} = {n + 1 \choose 2} + (n + 1) = (n + 1)\left( \frac{n}{2} + 1 \right) = {n + 2 \choose 2}

Tedy vzorec je pravdivý i pro n+1n+1. Musí tudíž platit provšechna přirozená čísla.


Demonstrace

Hlavolam Hanoiské věže spočívá v přesunutí disků navlečenýchna jedné ze tří tyček na jinou tyčku. Jedním tahem je možnévzít jen jeden disk a přesunout jej buď na prázdnou tyčku, nebona věž z disků navlečenou na jiné tyčce, jejíž vrchní disk mávětší průměr než disk, který přesouváme.

Tower of Hanoi

Označme hnh_n nejmenší počet tahů, který je potřeba k vyřešení hlavolamu pro n disků (na obrázku je n=7n = 7). Jistě platí h1=1h_1 = 1.

Předpokládáme, že pro nějaké nNn \in \N známe hnh_n. Máme-li hlavolam s n+1n + 1 disky, určitě někdy přesouváme největší z nich ze startovní na cílovou tyčku a předtím musíme přesunout zbylých nn menších disků na tyčku „pomocnou“. Na to je potřeba optimálně hnh_n tahů, dalších hnh_n tahů je pak potřeba na přesunutí nn disků z pomocné na cílovou tyčku. Celkem tedy:

hn+1=hn+1+hn=2hn+1h_{n+1} = h_n + 1 + h_n = 2h_n + 1

Pro prvních pár nn dá rekurence hodnoty 1,3,7,15,31,...1,3,7,15,31,..., což vypadá jako hn=2n1h_n=2n−1. Dokážeme indukcí: h1=211=1h_1= 2^1−1 = 1 platí a pokud pro nNn \in \N předpokládáme hn=2n1h_n=2n−1, pak

hn+1=2hn+1=2(2n1)+1=2n+11h_{n+1} = 2h_n + 1 = 2(2^n - 1) + 1 = 2^{n+1} - 1

Vzorec tedy platí i pro n+1n+1 a tudíž musí platit pro všechna nNn \in \N. Vyřešili jsme tedy úlohu tak, že jsme nejprve sestavili rekurentní vztah, pak jsme odhadli explicitní vzorec, a následně použili matematickou indukci pro důkaz, že vzorec rekurenci vyhovuje.