Opakujúce sa vzťahy. Všeobecné a partikulárne riešenia rekurentných vzťahov Príklady rekurentných vzťahov

Táto metóda spočíva v tom, že riešenie kombinatorickej úlohy s n objektmi je vyjadrené riešením podobnej úlohy s menším počtom objektov pomocou nejakého vzťahu, ktorý sa nazýva rekurzívny. Hovoríme, že postupnosť prvkov u0 , u1 , … un , … nad oborom komplexných čísel C spĺňa rekurzívny vzťah rádu k, ak

kde a1 , … , ak sú koeficienty z C. Vzťahy tohto typu prirodzene vznikajú pri riešení kombinatorických úloh.

Príklad. Nech existuje postupnosť pozícií očíslovaných 1, 2, ... , n, ... a v počiatočnom momente je objekt na 1. pozícii. Jedným ťahom sa položka posunie o 1 a 2 pozície dopredu. Nájdite počet spôsobov, ako sa dostať na n-tú pozíciu.

♦ Nech je un číslo, ktoré nás zaujíma. Je jasné, že u2 = 1, u3 = 2 . Ďalej rozdeľme všetky spôsoby, ako sa dostať na pozíciu číslo n, do dvoch tried: tie, v ktorých sa objekt pohne o 1 krok pri poslednom kroku a tie, v ktorých sa posunie o 2 kroky. Je jasné, že v prvom prípade máme možnosti un-1, v druhom - un-2 možnosti. Preto máme

Polynóm P(x) sa nazýva charakteristický pre lineárny rekurentný vzťah (2). Všimnite si, že každá opakujúca sa sekvencia k-tého rádu je jednoznačne určená špecifikovaním k jej prvých členov.

Nech λ je koreň charakteristického polynómu P(x).

Veta 1. Postupnosť u0 , u1 , … un , … , kde un = cλ n , c je ľubovoľná konštanta z C, spĺňa lineárny rekurentný vzťah (2).

♦ Dosadením daných hodnôt un , n = 0, 1, … do (2) máme

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

Veta 2. Nech postupnosti un , vn , n = 0, 1, … spĺňajú lineárny rekurentný vzťah (2). Potom postupnosť

rn , n = 0, 1, … , kde rn = α un + β vn , n , α, β sú ľubovoľné konštanty z C.

♦ Dôkaz je zrejmý. ♦

Veta 3. Nech λ 1 , … , λ k sú jednoduché (tj nie viacnásobné) korene charakteristického polynómu P(x) pre postupnosť (2).

Potom má všeobecné riešenie tohto rekurentného vzťahu tvar

kde c1, …, ck sú vhodné konštanty z C.

♦ Podľa predchádzajúcej poznámky postupnosť un , n = 0, 1, … je riešením vzťahu (2). Aby sme dokázali, že akékoľvek riešenie má tvar (5), stačí ukázať, že pre ľubovoľnú postupnosť vn , n = 0, 1, … , spĺňajúce

(2), existujú konštanty c1 , … , ck také, že un = vn , n . Na to stačí, že v0 = u0 , v1 = u1 , … , vk-1 = uk-1 . Zvážte tieto podmienky

vzhľadom na c1 , c2 , … , ck . Determinantom tohto systému je Vandermondov determinant a podľa (7, s. 118).

podľa predpokladu o koreňoch λ 1 , … , λ k . Z toho vyplýva tvrdenie. ♦ Ako príklad uvažujme vzťah opakovania (3). Máme charakteristický polynóm

P(x) = x2 - x -1

Jeho korene sú λ 1 = 1 + 2 5 , λ 2 = 1 − 2 5. Všeobecné riešenie je

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

Sústava rovníc pre konštanty c1 , c2 : c1 1 + 2 5 + c2 1 − 2 5 = 1

Teraz nech λ je koreň násobnosti r charakteristického polynómu P(x). Podobným spôsobom ako v predchádzajúcom dokazujeme

Veta 4. Postupnosti c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … pre

ľubovoľné konštanty c1 , … , cr z C spĺňajú vzťah (2).

Veta 5. Nech má charakteristický polynóm P(x) korene λ 1 , … , λ s násobností r1 , … , rs (r1 + … + rs = k) . Potom všeobecné riešenie rekurentného vzťahu

Naznačme ešte jednu užitočnú vlastnosť lineárnych rekurentných vzťahov. Veta 6. Nech máme vzťah

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

s počiatočnými podmienkami u1 , … , uk . Potom vzťah platí pre všetky n ≥ k

♦ Dôkaz indukciou na n. Pre n = k platí rovnosť (8). Nech platí pre n. Pre n + 1 máme

Vo väčšine prípadov však pri štúdiu enumeračných problémov vznikajú nelineárne rekurentné vzťahy, na riešenie ktorých sa využívajú špecifické techniky. Niektoré z nich sa budú ďalej posudzovať. Uveďme dôležitý príklad nelineárneho rekurentného vzťahu.

Veta 7. Nech C(n, k) je počet permutácií n-prvkovej množiny, ktoré majú presne k cyklov. Potom je to spravodlivé

♦ Rozdeľte množinu permutácií množiny X = (1, 2, … n,), ktorá má presne k cyklov, na dve triedy - permutácie, v ktorých je prvok n obsiahnutý v jednotkovom cykle, a permutácie, v ktorých je prvok n v cyklus dĺžky l, l > 1. V prvom prípade sa počet permutácií zhoduje s počtom permutácií množiny X′ = (1, 2, …, n - 1), ktorá má k - 1 cyklov, t.j. C(n-l, k-l). V druhom prípade odstránenie prvku n, semi-

máme substitúciu množiny X′ = (1, 2, …, n - 1) k cyklom, ktorých počet sa rovná C(n - 1, k). Poďme teraz zistiť, akým počtom spôsobov možno pridať prvok n k permutácii stupňa n - 1 s k cyklom. Ak existuje cyklus dĺžky i, potom to možno urobiť spôsobmi i. Celkový počet spôsobov sa rovná i1 + … + ik , kde i1 , … , ik sú dĺžky substitučných cyklov. Avšak i1 + … + ik = n - 1. Počet permutácií druhej triedy je teda rovný

(n-l)C(n-l, k). Tak dostaneme (9). ♦

Výsledné čísla C(n, k) súvisia so známymi Stirlingovými číslami prvého druhu sn,k, ktoré sú definované takto:

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

Uveďme tabuľku prvých niekoľkých hodnôt čísel sn,k .

Tab. Stirlingove čísla prvého druhu

Kombinatorické výpočty na konečných množinách

Úvod do kombinatoriky

Predmetom teórie kombinatorických algoritmov, často nazývaných kombinatorické výpočty, sú výpočty na diskrétnych matematických štruktúrach. V tejto teórii sa veľká pozornosť venuje algoritmickému prístupu k riešeniu problémov diskrétnej matematiky, optimalizácii enumerácie možností a redukcii počtu uvažovaných riešení.

Oblasť kombinatorických algoritmov zahŕňa úlohy, ktoré vyžadujú počítanie (odhad) počtu prvkov v konečnej množine alebo vypísanie týchto prvkov v špeciálnom poradí (príloha B). V tomto prípade je široko používaný postup výberu prvkov s návratom a jeho varianty.

Existujú dva typy problémov s počítaním. V jednoduchom prípade je daná konkrétna sada a tá je potrebná určiť presný počet prvkov v ňom. Vo všeobecnom prípade existuje rodina množín definovaná nejakým parametrom a mohutnosť množiny je definovaná ako funkcia parametra. Zároveň je to často dostatočný odhad poradia funkcie a niekedy len potrebujete hodnotenie jeho tempa rastu. Napríklad, ak sila uvažovanej množiny rastie exponenciálne v niektorom parametri, potom to môže stačiť na opustenie navrhovaného prístupu k štúdiu problému bez toho, aby sme zachádzali do rôznych detailov. Pre tento všeobecnejší typ problému sa aplikujú postupy asymptotických expanzií, rekurentných vzťahov a generujúcich funkcií.

Asymptotické

Asymptota je špeciálna čiara (najčastejšie priamka), ktorá je limitom pre uvažovanú krivku.

Asymptotika je umenie odhadovať a porovnávať rýchlosti rastu funkcií. Hovoria, že o X®¥ funkcia „správa ako X“, alebo „zvyšuje rovnakým tempom ako X“, a o X®0 "sa správa ako 1/ X Hovorí sa, že „log X pri X®0 a ľubovoľné e>0 sa správajú ako X e a čo n®¥ nerastie rýchlejšie ako n log n Takéto nepresné, ale intuitívne jasné vyhlásenia sú užitočné pri porovnávaní funkcií rovnakým spôsobom ako vzťahy<, £ и = при сравнивании чисел.

Definujme tri hlavné asymptotické vzťahy.

Definícia 1. Funkcia f(X) je ekvivalentné g(X) pri X® x0, vtedy a len vtedy, ak =1.

V tomto prípade sa hovorí o funkcii f(X) sa asymptoticky rovná funkcii g(X) alebo čo f(X) rastie rovnakým tempom ako g(X).

Definícia 2. f(X)=o( g(X)) pri X® x0, vtedy a len vtedy, ak =0.

Hovoria, že o X® x 0 f(X) rastie pomalšie ako g(X), alebo čo f(X) „existuje o-malé“ z g(X).

Definícia 3 . f(X)=O( g(X)) pri X® x0, vtedy a len vtedy, ak existuje konštanta C taká, že sup =C.

V tomto prípade to hovoria f(X) nerastie rýchlejšie ako g(X), alebo čokoľvek X® x 0 f(X) „je tam veľké O“ od g(X).

pomer f(X)=g(X)+o(h(X)) pri X®¥ to znamená f(x)-g(X)=o(h(X)). Podobne f(X)=g(X)+O(h(X)) znamená to f(X)-g(X)=O(h(X)).

V nerovniciach možno použiť aj výrazy O( ) a o( ). Napríklad nerovnosť X+o(X)2 £ X pri X®0 znamená, že pre akúkoľvek funkciu f(X) také, že f(X)=o(X), o X®¥ x+f(X)2 £ X pre všetky dostatočne veľké hodnoty X.

Ukážme niekoľko užitočných asymptotických rovnosti.

Polynóm sa asymptoticky rovná svojmu najvyššiemu členu:

pri X®¥; (4.1)

pri X®¥; (4.2)

pri X®¥ a a k¹0. (4.3)

Súčty mocnin celých čísel spĺňajú vzťah:

pri n®¥. (4.4)

Preto máme najmä n®¥

Vo všeobecnejšom prípade, kedy n®¥ a pre akékoľvek celé číslo k³0

; (4.6)

. (4.7)

Opakujúce sa vzťahy

Ilustrujme koncept rekurentných vzťahov s klasickým problémom, ktorý položil a študoval Fibonacci okolo roku 1200.

Fibonacci vyjadril svoj problém vo forme príbehu o rýchlosti rastu populácie králikov za nasledujúcich predpokladov. Všetko to začína jedným párom králikov. Každý pár králikov sa stane plodným (plodným) po mesiaci, potom každý pár porodí každý mesiac nový pár králikov. Králiky nikdy neumierajú a ich rozmnožovanie sa nikdy nezastaví. Nechaj F n- počet párov králikov v populácii po n mesiacov a nech sa táto populácia skladá z N n vrhové páry a O n„staré“ páry, t.j. F n = N n + O n. V nasledujúcom mesiaci teda nastanú tieto udalosti:

Stará populácia v ( n+1)-tý moment sa zvýši o počet pôrodov v danom čase n, t.j. O n+1 = O n + N n= F n;

Každý starý v určitom okamihu n pár produkuje v čase ( n+1) pár potomkov, t.j. Nn+1= C n.

Nasledujúci mesiac sa tento vzorec opakuje:

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

Nn+2=O n+1;

spojením týchto rovností dostaneme Fibonacciho vzťah opakovania:

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

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

Voľba počiatočných podmienok pre Fibonacciho postupnosť nie je dôležitá; podstatné vlastnosti tejto postupnosti určuje rekurentný vzťah (4.8). Zvyčajne veril F0=0, F1= 1 (niekedy F0=F1=1).

Rekurencia (4.8) je špeciálny prípad homogénnych lineárnych rekurentných vzťahov s konštantnými koeficientmi:

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

kde koeficienty a i nezávisia od n a x 1, x2, …, x k sa považujú za dané.

Existuje všeobecná metóda riešenia (t. j. nájdenie x n ako funkciu n) lineárne rekurentné vzťahy s konštantnými koeficientmi. Uvažujme túto metódu pomocou vzťahu (4.8) ako príkladu. Riešenie nájdeme vo formulári

F n=crn (4.10)

s trvalým S a r. Dosadením tohto výrazu do (4.8) dostaneme

cr + 2 = crn+ 1 + crn,

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

Znamená to, že F n=crn je riešením, ak buď S=0, alebo r= 0 (a teda Fn = 0 pre všetkých n), a tiež (a to je zaujímavejší prípad), ak r 2 - r -1 = 0 a konštanta S svojvoľný. Potom z (4.11) vyplýva

r= alebo r = . (4.12)

Číslo "1,618" je známe ako "zlatý" pomer, od staroveku sa verilo, že trojuholník (obdĺžnik) so stranami 1 má najpríťažlivejšie proporcie.

Súčet dvoch riešení homogénnej lineárnej rekurencie je samozrejme tiež riešením a možno skutočne ukázať, že všeobecné riešenie Fibonacciho postupnosti je

F n= , (4.13)

kde sú konštanty S a s' sú určené počiatočnými podmienkami. Ak F 0 = 0 a F 1 = 1, dostaneme nasledujúcu sústavu lineárnych rovníc:

, (4.14)

ktorého riešenie dáva

c = -c" = . (4.15)

V matematike sa veľmi často používajú pojmy ako „rekurzívne funkcie“, „rekurentné sekvencie“, „rekurzívne vzťahy“, „rekurzívne algoritmy“. Všetky tieto výrazy majú rovnaký koreň, odvodený od latinského slova gesiggege – vrátiť sa. Pre rekurzívne funkcie, rekurzívne algoritmy a rekurzívne sekvencie je spoločné to, že na výpočet ďalšej hodnoty funkcie, získanie ďalšej implementácie algoritmu, určenie ďalšieho člena sekvencie je potrebné odkázať na ich predchádzajúce hodnoty. vypočítané skôr. Výpočet predchádzajúcich hodnôt zase vyžaduje prístup k predtým vypočítaným požadovaným hodnotám atď. Aby sme teda získali hodnotu funkcie, implementáciu algoritmu alebo hodnotu člena radu na popoludnie krok, musíte poznať ich hodnoty (P- 1)-tý krok, a teda na prvom kroku. Pravidlo, ktoré určuje, ako vypočítať ďalšiu hodnotu funkcie alebo ďalšieho člena sekvencie, keďže tieto hodnoty sú známe pre prvý krok, sa nazýva rekurzívny vzťah. Rozvoj rekurentných vzťahov je jednou z metód riešenia rôznych problémov. Táto metóda je široko používaná v kombinatorike.

Najjednoduchším príkladom rekurentného vzťahu je vzorec na výpočet počtu permutácií n-prvkovej množiny. Tieto vzorce vyzerajú R x = 1, R p = R p _ x p a možno ho získať nasledujúcim spôsobom.

Nech je tam P prvky /, / 2 , ..., /„, množiny ja Liu

Novú permutáciu týchto prvkov je možné získať takto: zoberte nejakú permutáciu prvkov /, / 2 , ..., a všetkými možnými spôsobmi medzi označené prvky vrátane začiatku a konca vložte prvok / a. Je jasné, že takéto metódy budú P. V dôsledku toho sa z permutácie /, / 2 , ..., / d _, získa P permutácií. To znamená, že permutácie z P prvky v P krát viac ako permutácií z P-1 prvok súpravy ja Tým sa vytvorí vzťah opakovania R p = R p _ x p. Pomocou tohto vzťahu postupne získame R p -pR p _ x \u003d p (p-) R p _ 2 - p (p - )(n -2)...2Р H. Ale R x - 1, pretože z jedného prvku možno urobiť len jednu permutáciu. Preto P n \u003d n (n-1)(" - 2)___2-1 = P. Na základe vyššie uvedeného

správne je aj nasledovné: R p = (P-jedenásť! = 1.

Teraz uvedieme príklad opakujúcej sa postupnosti čísel, ktorá sa často nazýva Fibonacciho čísla, po talianskom matematikovi 13. storočia, ktorý ho založil ako výsledok riešenia nasledujúceho problému. Pár králikov prináša raz za mesiac potomstvo dvoch králikov (samice a samca). Novonarodené králiky, dva mesiace po narodení, tiež prinášajú potomstvo. Koľko králikov sa objaví za rok, ak na začiatku bol jeden pár králikov?

Z podmienky problému vyplýva, že o mesiac budú dva páry králikov (prvý pár králikov prinesie potomstvo). Za dva mesiace - tri páry a za tri mesiace - päť párov, pretože pár, ktorý sa objavil po prvom mesiaci, dá potomstvo.

Označme /„ počet párov králikov po P mesiacov od začiatku roka. Potom na začiatku roka / 0 = 1, o mesiac /, = 2, o dva mesiace / 2 = / 0 + /, = 3, o tri mesiace / 3 = = / 2 + /1 =5. Preto vo všeobecnom prípade na výpočet počtu králikov na konci ktoréhokoľvek mesiaca získame opakujúci sa vzťah /„ = + / i _ 2 . Tento pomer to umožňuje

vypočítajte počet párov králikov na konci roka podľa výrazu / 12 \u003d / n + /Yu PR A za predpokladu, že / 0 = 1, /, = 2. Rovná sa 377. postupnosť 1, 2, 3, 5, 8, 13, ... sa nazýva Fibonacciho čísla. Je pozoruhodné, že pomocou rekurentného vzťahu popisujúceho tento číselný rad sa riešia mnohé problémy kombinatoriky. Tu je jeden z nich.

Nájdite počet postupností núl a jednotiek dĺžky P tie, v ktorých dve jednotky nie sú vedľa seba. Uistime sa, že tento problém možno vyriešiť pomocou vzťahu opakovania

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

Vezmite ľubovoľnú sekvenciu z P+1 nuly a jednotky také, aby neobsahoval dve po sebe idúce jednotky. Môže to skončiť nulou alebo jednotkou. Ak sekvencia končí nulou, môže byť vyradená a sekvencia dĺžky P, v ktorom dve jednotky nesusedia. Naopak, ak túto postupnosť zoberieme a na konci jej priradíme nulu, dostaneme takúto postupnosť dĺžky n+ 1, v ktorom nie sú dve jednotky vedľa seba.

Nech počet sekvencií dĺžky P+1, v ktorom dve jednotky nesusedia a ktoré končia nulou, sa rovná g n . Zoberme si teraz postupnosť LONG /7 + 1, v ktorej dve 1 nesusedia a ktorá končí 1. Keďže dve 1 nie sú susediace, pred poslednou 1 v poradí je nula, t.j. postupnosť končí na 01. Ak tieto čísla vyhodíme, dostaneme postupnosť dĺžky P - 1, v ktorom nie sú dva celky za sebou. Počet takýchto sekvencií gn_^. Pretože každá sekvencia je dlhá n+ 1, v ktorom dve jednotky nie sú za sebou, končia jednotkou alebo nulou, pre celkový počet takýchto postupností podľa súčtového pravidla dostaneme g n+ ^ - g n + g n_x. Navyše pre sekvencie dĺžky P= 1, existujú dve postupnosti: 0 a 1, v ktorých dve 1 nesusedia kvôli

prečo gl- 2. Pre sekvencie dĺžky P - 2 existujú tri postupnosti, v ktorých dve 1 nesusedia: 00, 01 a 10. Preto = 3. Vzťah opakovania gn+l = gn + gn_( , g^ = 2, g 2=3 je ekvivalentné rekurzívnemu vzťahu /i+1 = /„ + /, =2, /2 = 3, ktorý popisuje rad

Fibonacci. Preto pre ľubovoľné /7 = 1,2, ... pomocou tohto vzťahu je možné vyriešiť problém sformulovaný vyššie.

Treba poznamenať, že odvodenie rekurentných vzťahov je niekedy jednoduché a niekedy si vyžaduje značné úsilie. Pre niektoré problémy sú rekurencie jednoduché, pre iné zložité. Všeobecnou nevýhodou rekurentných vzťahov je, že na výpočet člena postupnosti je potrebné vypočítať všetky jej predchádzajúce členy.

Všeobecné riešenie rekurentný vzťah (1) je množina všetkých postupností, ktoré tento vzťah spĺňajú.

Súkromné ​​rozhodnutie vzťah (1) sa nazýva jedna z postupností vyhovujúcich tomuto vzťahu.

Príklad 1¢. Následná sekvencia a n=a 0 +nd a n=a n - 1 +d. Toto je vzorec pre spoločný výraz aritmetickej progresie s rozdielom d a s počiatočným členom progresie a 0 .

Príklad 2¢. Následná sekvencia b n=b 0 × q n je všeobecné riešenie vzťahu b n=b n - 1 ×q. Toto je vzorec pre spoločný člen geometrickej postupnosti s menovateľom q¹0 a s počiatočným členom progresie b 0 .

Príklad 3¢. Tzv Binetov vzorec j n= je partikulárne riešenie vzťahu j n=j n-2+j n-1 pre j0=j1=1.

Od jednoduchých koreňov X 1 ,…,x k párovo odlišné, potom D¹0. Systém (5) má teda (jedinečné) riešenie.

Úloha 1. Nájdite spoločný člen geometrickej postupnosti pomocou vzorca (4).

Riešenie b n=qb n- 1 vyzerá ako . Preto .

Úloha 2. Nájdite všeobecné riešenie Fibonacciho pomeru a n + 2 =a n+a n + 1 .

Riešenie. Charakteristický polynóm rekurentného vzťahu a n + 2 =a n+a n+ 1 má tvar . Preto .

Bez dôkazu uvádzame nasledujúce zovšeobecnenie 1. vety.

Veta 2. Nech má charakteristický polynóm homogénneho lineárneho rekurentného vzťahu (3). k korene: a 1 násobky , …, a k násobnosti , , . Potom má všeobecné riešenie rekurentného vzťahu (3) tento tvar:

Úloha 3. Nájdite všeobecné riešenie vzťahu.

Riešenie. Charakteristický polynóm má koreň 2 násobnosti 3. Preto .

Komentujte. Všeobecné riešenie nehomogénneho lineárneho vzťahu (2) možno nájsť ako súčet všeobecného riešenia homogénneho lineárneho vzťahu (3) a partikulárneho riešenia nehomogénneho lineárneho vzťahu (2).

4. Generovanie funkcií. Formálna séria a 0 +a 1 X+a 2 X 2 +…+a k x k+… volali generujúca funkcia postupnosti a 0 ,a 1 ,a 2 ,…,a k,…

Generujúca funkcia je buď konvergentný rad alebo divergentný rad. Dve divergentné rady môžu byť rovnaké ako funkcie, ale môžu byť generované funkciami rôznych postupností. Napríklad riadky 1+2 X+2 2 X 2 +…+2k x k+… a 1+3 X+3 2 X 2 +…+3k x k+… definuje rovnakú funkciu (v bode sa rovná 1 X= 1, v bodoch neurčitý X>1), ale generujú funkcie rôznych sekvencií.

Vlastnosti generujúcich funkcií postupností:

súčet (rozdiel) generujúcich funkcií postupností a n a b n sa rovná generujúcej funkcii súčtu (rozdielu) postupností a n+b n;

súčin generujúcich funkcií postupností a n a b n je generujúca funkcia sekvenčnej konvolúcie a n a b n:

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

Príklad 1 Funkcia generuje pre sekvenciu

Príklad 2 Funkcia generuje pre postupnosť 1, 1, 1, ...

Recidívny vzťah má rozkaz k , ak umožňuje vyjadrenie f(n+k) pomocou f(n), f(n+1), …, f(n+k-1).

Príklad.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 je vzťah opakovania druhého rádu.

f(n+3)=6f(n)f(n+2)+f(n+1) je opakujúci sa vzťah tretieho rádu.

Ak je daný rekurentný vzťah k-tého rádu, potom ho môže spĺňať nekonečne veľa postupností, keďže prvých k prvkov postupnosti je možné nastaviť ľubovoľne - nie sú medzi nimi žiadne vzťahy. Ale ak je zadaných prvých k členov, potom sú všetky ostatné prvky jednoznačne určené.

Pomocou rekurentného vzťahu a počiatočných členov je možné vypísať členy postupnosti jeden po druhom a skôr či neskôr dostaneme ktorýkoľvek z jej členov. Ak však potrebujete poznať iba jeden konkrétny člen postupnosti, potom nie je racionálne počítať všetky predchádzajúce. V tomto prípade je vhodnejšie mať vzorec na výpočet n-tého členu.

Riešenie rekurentného vzťahu volá sa ľubovoľná postupnosť, pre ktorú daný vzťah platí identicky.

Príklad. Postupnosť 2, 4, 8, …, 2 n je riešením vzťahu f(n+2)=3∙f(n+1) – 2∙f(n).

Dôkaz. Spoločný člen postupnosti je f(n)=2 n . Takže f(n+2)= 2 n+2, f(n+1)= 2n+1. Pre ľubovoľné n platí identita 2 n+2 =3∙2 n+1 – 2∙2 n. Preto pri dosadení postupnosti 2 n do vzorca f(n+2)=3f(n+1) – 2f(n) je vzťah splnený identicky. 2 n je teda riešením uvedeného vzťahu.

Riešenie rekurentného vzťahu volá sa k-tý rád všeobecný, ak závisí od k ľubovoľných konštánt α 1 , α 2 , … α k a výberom týchto konštánt možno získať akékoľvek riešenie tohto vzťahu.

Príklad. Vzťah opakovania je daný: f(n+2)=5f(n+1)-6f(n). Dokážme, že jeho všeobecné riešenie má tvar: f(n)= α 2 n + β3 n .

1. Najprv dokážeme, že postupnosť f(n)=α 2 n + β3 n je riešením rekurentného vzťahu. Dosaďte túto postupnosť do vzťahu opakovania.

f(n)= α 2 n + β 3 n, takže f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 teda

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).

Platí rekurentný vzťah, preto α 2 n + β 3 n je riešením tohto rekurentného vzťahu.

2. Dokážme, že akékoľvek riešenie vzťahu f(n+2)=5f(n+1)–6f(n) možno zapísať ako f(n)= α 2 n + β 3 n . Ale akékoľvek riešenie rekurencie druhého rádu je jednoznačne určené hodnotami prvých dvoch členov sekvencie. Preto stačí ukázať, že pre ľubovoľné a=f(1) ab=f(2) existujú α a β také, že 2 α +3 β =a a 4 α +9 β =b. Je ľahké vidieť, že systém rovníc má riešenie pre akékoľvek hodnoty a a b.

Teda f(n)= α 2 n + β 3 n je všeobecným riešením rekurentného vzťahu f(n+2)=5f(n+1)–6f(n).

Lineárne rekurentné vzťahy s konštantnými koeficientmi

Neexistujú žiadne všeobecné pravidlá na riešenie rekurentných vzťahov, ale existuje často sa vyskytujúca trieda rekurentných vzťahov, pre ktorú je známy algoritmus na ich riešenie. Ide o lineárne rekurentné vzťahy s konštantnými koeficientmi, t.j. typové pomery:

f(n+k)=c1f(n+k-1)+c2f(n+k-2)+...+ckf(n).

Nájdime riešenie všeobecného lineárneho rekurentného vzťahu s konštantnými koeficientmi prvého rádu.

Lineárny rekurentný vzťah s konštantnými koeficientmi prvého rádu má tvar: f(n+1)=c f(n).

Nech f(1)=a, potom f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, podobne ako f(4)=c 3 ∙a a tak ďalej, všimnite si, že f(n)=c n -1 ∙f(1).

Dokážme, že postupnosť c n -1 ∙f(1) je riešením rekurencie prvého rádu. f(n)=c n -1 ∙f(1), teda f(n+1)=c n f(1). Dosadením tohto výrazu do vzťahu dostaneme identitu c n f(1)=с∙ c n -1 ∙f(1).

Uvažujme teraz podrobnejšie lineárne rekurentné vzťahy s konštantnými koeficientmi druhého rádu , teda vzťahy formy

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

Všimnite si, že všetky úvahy platia aj pre vzťahy vyššieho rádu.

Vlastnosti roztoku:

1) Ak je postupnosť x n riešením (*), potom postupnosť a∙x n je tiež riešením.

Dôkaz.

x n je riešenie (*), teda x n +2 = C1 x n + 1 + C2 x n . Obe strany rovnosti vynásobíme a. Dostaneme a∙x n +2 =a∙(С 1 ∙x n +1 + С 2 ∙x n)= С 1 ∙a∙x n +1 + С 2 ∙a∙x n . To znamená, že ax n je riešenie (*).

2) Ak postupnosti x n a y n sú riešenia (*), potom postupnosť x n + y n je tiež riešením.

Dôkaz.

x n a y n sú riešenia, takže platia nasledujúce identity:

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

yn+2=Ciyn+1+C2yn.

Pridajme dve rovnosti po členoch:

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 n + 1) + C (x n + yn). To znamená, že x n + y n je riešením (*).

3) Ak je r 1 riešením kvadratickej rovnice r 2 =С 1 r+С 2, potom postupnosť (r 1) n je riešením vzťahu (*).

r 1 je riešením kvadratickej rovnice r 2 =C 1 r+C 2, teda (r 1) 2 =C 1 r 1 +C 2 . Vynásobme obe strany rovnosti (r 1) n . Získajte

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.

To znamená, že postupnosť (r 1) n je riešením (*).

Z týchto vlastností to vyplýva spôsob riešenia lineárne rekurentné vzťahy s konštantnými koeficientmi druhého rádu:

1. Zostavte charakteristickú (kvadratickú) rovnicu r 2 =C 1 r+C 2 . Nájdite jej korene r 1, r 2. Ak sú korene rôzne, potom všeobecné riešenie je f(n)= ar 1 n + βr 2 n .

2. Nájdite koeficienty a a β. Nech f(0)=a, f(1)=b. Systém rovníc

má riešenie pre ľubovoľné a a b. Tieto riešenia sú

Úloha . Poďme nájsť vzorec pre bežný člen Fibonacciho postupnosti.

Riešenie . Charakteristická rovnica má tvar x 2 \u003d x + 1 alebo x 2 -x-1 \u003d 0, jej korene sú čísla, čo znamená, že všeobecné riešenie má tvar f (n) \u003d . Ako je ľahké vidieť, z počiatočných podmienok f(0)=0, f(1)=1 vyplýva, že a=-b=1/Ö5, a teda všeobecné riešenie Fibonacciho postupnosti má tvar :

.

Prekvapivo tento výraz preberá celočíselné hodnoty pre všetky prirodzené hodnoty n.