Visszatérő kapcsolatok. Ismétlődési összefüggések általános és sajátos megoldásai Ismétlődési relációs példák

Ez a módszer abból áll, hogy egy n objektumú kombinatorikus probléma megoldását egy hasonló probléma megoldásán keresztül fejezzük ki kisebb számú objektummal valamilyen relációval, amelyet rekurzívnak nevezünk. Azt mondjuk, hogy az u0 , u1 , … un , … elemek sorozata a C komplex számok mezője felett kielégít egy k rendű rekurzív relációt, ha

ahol a1 , … , ak a C-ből származó együtthatók. Az ilyen típusú relációk természetesen kombinatorikai feladatok megoldása során jönnek létre.

Példa. Legyen 1, 2, ... , n, ... számozott pozíciósorozat, és a kezdeti pillanatban az objektum az 1. pozícióban van. Egy mozdulattal az elem 1 és 2 pozíciót lép előre. Keresse meg, hány módon juthat el az n-edik pozícióba.

♦ Legyen un az a szám, amelyik érdekel. Nyilvánvaló, hogy u2 = 1, u3 = 2. Ezután osszuk két osztályra az n számú pozícióba jutás összes módját: azokra, amelyekben az objektum az utolsó lépésnél 1 lépést, és azokra, amelyekben 2 lépést mozog. Nyilvánvaló, hogy az első esetben un-1 opcióink vannak, a másodikban - un-2 opcióink. Ezért van

A P(x) polinomot nevezzük jellegzetes a lineáris ismétlődési relációhoz (2). Ne feledje, hogy a k-edik sorrend minden ismétlődő sorozata egyedileg meghatározható az első tagok k megadásával.

Legyen λ a P(x) karakterisztikus polinom gyöke.

1. Tétel. Az u0 , u1 , … un , … sorozat, ahol un = cλ n , c egy tetszőleges konstans C-ből, kielégíti a (2) lineáris ismétlődési összefüggést.

♦ A megadott un , n = 0, 1, … értékeket (2-be) behelyettesítve megkapjuk

cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak cλ n-k = cλ n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦

2. Tétel. Az un , vn , n = 0, 1, … sorozatok teljesítsék a (2) lineáris ismétlődési összefüggést. Aztán a sorrend

rn , n = 0, 1, … , ahol rn = α un + β vn , n , α, β tetszőleges állandók C-ből.

♦ A bizonyíték nyilvánvaló. ♦

3. Tétel. Legyen λ 1 , … , λ k a P(x) karakterisztikus polinom egyszerű (vagyis nem többszörös) gyöke a (2) sorozatra.

Ekkor ennek az ismétlődési relációnak az általános megoldása megvan a formája

ahol c1 , … , ck megfelelő konstansok C-ből.

♦ Az előző megjegyzés szerint az un , n = 0, 1, … sorozat a (2) összefüggés megoldása. Annak bizonyításához, hogy bármely megoldás (5) alakú, elegendő megmutatni, hogy egy tetszőleges vn sorozatra n = 0, 1, … , kielégítő

(2), vannak olyan c1 , … , ck konstansok, amelyekre un = vn , n . Ehhez elegendő, ha v0 = u0 , v1 = u1 , … , vk-1 = uk-1 . Vegye figyelembe ezeket a feltételeket

c1 , c2 , … , ck vonatkozásában. Ennek a rendszernek a meghatározója a Vandermonde-determináns és a (7, 118. o.) szerint.

a λ 1 , … , λ k gyökökre vonatkozó feltételezés szerint. Ezért az állítás következik. ♦ Példaként tekintsük az ismétlődési relációt (3). Megvan a karakterisztikus polinom

P(x) = x2 - x -1

Gyökei λ 1 = 1 + 2 5, λ 2 = 1 − 2 5. Az általános megoldás:

u n = c 1 1+ 2 5 n + c 2 1- 2 5 n

Egyenletrendszer c1 , c2 állandókhoz: c1 1 + 2 5 + c2 1 - 2 5 = 1

Most legyen λ a P(x) karakterisztikus polinom r multiplicitásának gyöke. Az előzőhöz hasonló módon bizonyítjuk

4. Tétel. Sorozatok c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, …

A C-ből származó tetszőleges c1 , … , cr állandók kielégítik a (2) összefüggést.

5. Tétel. Legyen a P(x) karakterisztikus polinomnak λ 1 , … , λ s gyöke az r1 , … , rs (r1 + … + rs = k) multiplicitásokból. Ezután az ismétlődési reláció általános megoldása

Jelöljük meg a lineáris rekurrens relációk még egy hasznos tulajdonságát. 6. Tétel. Legyen az összefüggés

un = a1 un-1 + … + ak un-k

kezdeti feltételekkel u1 , … , uk . Ekkor az összefüggés minden n ≥ k-re érvényes

♦ Bizonyítás indukcióval n-en. n = k esetén a (8) egyenlőség érvényes. Legyen igaz n. N + 1-re megvan

A legtöbb esetben azonban a numerációs problémák tanulmányozása során nemlineáris ismétlődési összefüggések merülnek fel, amelyek megoldására speciális technikákat alkalmaznak. Némelyiket a továbbiakban megvizsgáljuk. Adjunk egy fontos példát egy nemlineáris ismétlődési relációra.

7. Tétel. Legyen C(n, k) egy n elemű halmaz pontosan k ciklusú permutációinak száma. Akkor igazságos

♦ Oszd fel a pontosan k ciklusú X = (1, 2, … n,) halmaz permutációinak halmazát két osztályra - olyan permutációkra, amelyekben az n elem benne van az egységciklusban, és olyan permutációkra, amelyekben az n elem benne van. az l, l > 1 hosszúságú ciklus. Az első esetben a permutációk száma egybeesik a k - 1 ciklusú X′ = (1, 2, …, n - 1) halmaz permutációinak számával, azaz. C(n-1, k-1). A második esetben az n elem eltávolításával félig

az X′ = (1, 2, …, n - 1) halmazt k ciklussal helyettesítjük, amelyek száma egyenlő C(n - 1, k). Most nézzük meg, hogy egy n elem hányféleképpen adható hozzá egy n - 1 fokú permutációhoz k ciklussal. Ha van egy i hosszúságú ciklus, akkor ezt i módokon lehet megtenni. Az összes utak száma egyenlő i1 + … + ik , ahol i1 , … , ik a helyettesítési ciklusok hossza. Azonban i1 + … + ik = n - 1. Ezért a második osztály permutációinak száma egyenlő

(n-1)C(n-1, k). Így megkapjuk (9). ♦

A kapott C(n, k) számok az sn,k első típusú ismert Stirling-számokhoz kapcsolódnak, amelyeket a következőképpen határozunk meg:

sn,k = (-1)n+k C(n,k)

Adjunk táblázatot az sn,k számok első néhány értékéről.

Tab. Stirling-számok az első fajtából

Kombinatorikus számítások véges halmazokon

Bevezetés a kombinatorikába

A gyakran kombinatorikus számításoknak nevezett kombinatorikus algoritmusok elméletének tárgya a diszkrét matematikai struktúrákon végzett számítások. Ebben az elméletben nagy figyelmet fordítanak a diszkrét matematikai problémák megoldásának algoritmikus megközelítésére, az opciók felsorolásának optimalizálására és a figyelembe vett megoldások számának csökkentésére.

A kombinatorikus algoritmusok területe olyan feladatokat foglal magában, amelyek egy véges halmaz elemeinek számának megszámlálását (becslését), vagy ezen elemek speciális sorrendben történő felsorolását igénylik (B melléklet). Ebben az esetben széles körben alkalmazzák a visszatérő elemek kiválasztásának eljárását és annak változatait.

Kétféle számolási probléma létezik. Egyszerű esetben egy adott készlet adott, és ez kötelező határozza meg az elemek pontos számát benne. Általános esetben létezik valamilyen paraméter által meghatározott halmazcsalád, és a halmaz számosságát a paraméter függvényében definiáljuk. Ugyanakkor gyakran a függvény sorrendjének megfelelő becsléseés néha csak arra van szüksége növekedési ütemének értékelése. Például, ha a vizsgált halmaz ereje exponenciálisan növekszik valamilyen paraméterben, akkor ez elegendő lehet ahhoz, hogy a probléma tanulmányozásának javasolt megközelítését elhagyjuk anélkül, hogy különféle részletekbe mennénk. Ennél az általánosabb problématípusnál az aszimptotikus kiterjesztések, az ismétlődési relációk és a generáló függvények eljárásait alkalmazzuk.

Aszimptotikumok

Az aszimptota egy speciális vonal (leggyakrabban egyenes), amely a vizsgált görbe határa.

Az aszimptotika a függvények növekedési ütemének becslésének és összehasonlításának művészete. Azt mondják, hogy at x®¥ függvény "úgy viselkedik x", vagy "ugyanolyan mértékben növekszik, mint x", és at x®0 "úgy viselkedik, mint 1/ x". Azt mondják, hogy "napló x nál nél x®0 és bármely e>0 úgy viselkedik x e , és mi n®¥ nem nő gyorsabban, mint n log n Az ilyen pontatlan, de intuitív módon világos kijelentések a relációkhoz hasonlóan hasznosak a függvények összehasonlításában<, £ и = при сравнивании чисел.

Határozzuk meg három fő aszimptotikus relációt.

1. definíció. Funkció f(x) egyenértékű g(x) nál nél x® x0, akkor és csak akkor, ha =1.

Ebben az esetben a függvényt a következőnek mondjuk f(x) aszimptotikusan egyenlő a függvénnyel g(x) vagy mi f(x) ugyanolyan ütemben nő, mint g(x).

2. definíció. f(x)=o( g(x)) nál nél x® x0, akkor és csak akkor, ha =0.

Azt mondják, hogy at x® x 0 f(x) lassabban nő, mint g(x), vagy mi f(x) "van o-small" -ból g(x).

3. definíció . f(x)=O( g(x)) nál nél x® x0, akkor és csak akkor, ha létezik olyan C állandó, amelyre sup =C.

Ebben az esetben azt mondják f(x) nem nő gyorsabban mint g(x), vagy mindegy x® x 0 f(x) "van egy nagy O" innen g(x).

Hányados f(x)=g(x)+o(h(x)) nál nél x®¥ azt jelenti f(x)-g(x)=o(h(x)). Hasonlóképpen f(x)=g(x)+O(h(x)) azt jelenti, hogy f(x)-g(x)=O(h(x)).

Az O( ) és o( ) kifejezések is használhatók az egyenlőtlenségekben. Például az egyenlőtlenség x+o(x)2 GBP x nál nél x A ®0 azt jelenti, hogy bármely funkciónál f(x) oly módon, hogy f(x)=o(x), nál nél x®¥ x+f(x)2 GBP x minden kellően nagy értékre x.

Mutassunk be néhány hasznos aszimptotikus egyenlőséget.

A polinom aszimptotikusan egyenlő a legmagasabb tagjával:

nál nél x®¥; (4.1)

nál nél x®¥; (4.2)

nál nél x®¥ és a k¹0. (4.3)

Az egész számok hatványösszegei kielégítik a következő összefüggést:

nál nél n®¥. (4.4)

Ezért különösen van n®¥

Általánosabb esetben mikor n®¥ és bármely egész számra k³0

; (4.6)

. (4.7)

Visszatérő kapcsolatok

Illusztráljuk az ismétlődési viszonyok fogalmát a Fibonacci által 1200 körül felvetett és tanulmányozott klasszikus problémával.

Fibonacci a problémáját a nyúlpopuláció növekedési üteméről szóló történet formájában fogalmazta meg a következő feltételezések alapján. Minden egy pár nyúllal kezdődik. Minden nyúlpár egy hónap után lesz termékeny (termékeny), ezután minden pár minden hónapban új nyúlpárt hoz világra. A nyulak soha nem halnak meg, és szaporodásuk soha nem áll le. Hadd F n- utáni populációban lévő nyúlpárok száma n hónap, és álljon ez a populáció N n alompárok és Tovább„régi” párok, pl. F n = N n + Tovább. Így a következő hónapban a következő események történnek:

Régi lakosság ( n+1)-edik pillanat az akkori születések számával nő n, azaz O n+1 = Tovább + N n= F n;

Minden öreg egy adott időpontban n a pár időben produkál ( n+1) pár utód, i.e. Nn+1= C n.

A következő hónapban ez a minta megismétlődik:

O n+2 = O n+1+ Nn+1= Fn+1,

Nn+2=O n+1;

ezeket az egyenlőségeket kombinálva megkapjuk a Fibonacci ismétlődési relációt:

O n+2 + Nn+2=Fn+1 + O n+1,

Fn+2 = Fn+1 + F n. (4.8)

A Fibonacci-szekvencia kezdeti feltételeinek megválasztása nem fontos; ennek a sorozatnak a lényeges tulajdonságait a (4.8) ismétlődő összefüggés határozza meg. Általában azt hitték F0=0, F1=1 (néha F0=F1=1).

Az ismétlődési reláció (4.8) egy speciális esete a homogén lineáris ismétlődési relációknak, állandó együtthatókkal:

x n = a 1 x n-1 + a 2 x n-2 +…a k x n-k, (4.9)

ahol együtthatók a i ne függj attól nés x 1, x2, …, x k adottnak tekintendők.

Van egy általános módszer a megoldásra (azaz megtalálásra x n függvényként n) lineáris ismétlődő összefüggések állandó együtthatókkal. Tekintsük ezt a módszert a (4.8) reláció segítségével. A formában találunk megoldást

F n=crn (4.10)

állandóval Val velés r. Ezt a kifejezést (4.8) behelyettesítve azt kapjuk, hogy

cr + 2 = crn+ 1 + crn,

crn(rn-r-1)=0. (4.11)

Ez azt jelenti F n=crn megoldás, ha bármelyik Val vel=0, vagy r= 0 (és ebből fakadóan F n =0 mindenre n), valamint (és ez egy érdekesebb eset), ha r 2 - r -1=0, és az állandó Val vel tetszőleges. Ekkor a (4.11)-ből az következik

r= vagy r = . (4.12)

Az "1,618" számot "arany" aránynak nevezik, mivel ősidők óta úgy gondolják, hogy az 1-es oldalakkal rendelkező háromszög (téglalap) a legszembetűnőbb arányokkal rendelkezik.

Egy homogén lineáris ismétlődés két megoldásának összege nyilvánvalóan szintén megoldás, és valójában megmutathatjuk, hogy a Fibonacci sorozat általános megoldása

F n= , (4.13)

hol vannak az állandók Val velés Val vel' a kezdeti feltételek határozzák meg. Ha F 0 =0 és F 1 =1 értékeket teszünk, a következő lineáris egyenletrendszert kapjuk:

, (4.14)

amelynek megoldása megadja

c = -c" = . (4.15)

A matematikában nagyon gyakran használják az olyan kifejezéseket, mint a „rekurzív függvények”, „ismétlődő sorozatok”, „rekurzív relációk”, „rekurzív algoritmusok”. Ezeknek a kifejezéseknek ugyanaz a gyöke, amely a latin gesiggege - visszatérni szóból származik. A rekurzív függvényekre, rekurzív algoritmusokra és ismétlődő sorozatokra jellemző, hogy a függvény következő értékének kiszámításához, az algoritmus következő implementációjának megszerzéséhez, a sorozat következő tagjának meghatározásához az előző értékükre kell hivatkozni. korábban számított. A korábbi értékek kiszámításához viszont hozzá kell férni a korábban kiszámított szükséges értékekhez, és így tovább. Így egy függvény értékének megszerzéséhez egy algoritmus megvalósítása, vagy egy sorozat tagjának értéke délután lépésben ismernie kell az értékeiket (P- 1)-edik lépés, tehát az első lépésben. Az a szabály, amely meghatározza, hogyan számítsuk ki egy függvény következő értékét vagy egy sorozat következő tagját, feltéve, hogy ezek az értékek az első lépéshez ismertek, az ún. rekurzív reláció. Az ismétlődő kapcsolatok fejlesztése a különféle problémák megoldásának egyik módja. Ezt a módszert széles körben alkalmazzák a kombinatorikában.

Az ismétlődési reláció legegyszerűbb példája egy n elemű halmaz permutációinak számának kiszámítására szolgáló képlet. Ezek a képletek így néznek ki R x = 1, R p = R p _ x pés a következő módon szerezhető be.

Legyen P elemek /, / 2 , ..., /„, halmazok ÉN. Liu

Ezeknek az elemeknek az új permutációja a következőképpen érhető el: vegyük át a /, / 2 , ... elemeket, és minden lehetséges módon a jelzett elemek közé, beleértve az elejét és a végét is, tegyük a / és elemet. Nyilvánvaló, hogy az ilyen módszerek igen P. Ennek eredményeként a /, / 2 , ..., / d _ permutációból kapjuk P permutációk. Ez azt jelenti, hogy a permutációk a P elemek benne P-szer több, mint a permutációk P-1 elem a készletből ÉN. Ez létrehozza az ismétlődési kapcsolatot R p = R p _ x p. Ezt az összefüggést felhasználva egymás után megkapjuk R p -pR p _ x \u003d p (p-) R p _ 2 - p (p - )(n -2)...2Р H. De R x - 1, mivel egy elemből csak egy permutáció készíthető. Ezért P n \u003d n (n-1)(" - 2)___2-1 = P. A fentiek alapján

a következő is igaz: R p = (P-tizenegy! = 1.

Most példát adunk egy ismétlődő számsorozatra, amelyet gyakran hívnak Fibonacci számok, századi olasz matematikus után, aki a következő probléma megoldásának eredményeként állapította meg. Egy nyúlpár havonta egyszer két nyúl (nőstény és hím) utódját hozza. Az újszülött nyulak két hónappal a születés után is hoznak utódokat. Hány nyúl fog megjelenni egy évben, ha egy pár nyúl volt az elején?

A probléma feltételéből az következik, hogy egy hónap múlva két pár nyúl lesz (az első nyúl utódokat hoz). Két hónap alatt - három pár, három hónap alatt - öt pár, mivel az első hónap után megjelent pár utódokat ad.

Jelölje /„ az utána lévő nyúlpárok számát P hónapok az év elejétől. Majd év elején / 0 = 1, egy hónap múlva /, = 2, két hónap múlva / 2 = / 0 + /, = 3, három hónap múlva / 3 = = / 2 + /1 =5. Ezért általános esetben bármely hónap végén a nyulak számának kiszámításához a /„ = + / i _ 2 ismétlődő összefüggést kapjuk. Ez az arány lehetővé teszi

számítsa ki a nyúlpárok számát az év végén a / 12 \u003d / n + kifejezés szerint /Yu P R És feltéve, hogy / 0 = 1, /, = 2. Egyenlő: 377. Azok a számok, amelyeket a fenti ismétlődési összefüggés alkalmazása eredményeként kapunk, azaz. az 1, 2, 3, 5, 8, 13, ... sorozatot Fibonacci-számoknak nevezzük. Figyelemre méltó, hogy a numerikus sorozatot leíró ismétlődési reláció segítségével a kombinatorika számos problémája megoldódik. Íme az egyik közülük.

Határozza meg a nullák és egyesek hosszúságú sorozatainak számát! P amelyekben két egység nincs egymás mellett. Győződjön meg arról, hogy ez a probléma az ismétlődési reláció segítségével megoldható

/ i \u003d / "-1 + / i- 2-

Vegyél tetszőleges sorozatot innen P+1 nullákat és egyeseket úgy, hogy ne legyen benne két egymást követő egy. A vége lehet nulla vagy egy. Ha a sorozat nullára végződik, akkor el lehet vetni, és egy hosszúságú sorozat P, amelyben két egység nem szomszédos. Fordítva, ha ezt a sorozatot vesszük, és a végén nullát rendelünk hozzá, akkor ilyen hosszúságú sorozatot kapunk n+ 1, amelyben két egység nincs egymás mellett.

Legyen a hosszúságú sorozatok száma P+1, amelyben két egyes nincs szomszédos, és amelyek nullára végződnek, egyenlő g n . Vegyünk most egy HOSSZÚ /7 + 1 sorozatot, amelyben két 1 nem szomszédos, és amely 1-re végződik. Mivel két 1-es nem szomszédos, a sorozat utolsó 1-je előtt egy nulla áll, azaz. a sorozat 01-re végződik. Ezeket a számokat elvetve egy hosszúságú sorozatot kapunk P - 1, amelyben két egység nincs egy sorban. Az ilyen sorozatok száma gn_^. Mivel minden sorozat hosszú n+ 1, amelyben két egység nem áll egy sorban, egyben vagy nullában végződik, az ilyen sorozatok teljes számára az összegzési szabály szerint kapjuk g n+ ^ - g n + g n_x. Sőt, hosszúságú sorozatokhoz P= 1, két sorozat van: 0 és 1, amelyekben két 1 nem szomszédos, mivel

miért gl- 2. Hosszúságú sorozatokhoz P - 2, három sorozat van, amelyben két 1 nem szomszédos: 00, 01 és 10. Ezért = 3. Így az ismétlődési reláció gn+l = gn + gn_( , g^ = 2, g 2=3 ekvivalens a sorozatot leíró /i+1 = /„ + /, =2, /2 = 3 rekurzív relációval

Fibonacci. Ezért bármely /7 = 1,2, ... esetén ezt az összefüggést felhasználva megoldható a fent megfogalmazott probléma.

Megjegyzendő, hogy az ismétlődő összefüggések levezetése néha egyszerű, néha komoly erőfeszítést igényel. Egyes problémák esetében az ismétlődési viszonyok egyszerűek, mások esetében összetettek. Az ismétlődési relációk általános kellemetlensége, hogy a sorozat egy tagjának kiszámításához ki kell számítani az összes korábbi tagját.

Általános megoldás Az ismétlődő reláció (1) az összes olyan sorozat halmaza, amely kielégíti ezt az összefüggést.

Magán döntés reláció (1) az ezt a relációt kielégítő sorozatok egyikét nevezzük.

1¢ példa. Utóbbi a n=a 0 +nd a n=a n - 1 +d. Ez a képlet a különbséggel rendelkező aritmetikai sorozat közös tagjára dés a progresszió kezdő tagjával a 0 .

2¢ példa. Utóbbi b n=b 0 × q n az összefüggés általános megoldása b n=b n - 1 ×q. Ez a képlet egy nevezővel rendelkező geometriai sorozat közös tagjára q¹0 és a progresszió kezdő tagjával b 0 .

Példa 3¢.Úgynevezett Binet képlete j n= a j reláció sajátos megoldása n=j n-2+j n- 1, ha j 0 =j 1 =1.

Egyszerű gyökerek óta x 1 ,…,x k páronként eltérő, akkor D¹0. Ezért az (5) rendszernek (egyedi) megoldása van.

1. feladat. Keresse meg egy geometriai folyamat általános tagját a (4) képlet segítségével!

Megoldás b n=qb n- 1 úgy néz ki. Ezért .

2. feladat. Keresse meg a Fibonacci-hányados általános megoldását! a n + 2 =a n+a n + 1 .

Megoldás. Az ismétlődési reláció karakterisztikus polinomja a n + 2 =a n+a n A + 1 alakja . Ezért .

Bizonyítás nélkül megadjuk az 1. Tétel alábbi általánosítását.

2. tétel. Legyen a (3) homogén lineáris ismétlődési reláció karakterisztikus polinomja k gyökök: a 1 szorzatok , …, a k multiplicitások , , . Ekkor a (3) ismétlődési reláció általános megoldása a következő alakú:

3. feladat. Keresse meg az összefüggés általános megoldását!

Megoldás. A karakterisztikus polinomnak 3-as multiplicitásának 2 gyöke van. Ezért .

Megjegyzés. Az inhomogén lineáris reláció (2) általános megoldása a homogén lineáris reláció általános megoldásának (3) és az inhomogén lineáris összefüggés (2) partikuláris megoldásának összegeként kereshető.

4. Függvények generálása. Formális sorozat a 0 +a 1 x+a 2 x 2 +…+a k x k+… hívott a sorozat generáló függvénye a 0 ,a 1 ,a 2 ,…,a k,…

A generáló függvény egy konvergens sorozat vagy egy divergens sorozat. Két divergens sorozat lehet függvényként egyenlő, de különböző sorozatokból generált függvények. Például az 1+2 x+2 2 x 2 +…+2k x k+… és 1+3 x+3 2 x 2 +…+3k x k+… definiálja ugyanazt a függvényt (egyenlő 1-gyel a pontban x=1, pontokban határozatlan x>1), hanem különböző sorozatokból álló függvényeket generálnak.

Sorozatok függvénygeneráló tulajdonságai:

sorozatok generáló függvényeinek összege (különbsége). a nés b n egyenlő a sorozatok összegének (különbségének) generáló függvényével a n+b n;

sorozatok függvényeinek generálásának szorzata a nés b n a sorozatkonvolúció generáló függvénye a nés b n:

c n=a 0 b n+a 1 b n - 1 +…+a n - 1 b 1 +a n b 0 .

1. példa A függvény a sorozathoz generál

2. példa A függvény az 1, 1, 1, ... sorozathoz generál

Az ismétlődési relációnak van rend k , ha lehetővé teszi az f(n+k) kifejezését f(n), f(n+1), …, f(n+k-1) értékekkel.

Példa.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 a másodrendű ismétlődési reláció.

f(n+3)=6f(n)f(n+2)+f(n+1) egy harmadrendű visszatérő reláció.

Ha adott egy k-edik rendű ismétlődési reláció, akkor azt végtelenül sok sorozat kielégítheti, hiszen a sorozat első k eleme tetszőlegesen beállítható - nincs közöttük reláció. De ha az első k tag adott, akkor az összes többi elem egyedileg meghatározott.

Az ismétlődési reláció és a kezdeti tagok segítségével egyenként kiírhatjuk a sorozat tagjait, és előbb-utóbb megkapjuk bármelyik tagját. Ha azonban a sorozatnak csak egy adott tagját kell ismernie, akkor nem ésszerű az összes előzőt kiszámítani. Ebben az esetben kényelmesebb egy képlet az n-edik tag kiszámítására.

Az ismétlődési reláció megoldása minden olyan sorozatot meghívunk, amelyre az adott reláció azonosan érvényes.

Példa. A 2, 4, 8, …, 2 n sorozat az f(n+2)=3∙f(n+1) – 2∙f(n) összefüggés megoldása.

Bizonyíték. A sorozat közös tagja f(n)=2 n . Tehát f(n+2)=2n+2, f(n+1)=2n+1. Bármely n-re érvényes a 2 n+2 =3∙2 n+1 – 2∙2 n azonosság. Ezért ha a 2 n sorozatot behelyettesítjük az f(n+2)=3f(n+1) – 2f(n) képletbe, az összefüggés azonosan teljesül. Ezért 2 n a jelzett összefüggés megoldása.

A recidíva reláció megoldása k-edik rendet hívják Tábornok, ha k tetszőleges α 1 , α 2 , … α k állandótól függ, és ezen állandók kiválasztásával ennek az összefüggésnek tetszőleges megoldása kapható.

Példa. Az ismétlődési összefüggés adott: f(n+2)=5f(n+1)-6f(n). Bizonyítsuk be, hogy általános megoldásának alakja: f(n)= α 2 n + β3 n .

1. Először bizonyítjuk be, hogy az f(n)=α 2 n + β3 n sorozat megoldása az ismétlődési relációra. Helyettesítse ezt a sorozatot az ismétlődési relációba.

f(n)= α 2 n + β 3 n, tehát f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2, akkor

5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f( n+2).

Az ismétlődési összefüggés fennáll, ezért α 2 n + β 3 n ennek az ismétlődési relációnak a megoldása.

2. Bizonyítsuk be, hogy az f(n+2)=5f(n+1)–6f(n) összefüggés bármely megoldása felírható így: f(n)= α 2 n + β 3 n . De a másodrendű ismétlődési reláció bármely megoldását a sorozat első két tagjának értékei egyértelműen meghatározzák. Ezért elegendő megmutatni, hogy bármely a=f(1) és b=f(2) esetén létezik α és β úgy, hogy 2 α +3 β =a és 4 α +9 β =b. Könnyen belátható, hogy az egyenletrendszernek van megoldása a és b bármely értékére.

Így f(n)= α 2 n + β 3 n az f(n+2)=5f(n+1)–6f(n) ismétlődő összefüggés általános megoldása.

Lineáris ismétlődési viszonyok állandó együtthatókkal

Az ismétlődési viszonyok megoldására nincsenek általános szabályok, de van egy gyakran előforduló ismétlődő reláció osztály, amelyre ismert a megoldásukra szolgáló algoritmus. Ezek lineárisan visszatérő összefüggések állandó együtthatókkal, pl. típus arányok:

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

Keressük az általános lineáris ismétlődési összefüggés megoldását elsőrendű állandó együtthatókkal.

Egy lineáris ismétlődési összefüggés elsőrendű állandó együtthatókkal a következő formájú: f(n+1)=c f(n).

Legyen f(1)=a, majd f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, hasonlóan az f(4)=c-hez 3 ∙a és így tovább, vegye figyelembe, hogy f(n)=c n -1 ∙f(1).

Bizonyítsuk be, hogy a c n -1 ∙f(1) sorozat az elsőrendű ismétlődési reláció megoldása. f(n)=c n -1 ∙f(1), tehát f(n+1)=c n f(1). Ezt a kifejezést behelyettesítve a relációba, a c n f(1)=с∙ c n -1 ∙f(1) azonosságot kapjuk.

Most nézzük meg részletesebben lineáris ismétlődési relációk konstans másodrendű együtthatókkal , vagyis a forma relációi

f(n+2)=C1∙f(n+1)+C2∙f(n). (*).

Megjegyzendő, hogy minden megfontolás igaz a magasabb rendű kapcsolatokra is.

Megoldás tulajdonságai:

1) Ha az x n sorozat egy megoldás (*), akkor az a∙x n sorozat is megoldás.

Bizonyíték.

x n a (*) megoldása, ezért x n +2 =C 1 x n +1 +C 2 x n . Az egyenlőség mindkét oldalát megszorozzuk a-val. Azt kapjuk, hogy a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . Ez azt jelenti, hogy ax n a megoldás (*).

2) Ha az x n és y n sorozatok megoldások (*), akkor az x n +y n sorozat is megoldás.

Bizonyíték.

x n és y n megoldások, tehát a következő azonosságok teljesülnek:

x n +2 \u003d C 1 x n +1 + C 2 x n.

y n +2 =C 1 y n +1 +C 2 y n .

Adjuk hozzá a két egyenlőséget tagonként:

x n +2 + y n +2 \u003d C 1 ∙ x n +1 + C 2 ∙ x n + C 1 ∙ y n +1 + C 2 ∙ y n \u003d C 1 ∙ (x n +1 + y C n + 2 1) (x n +yn). Ez azt jelenti, hogy x n +y n a (*) megoldása.

3) Ha r 1 az r 2 =С 1 r+С 2 másodfokú egyenlet megoldása, akkor az (r 1) n sorozat a (*) összefüggés megoldása.

r 1 az r 2 =C 1 r+C 2 másodfokú egyenlet megoldása, tehát (r 1) 2 =C 1 r 1 +C 2 . Szorozzuk meg az egyenlőség mindkét oldalát (r 1) n -nel. Kap

r 1 2 r 1 n \u003d (C 1 r 1 + C 2) r n.

r 1 n +2 \u003d C 1 r 1 n +1 + C 2 r 1 n.

Ez azt jelenti, hogy az (r 1) n sorozat a (*) megoldása.

Ezekből a tulajdonságokból az következik megoldási mód lineáris ismétlődési viszonyok másodrendű állandó együtthatókkal:

1. Állítsa össze az r 2 =C 1 r+C 2 karakterisztikus (másodfokú) egyenletet! Határozzuk meg a gyökeit r 1, r 2. Ha a gyökök különböznek, akkor az általános megoldás f(n)= ar 1 n +βr 2 n .

2. Keresse meg az a és β együtthatókat! Legyen f(0)=a, f(1)=b. Egyenletrendszer

van megoldása bármely a-ra és b-re. Ezek a megoldások

Egy feladat . Keressünk egy képletet a Fibonacci sorozat közös tagjára.

Megoldás . A karakterisztikus egyenlet alakja x 2 \u003d x + 1 vagy x 2 -x-1 \u003d 0, gyökerei számok, ami azt jelenti, hogy az általános megoldás alakja f (n) \u003d . Amint jól látható, az f(0)=0, f(1)=1 kezdeti feltételekből az következik, hogy a=-b=1/Ö5, és ebből következően a Fibonacci sorozat általános megoldása a következő alakú. :

.

Meglepő módon ez a kifejezés egész számokat vesz fel n minden természetes értékéhez.