Rekurzív sorozat

A matematikában a rekurzív sorozat egy olyan sorozat, ami definiálható egy rekurziós összefüggés segítségével. Utóbbi olyan képlet, összefüggés, ami a sorozat bármely elemét a megelőző néhány tag ismeretében adja meg (a pontos definíciót lásd lentebb).

Rekurzív vs. explicit képlet

Például az ${\displaystyle a_{n+1}=a_{n}+n;a_{1}=0}$ rekurzív képlettel definiált sorozat tagjai rendre: ${\displaystyle 0,1,3,6,10,15,...}$ (magyarul: bármely tagot úgy számolj ki, hogy az előző taghoz hozzáadod a sorszámát). Az ${\displaystyle a_{7}=a_{6}+6=21}$ tagot csak akkor tudjuk kiszámolni, ha előbb a hatodik tagot már kiszámoltuk. E sorozatra azonban explicit (a megelőző tagok ismeretét nem kívánó) képlet is adható: ${\displaystyle a_{n}=(n-1)*n/2}$. Sokszor épp az okoz gondot, hogy csak a megelőző tagok ismeretében tudunk számolni (ha az explicit képletet nehezebb megtalálni); ezért ha például egy számszerűen ismeretlen rekurzív sorozat ${\displaystyle 10000}$. tagját kívánjuk ismerni, akkor előtte mind a ${\displaystyle 9999}$ megelőző tagot végig kell számolni.

Tehát a fogalomnak bizonyos értelemben ellenpárja az általánosan, képlettel megadott sorozat fogalma, mely utóbbi azt jelenti, hogy ha kíváncsiak vagyunk a sorozat valamely tagjára/elemére, azt az előző tagok ismerete nélkül is, explicite ki tudjuk számolni. Azonban, mint a fenti példából látható, a félrevezető név ellenére egy sorozat rekurzivitása nem az egyes sorozatok egy immanens tulajdonsága, hanem pusztán egy megadási mód (egy lehetséges a sok közül).

A két fogalom (rekurzív-explicit) szembeállítása elmosódott és pragmatikus (azaz matematikailag nehezen lenne precízen értelmezhető, mivel gyakorlatilag minden függvény és sorozat, már a természetes számok ${\displaystyle 1,2,3,...}$ sorozata is tkp. rekurzív); de a gyakorlatban fontos ez a megkülönböztetés. Bizonyos esetekben a rekurzív sorozat elemei kiszámíthatók zárt alakos kifejezéssel is (az előző tagok ismerete nélkül), ilyenek például a lineáris rekurzióval definiált sorozatok, mint amilyen a Fibonacci-számok sorozata is.

Alkalmazások

Mind a rekurzív sorozat fogalma, mind a fenti probléma a matematika szinte minden ágában előfordul (de különösen a számítógéptudományban, a kombinatorikában, a numerikus analízisben és az elemi matematikában), de az informatika számára is nagyon fontos, mivel az általános tagot számítgató emberrel ellentétben a gépek viszont a rekurzív sorozatokkal boldogulnak jobban.

Jelölések és előzetes megállapodások: Adott ${\displaystyle S}$ halmazba képező, a természetes számok (esetleg a pozitív egész számok) halmazán értelmezett ${\displaystyle f:\mathbb {N} \to S}$ függvényt az ${\displaystyle S}$ feletti végtelen sorozatnak nevezünk; ${\displaystyle i\in \mathbb {N} }$ esetén pedig az ${\displaystyle f(i)\in S}$ elemet a sorozat ${\displaystyle i}$-edik tagjának nevezzük és ${\displaystyle s_{i}}$-vel jelöljük. Magát a sorozatot ${\displaystyle \left\{s_{i}\right\}}$-vel vagy ${\displaystyle \left(s_{i}\right)_{i\in \mathbb {N} }}$-nel vagy hasonló módon jelöljük.

Definíció

• Egy ${\displaystyle S}$ halmaz feletti ${\displaystyle (s_{i})_{i\in \mathbb {N} }=(s_{0},s_{1},s_{2},\ldots ,s_{i},\ldots )}$ végtelen sorozatot m-edrendben rekurzívnak nevezünk, ha létezik olyan m-változós

${\displaystyle \varphi \!:S^{m}\to S}$ függvény,

mellyel tetszőleges nemnegatív egész ${\displaystyle i}$ indexre

${\displaystyle s_{i+m}=\varphi \left(s_{i},s_{i+1},\ldots ,s_{i+m-1}\right)}$,

tehát ha a sorozat bármely tagja a megelőző m darab tagból a fenti m-változós függvény segítségével számolható ki. A ${\displaystyle \varphi }$ függvény a rekurziós szabály (-előírás, -összefüggés, -kapcsolat, egyenlet stb.). Arról van szó tehát, hogy a sorozat bármely tagja az őt megelőző m darab tagból számítható ki valamilyen módon.

Rend

Egy sorozatot akkor nevezünk (minden további jelző nélkül) rekurzívnak, ha van olyan m pozitív természetes szám, amelyre nézve m-edrendben rekurzív. Ha van ilyen pozitív szám, akkor a (pozitív) természetes számok halmazának jólrendezettsége miatt – azaz amiatt, hogy a pozitív természetes számok nem üres halmazában van egy legkisebb elem – van legkisebb ilyen pozitív szám is, melyet a sorozat minimális rekurziós rendjének nevezünk, és ${\displaystyle o\left(f\right)}$-fel jelölünk (az o betű utalás a latin ordo = rend szóra). A minimális rekurziós rend egyértelmű, de ettől eltekintve egy sorozat ha m-rendben rekurzív, attól lehet más rendben is rekurzív: belátható, hogy ha a minimális rekurziós rend m, akkor minden ennél nagyobb n≥m számra is n-edrendben rekurzív a sorozat.

Példák

1. Legyen S = ℕ a természetes számok halmaza, ekkor az ${\displaystyle \phi _{1}:\mathbb {N} \to \mathbb {N} ;\phi _{1}(n):=n+1}$ függvényt véve, ${\displaystyle s_{1}:=0}$ esetén a következő elsőrendben rekurzív sorozatot kapjuk: 0, 1, 2, 3, 4, … ; ennek értékkészlete a természetes számok halmaza.
2. Legyen S = ℕ, és j∈ℕ rögzített természetes szám; a ${\displaystyle \phi _{j}(n):\mathbb {N} \to \mathbb {N} ;\phi _{j}(n):=n+j}$ függvényt véve, a ${\displaystyle s_{1}:=0}$ megállapodással a 0, 0+j = j, j+j = 2j, 2j+j = 3j , … egyszóval a 0, j, 2j, 3j , … sorozatot kapjuk, vagyis a j-vel osztható számok sorozatát.
3. Legyen S = ℕ, és ${\displaystyle \Phi (n,m):\mathbb {N} ^{2}\to \mathbb {N} ;\Phi (n,m):=n+m}$ . Ekkor a ${\displaystyle s_{1}:=1,s_{2}:=1}$ megállapodással a következő másodrendben rekurzív sorozatot kapjuk: 1, 1, 1+1 = 2 , 1+2 = 3 , 2+3 = 5, 3+5 = 8 , … s_n, s_n+1 , s_n+s_n+1 , … sorozatot kapjuk; minden elem a két megelőző elem összege. ez a híres Fibonacci-sorozat (1, 1, 2, 3, 5, 8, 13, 21, 34 , …), amely másodrendben rekurzív. Minimális rekurziós rendje is 2, ugyanis nem állítható elő egyváltozós f(n) függvény segítségével rekurzív módon; mivel s₂ = f(1) = 1 és 2 = s₃ = f(s₂) = f(1) miatt f(n) az n = 1 helyen az 1 és 2 értéket is fel kellene hogy vegye, így nem (lenne) függvény.
4. Adott rekurzióval számított sorozatok esetén a kezdőelemek (a kezdőállapot) megválasztása hatással lehet a minimális rekurziós rendre. Legyen most S = ℤ, és tekintsük a ${\displaystyle \psi (a,b,c):\mathbb {N} ^{3}\to \mathbb {N} ;\psi (a,b,c):=a-b+c}$ rekurziót.
   1. Ha például a ${\displaystyle s_{1}:=0,s_{2}:=0,s_{3}:=0}$ megállapodással indítunk, akkor a sorozat összes értéke 0 lesz: 0,0,0, 0-0+0 = 0, 0-0+0 = 0, … , tehát a csupa 0-ból álló sorozatot kapjuk. Ez viszont már elsőrendben is rekurzív.
   2. Ha meg például az ${\displaystyle s_{1}:=0,s_{2}:=0,s_{3}:=1}$ megállapodással indítunk, akkor a sorozat periodikus lesz : 0,0,1, 0-0+1 = 1, 0-1+1 = 0, 1-1+0 = 0, 1-0+0 = 1, 0-0+1 = 1 , …; tehát a 0,0,1,1,0,0,1,1, … sorozatot kapjuk. Ez nem meglepő, hisz a sorozat első három a,b,c tagját bárhogy is megválasztva a negyedik tag s₄ = a-b+c, az ötödik pedig s₅ = b-c+(a-b+c) = a , a hatodik s₆ = c-(a-b+c)+(a) = c-a+b-c+a = b , a hetedik s₇ = (a-b+c)-(a)+b = c, tehát a sorozat így néz ki: a,b,c,a-b+c, a,b,c,a-b+c … Másrészt ez a sorozat már 2-rendben is rekurzív, ugyanis a kétváltozós f(x,y)=1-x függvény is generálja (ez csak egy változótól függ igazán, de két változós). A sorozat minimális rekurziós rendje pedig 2, mert egyváltozós g(x) függvény nem generálja: ugyanis s₂ = g(s₁) = g(0) = 0 és s₃ = g(s₂) = g(0) = 1 is teljesülne, azaz g(0) = 0 = 1, márpedig nem igaz, hogy 0 = 1.
   3. Belátható azonban, hogy bármilyen kezdőelemekből is induljunk ki, a fenti rekurzióval adott sorozatok mindig már másodrendben is rekurzívak lesznek, bármilyen, az f(a,b) = c; f(b,c) = a-b+c; f(c, a-b+c) = a , f(a-b+c,a) = b előírással értelmezett függvénnyel. Némi számolással ellenőrizhető, hogy ilyen függvény létezik (ha (x,y)=(x',y'), akkor f(x,y)=f(x',y') teljesül, amennyiben (x,y) a fent megnevezett rendezett párok közül kerülnek ki), egy konkrét példánya pedig valamilyen interpolációs eljárással kereshető (utóbbi esetben a függvény egy polinom lesz); vagy akár a megnevezett rendezett párok kivételével akár mindenütt máshol 1-nek is definiálható.

A rekurzív sorozat állapotai

E szakasz szerint egy m-edrendű rekurzív sorozatot (ahogy az sejthető) az első m eleme tökéletesen meghatározza.

Az ${\displaystyle s^{i}:=\left(s_{i},s_{i+1},...,s_{i+m-1}\right)}$ elem-m-est a sorozat i-edik állapotának nevezzük, ${\displaystyle s^{0}:=\left(s_{0},s_{1},...,s_{m-1}\right)}$ -et, tehát az első m db. elemét (az első állapotot) kezdőállapotnak. Belátható, hogy a kezdőállapot egyértelműen meghatározza a rekurzív sorozat bármelyik elemét, tehát az egész sorozatot; a k-adik állapot pedig a sorozat bármely, k-nál nagyobb (ti. nem kisebb) indexű elemét.

Előbbi, kezdőállapotra vonatkozó tétel teljes indukcióval látható be (az azt követő állítás is, hasonlóan): adottak az ${\displaystyle s^{1}:=\left(s_{1},s_{2}...,s_{m-1},s_{m}\right)}$ elemek, ezek tehát meghatározottak, továbbá ekkor ${\displaystyle s_{m+1}=\varphi \left(s_{1},s_{2},...,s_{m}\right)}$ is egyértelműen kiszámolható a ${\displaystyle \varphi }$ függvény segítségével, ugyanígy az ${\displaystyle s^{2}:=\left(s_{2},s_{3},...,s_{m+1}\right)}$ elemekből ${\displaystyle s_{m+2}=\varphi \left(s_{2},s_{3},...,s_{m+1}\right)}$, … és ha már valamilyen k-ra (k ≥ m) ismerjük a sorozat összes elemét, akkor az utolsó, k-adik elemtől visszafelé számolva, az utolsó m db. elemből: ${\displaystyle s^{k-m+1}:=\left(s_{k-(m-1)},...,s_{k-1},s_{k}\right)=\left(s_{k-m+1},s_{k-m+2},...,s_{k-m+m}\right)}$ állapotból a következő, k+1-edik elem is kiszámolható: ${\displaystyle s_{k+1}:=\varphi \left(s_{k-m+1},s_{k-m+2},...,s_{k}\right)}$.

Periodikus és rekurzív sorozatok

Belátható, hogy ha egy S-sorozat a k küszöbindextől kezdve periodikus a p (minimális) periódussal, akkor rekurzív, és rendje legfeljebb a küszöbindex és a periódus összege:

${\displaystyle o(f)\leq p+k}$

Érdekes, hogy ha S véges halmaz (elemeinek száma N), akkor tkp. fordítva is igaz: ha ${\displaystyle f}$ rekurzív, akkor periodikus is, és minimális p periódusára érvényes

${\displaystyle p\leq p+k\leq \left|S\right|^{o(f)}=N^{o(f)}}$

Külső hivatkozások

• Sulinet-oldal a rekurzív sorozatokról
• PDF jegyzet (Gonda János)