Numerikus sorozatok/Rekurzív sorozatok

Rekurzív módon megadott sorozatok

Rekurzív módon adunk meg egy ($a_{n}$) sorozatot, ha az n-edik tagja az $a_{1}$,$a_{2}$, ..., $a_{n-1}$ elemek segítségével számítható ki. Ezzel szemben a sorozat explicit módon van megadva, ha ismert az a mód, ahogyan az n szám és más műveletek segítségével kiszámítható az $a_{n}$ általános tag.

Példák

1. Az $a_{n}=\left\{{\begin{matrix}1,&{\mbox{ha}}&n=1\\{\sqrt {3-a_{n-1}}},&{\mbox{ha}}&n>1\end{matrix}}\right.$

   hozzárendeléssel megadott sorozat rekurzív módon van adva, mert az n-edik tagot a közvetlenül megelőzőből kell kiszámítani, feltéve, hogy az a tag egyáltalán létezik (a definíció 1-et ad $a_{1}$-re)

2. $(b_{n})=\left({\sqrt {n+1}}\right)$

   az index függvényében, azaz explicit módon megadott sorozat

3. $(p_{n})=(2,3,5,7,11,...)\,$

   a prímszámok sorozata a prímszámok halmazának sorbarendezésével megadott sorozat, mely esetén a megadás módja nem jellemezhető egyértelműen

4. $c_{n}=\left\{{\begin{matrix}1,&{\mbox{ha}}&n=1\\n\cdot a_{n-1},&{\mbox{ha}}&n>1\end{matrix}}\right.$

   maga a faktoriális sorozat: (n!), mely általános tagja az előző tag és az index függvényében van megadva.

Megjegyzések

A matematikai analízisben egy sorozatot elegendő adottnak vennünk, egyáltalán nem kell mellékelnünk azt a módot ahogyan az elemeket kiszámíthatjuk. Ezzel szemben a rekurzív matematikában használatos sorozatokat nem tekinthetjük adottnak, amíg egy rekurzív eljárást nem mutatunk fel, mellyel kiszámíthatjuk a sorozat tetszőleges tagját.

A rekurzív definíció tétele

A rekurzív megadási módnál ellenőriznünk kell, hogy egyáltalán létezik-e az adott módon adott sorozat, sőt sok esetben (de nem mindig) azt is elvárjuk, hogy egyértelműen létezzen a kívánt rekurzív tulajdonságú sorozat. Ezt biztosítja a rekurziótétel.

Tétel – A rekurzív definíció tétele – Legyen S a következő függvényhalmaz:

$S=\{f\mid f:\{1,...,n-1\}\to \mathbf {R} ,\;n\in \mathbf {Z} ^{+}\}$

és legyen

$g:S\to \mathbf {R}$

függvény. Ekkor létezik egyetlen olyan ($a_{n}$):Z⁺ $\to$ R sorozat, mely rendelkezik a következő tulajdonsággal:

$a_{n}=g((a_{n})|_{\{1,...,n-1\}})\,$ minden n ∈ Z⁺-re.

Magyarázat. A g függvény szerepe az, hogy a sorozat előző tagjaiból, például az ($a_{1}$,$a_{2}$, ..., $a_{n-1}$) véges sorozatból, mely az (a_n) sorozat {1,...,n – 1} halmazra vett $\scriptstyle {(a_{n})|_{\{1,...,n-1\}}}$-vel jelölt leszűkítése, kiszámítsa az n-edik tag értékét. Speciálisan az n = 1 esetben az előbb említett sorozat az üres halmazra vett leszűkítés, azaz $\scriptstyle {a_{1}=g(\emptyset )}$, mely a kezdő elem értékét definiálja.

Világos, hogy a tételben az R halmaz szerepeltetésének nincs különleges indoka, állhat R helyett bármely halmaz.

Bizonyítás.

(1) egzisztencia

(a) Először belátjuk, hogy tetszőleges n ∈ Z⁺-re létezik egyetlen olyan s:{1,...,n – 1} $\to$ R véges sorozat, hogy minden 0 < k < n-ra

$s_{k}=g(s|_{\{1,...,k-1\}})\,$

n=1-re nyilvánvalóan létezik egyetlen ilyen sorozat, hiszen ekkor $\scriptstyle {s_{1}=g(\emptyset )}$.

n > 1 tetszőleges esetén tegyük fel, hogy az állítás az n-nél kisebb számokra már áll. Vegyük t:{1,...,n – 2} $\to$ R -t ilyen tulajdonsággal. Ekkor

s(m) = t(m) (m < n), s(n) = g(t)

alkalmasan definiált sorozat, mert t-re már igaz a szóban forgó tulajdonság, s-re pedig a definícióbójából adódik. Az egyértelműség az n-edik elem sorozattól független megadásából következik.

(b) Jól definiált tehát minden n-re az az (a_n) sorozat, melyet a következő definícióval kapunk:

a_n = s(n)

ahol s az előző pontban az n + 1 -hez egyértelműen megadható véges sorozat, s(n) pedig ennek n-edik eleme.

(2) unicitás

Teljes indukcióval igazolható, hogy ha lenne két ilyen tulajdonságú (a_n) sorozat, akkor ezek pontról pontra megegyeznek.

Példák

1. számtani sorozat, iterációk

Ha

$a_{1}=a\,$

$a_{n}=a_{n-1}+d\,$ minden n > 1

akkor

$g:\quad (s:\{1,...,n-1\}\to \mathbf {R} )\quad \mapsto \quad s_{n-1}+d\,$

és g($\scriptstyle {\emptyset }$) = a

Általában, ha a g függvény

$g:\quad (s:\{1,...,n-1\}\to \mathbf {R} )\quad \mapsto \quad f(s_{n-1})\,$

alakú, ahol f egyváltozós függvény, akkor iterációról beszélünk.

2. faktoriális sorozat, egyszerű rekurziók

Ha

$a_{1}=1\,$

$a_{n}=n\cdot a_{n-1}\,$ minden n > 1

akkor

$g:\quad (s:\{1,...,n-1\}\to \mathbf {R} )\quad \mapsto \quad n\cdot s_{n-1}\,$

Általában, ha a g függvény

$g:\quad (s:\{1,...,n-1\}\to \mathbf {R} )\quad \mapsto \quad f(n,s_{n-1})\,$

alakú, ahol f kétváltozós függvény, akkor egyszerű rekurzióról beszélünk (mely nem összetévesztendő a primitív rekurzióval).

3. Fibonacci-sorozat, általános rekurziók

Ha

$a_{1}=0\,$

$a_{2}=1\,$

$a_{n}=a_{n-2}+a_{n-1}\,$ minden n > 2

akkor

$g:\quad (s:\{1,...,n-1\}\to \mathbf {R} )\quad \mapsto \quad s_{n-2}+\cdot s_{n-1}\,$

mely egy teljesen általános rekurzióval megadott sorozat.

Ilyen általános rekurzióra még egy példa:

$a_{1}=a\,$

$a_{2}=b\,$

$a_{3}=c\,$

$a_{n}=n\cdot a_{n-3}+(n^{2}+1)a_{n-2}-(n^{3}-1)\cdot (a_{n-1})^{2008}\,$ minden n > 3

akkor

$g:\quad (s:\{1,...,n-1\}\to \mathbf {R} )\quad \mapsto \quad n\cdot s_{n-3}+(n^{2}+1)s_{n-2}-(n^{3}-1)\cdot (s_{n-1})^{2008}\,$

Kiválasztással kombinált rekurzió

Az analízis bizonyításai során számos esetben nem kell megadnunk rekurzív módon sorozatokat, elegendő valamely rekurzív tulajdonságnak eleget tévő sorozat létezését igazolni (például monoton növekvő, vagy egy ponttól egyenletesen távolodó, vagy ahhoz közeledő sorozat létezését igazolni).

Tétel – A kiválasztási axiómával segített rekurzió tétele – Legyen $\scriptstyle {(F_{n})_{n\in \mathbf {Z} ^{+}}}$ olyan függvényrendszer, hogy minden n természetes számra F_n elemei az {1,...,n-1}-en értelmezett, R-be képező függvények (R helyett tetszőleges halmazt is vehetünk). Legyen továbbá $\scriptstyle {e=(e_{i})_{i=1}^{M}\in F_{M}}$ „kezdő sorozat”. Ha

minden n természetes számra és minden f ∈ F_n-re létezik f* ∈ F_n+1, hogy f*|_{1,...,n-1} = f,

akkor létezik olyan a sorozat, hogy

$a|_{\{1,...,M\}}=e\,$ és minden n > M-re ($a_{1},...,a_{n-1})\in F_{n}\,$

Bizonyítás.

Először is a feltétel szerint minden n természetes számra a

$\prod \limits _{f\in F_{n}}\{f{\mbox{*}}\in F_{n+1}\mid f{\mbox{*}}|_{f}\}$

halmaz nem üres (ez tehát azon függvények halmaza, mely minden F_n -beli f-hez az f egy F_n+1-beli kiterjesztését rendeli). A kiválasztási axióma miatt ekkor nem üres az alábbi Descartes-szorzat:

$\prod \limits _{n\in \mathbf {Z} ^{+}}\prod \limits _{f\in F_{n}}\{f{\mbox{*}}\in F_{n+1}\mid f{\mbox{*}}|_{f}\}$

Ennek egy eleme olyan

$(g_{1},g_{2},...,g_{n},...)\,$

függvényrendszer, melynek n-edik eleme az összes F_n -beli f-hez az f egy F_n+1-beli kiterjesztését rendeli. Iterációval definiálunk ezek után egy sorozatot, mely rendelkezni fog a kívánt tulajdonsággal. Legyen ugyanis

$a_{1}=e\,$ és

$a_{n+1}=g_{n}(a_{n})\,$

Világos, hogy ez jól definiált függvény és teljes indukcióval az is belátható, hogy rendelkezik a fenti tulajdonsággal.

Példa. Ha (a_n) szigorúan monoton növekvő valós számsorozat, akkor van olyan csupa racionális számokból álló (b_n) sorozat, melyre a_n < b_n < a_n+1.

(1) Ilyen nyilvánvalóan létezik, hisz a_n és a_n+1 között mindig van racionális szám, ezeket kiválasztva nyerjük a sorozatot. Ez a megoldás lényeget érintően helyes, de formailag kifogásolható, hiszen a végtelen sok halmazból történő egyidejű kiválasztás esetén legalább azt igazolni kell, hogy ezen halmazok egyike sem üres.

(2) Igényesebb igazolása ennek a ténynek, a fenti tétel alkalmazása. a₁ és a₂ között választunk egy b₁ racionális számot. Ezután legyen F_n+1 az összes olyan {1,...,n}-halmazon értelmezett függvény (n tagú véges sorozat), melyekre teljesül, hogy az n-edik tagja a_n és a_n+1 közé eső racionális szám. Ha f egy F_n-beli, akkor világos, hogy hozzávéve n+1-edik tagként egy a_n+1 és a_n+2 közé eső racionális számot F_n+1-beli sorozatot kapunk. Ezen a ponton hivatkozunk a tételre: eszerint van a b₁ számmal induló, a fenti rekurzív tulajdonságnak eleget tévő sorozat.