Rekurentiniai s¹ryšiai ir generuojančios funkcijos

Rekurentiniai s¹ryšiai ir generuojančios funkcijos

Kaip minėjome, rekurentiniai s¹ryšiai generuoja skaitines sekas, o šioms galima užrašyti generuojančias funkcijas. Šiame paragrafe panagrinėkime, kaip, turint tiesinį rekurentinį s¹ryšį, sudaryti jam atitinkanči¹ generuojanči¹ funkcij¹.

Tam tikslui panagrinėkime taisykling¹j¹ algebrinź trupmen¹ , čia ir – atitinkamai n-osios ir m-osios () eilės polinomai:

ir

Aišku, kad

(3.7.1)

Vadinasi,

Sudauginź (3.7.1) dešini¹j¹ pusź ir palyginź koeficientus prie tų pačių x laipsnių, gausime

(3.7.2)

čia didžiausia galima n reikšmė yra

Visi tolesni s¹ryšiai bus vienodo pavidalo:

(3.7.3)

Vadinasi, (3.7.1) eilutės koeficientai tenkina (3.7.3) tiesinį rekurentinį s¹ryšį, o (3.7.2) apibrėžia šio rekurentinio s¹ryšio pradines s¹lygas.

Atvirkščiai, tarkime, kad duotas m-osios eilės (3.7.3) rekurentinis s¹ryšis ir pradinės s¹lygos . Tada šiam s¹ryšiui atitinkanti generuojanti funkcija yra trupmena

(3.7.4)

čia – rekurentinio s¹ryšio koeficientai, o – koeficientai, apskaičiuoti iš (3.7.2) lygčių.

Pastaba. Tarkime, , čia – polinomo

šaknys. Tada (3.7.1) eilutė konverguoja srityje

Pavyzdys. Sudarysime Fibonačio skaičių sekos generuojanči¹ funkcij¹. Fibonačio skaičius generuojantis rekurentinis s¹ryšis yra

Vadinasi, Fibonačio skaičius generuojanti funkcija yra

Koeficientus a₀ ir a₁ apskaičiuosime pagal (3.7.2) formules:

Tuo būdu, Fibonačio skaičių sekos generuojanti funkcija yra

Iš pirmo žvilgsnio atrodo, kad mažai k¹ laimėjome, rekurentinį s¹ryšį pakeisdami generuojančia funkcija: juk vis tiek reikės skaitiklį dalyti iš vardiklio, o iš to gausime t¹ patį rekurentinį s¹ryšį. Tačiau (3.7.4) trupmen¹ galima tapačiai pertvarkyti, o tai palengvina skaičių c_k radim¹.

Pavyzdys. Tarkime, generuojanti funkcija yra

Išdėstykime ši¹ trupmen¹ paprastesnėmis trupmenomis.

Šis uždavinys buvo sprźstas matematinės analizės kurse. Tam tikslui raskime vardiklio polinomo šaknis:

Vadinasi,

Abi lygybės puses padauginź iš bendro vardiklio ir palyginź skaitiklių koeficientus prie tų pačių x laipsnių, gausime:

Šios sistemos sprendinys yra:

, , ir .

Trupmenos eilutė žinoma. Pavyzdžiui,

Tokiu būdu, gausime:

Apskaičiavź koeficient¹ prie , gausime:

Tuo pačiu gavome generuojančiai funkcijai atitinkančio rekurentinio s¹ryšio sprendinį.

Šis nagrinėjimas duoda mintį, kaip galima sprźsti rekurentinį s¹ryšį, panaudojant generuojančias funkcijas.

Tam tikslui reikia:

sudaryti rekurentiniam s¹ryšiui generuojanči¹ funkcij¹ ,

išreikšti elementariųjų trupmenų suma, o jas – laipsninėmis eilutėmis (pagal Niutono formulź),

gautos eilutės koeficientas prie ir bus ieškomasis sprendinys.

Pavyzdys. Išsprźskime rekurentinį s¹ryšį:

Šiuo atveju , ir .

Pagal (3.7.2) formules apskaičiuosime a₀ ir a₁:

Vadinasi, rekurentinį s¹ryšį atitinkanti generuojanti funkcija yra

Ši trupmena elementariosiomis trupmenomis išreiškiama taip:

ir, išskaidź eilute, gausime:

Todėl

Reikia pabrėžti, kad rekurentinių išraiškų sprendimas charakteristinių šaknų metodu yra žymiai efektyvesnis nei generuojančių funkcijų metodas.