5 spôsobov riešenia rekurenčných vzťahov

Pri snahe nájsť vzorec pre nejakú matematickú postupnosť je bežným medzikrokom nájsť n-tý člen nie ako funkciu n, ale v termínoch predchádzajúcich členov postupnosti. Napríklad, hoci by bolo pekné mať uzavretý tvar funkcie pre n-tý člen Fibonacciho postupnosti, niekedy máte k dispozícii len rekurenčný vzťah, a to, že každý člen Fibonacciho postupnosti je súčtom predchádzajúcich dvoch členov. Tento článok predstaví niekoľko metód na odvodenie vzorca v uzavretom tvare z rekurencie.

Metóda 1 z 5:Aritmetika


Uvažujme aritmetickú postupnosť, napríklad 5, 8, 11, 14, 17, 20, .…[1]


Keďže každý člen je o 3 väčší ako predchádzajúci, možno to vyjadriť ako rekurenciu, ako je uvedené na obrázku.


Uvedomte si, že každá rekurencia v tvare an = an-1 + d je aritmetická postupnosť.[2]


Napíšte uzavretý tvar vzorec pre aritmetickú postupnosť, prípadne s neznámymi, ako je uvedené.[3]


Vyriešte všetky neznáme v závislosti od toho, ako bola postupnosť inicializovaná. V tomto prípade, keďže 5 bol 0. člen, vzorec je an = 5 + 3n. Ak by ste namiesto toho chceli, aby prvým členom bolo 5, dostali by sten = 2 + 3n.[4]

Metóda 2 z 5: Geometrická


Uvažujme geometrickú postupnosť, napríklad 3, 6, 12, 24, 48, .


Keďže každý člen je dvojnásobkom predchádzajúceho, možno ho vyjadriť ako rekurenciu, ako je uvedené.


Uznajte, že každá rekurencia v tvare an = r * an-1 je geometrická postupnosť.


Napíšte uzavretý tvar vzorec pre geometrickú postupnosť, prípadne s neznámymi, ako je uvedené.


Riešte všetky neznáme v závislosti od toho, ako bola postupnosť inicializovaná. V tomto prípade, keďže 3 bol 0. člen, vzorec je an = 3*2n. Ak by ste namiesto toho chceli, aby bol prvým členom 3, dostali by ste an = 3*2(n-1).[5]

Metóda 3 z 5: Polynóm


Uvažujme postupnosť 5, 0, -8, -17, -25, -30, ... daných rekurziou an = an-1 + n2 – 6n.[6]


Každá rekurzia v zobrazenom tvare, kde p(n) je ľubovoľný polynóm v n, bude mať polynomický vzorec v uzavretom tvare o stupeň vyšší, ako je stupeň p.[7]


Napíšte všeobecný tvar polynómu požadovaného stupňa. V tomto príklade je p kvadratický, takže na reprezentáciu postupnosti a budeme potrebovať kubickýn.[8]


Keďže všeobecná kocka má štyri neznáme koeficienty, na vyriešenie výsledného systému sú potrebné štyri členy postupnosti. Stačia akékoľvek štyri, takže použime členy 0, 1, 2 a 3. Spustenie rekurencie dozadu na nájdenie -1. člena môže uľahčiť niektoré výpočty, ale nie je to nevyhnutné.[9]


Buď Vyriešte výslednú sústavu rovníc deg(p)+2 v deg(p)=2 neznámych alebo prispôsobte Lagrangeov polynóm známym bodom deg(p)+2.

  • Ak bol nultý člen jedným z členov, ktoré ste použili na riešenie koeficientov, získate zadarmo konštantný člen polynómu a môžete okamžite redukovať sústavu na rovnice deg(p)+1 v deg(p)+1 neznámych, ako je znázornené.


Uveďte uzavretý vzorec pre an ako polynóm so známymi koeficientmi.

Metóda 4 z 5: Lineárny


Toto je prvá metóda, ktorá dokáže vyriešiť Fibonacciho postupnosť v úvode, ale metóda rieši ľubovoľnú rekurenciu, kde n-ty člen je lineárnou kombináciou predchádzajúcich k členov. Skúsme to teda na inom uvedenom príklade, ktorého prvé členy sú 1, 4, 13, 46, 157, ….[10]


Napíšte charakteristický polynóm rekurencie. Nájde sa nahradením každého an v rekurencii xn a delením x(n-k), čím vznikne monický polynóm stupňa k a nenulový konštantný člen.[11]


Vyriešte charakteristický polynóm. V tomto prípade má charakteristika stupeň 2, takže na nájdenie jej koreňov môžeme použiť kvadratický vzorec.[12]


Každý výraz uvedeného tvaru spĺňa rekurziu. Ci sú ľubovoľné konštanty a základom exponentov sú korene k charakteristike nájdenej vyššie. To sa dá overiť indukciou.[13]

  • Ak má charakteristika násobný koreň, tento krok sa mierne modifikuje. Ak r je koreň s násobnosťou m, použite (c1rn + c2nrn + c3n2rn + … + cmnm-1rn) namiesto jednoduchého (c1rn). Napríklad postupnosť začínajúca 5, 0, -4, 16, 144, 640, 2240, … spĺňa rekurzívny vzťah an = 6an-1 – 12an-2 + 8an-3. Charakteristický polynóm má trojný koreň 2 a uzavretý vzorec an = 5*2n – 7*n*2n + 2*n2*2n.


Nájdite ci ktoré spĺňajú zadané počiatočné podmienky. Rovnako ako v prípade polynómu sa to robí vytvorením lineárnej sústavy rovníc z počiatočných členov. Keďže tento príklad má dve neznáme, potrebujeme dva členy. Budú stačiť ľubovoľné dva, takže vezmeme 0. a 1., aby sme nemuseli zvyšovať iracionálne číslo na vysokú mocninu.


Vyriešte výslednú sústavu rovníc.


Výsledné konštanty dosadíme do všeobecného vzorca ako riešenie.

Metóda 5 z 5:Generovanie funkcií


Uvažujme postupnosť 2, 5, 14, 41, 122 ... danú rekurziou na obrázku. Túto postupnosť nemožno vyriešiť žiadnou z uvedených metód, ale vzorec možno nájsť pomocou generujúcich funkcií.[14]


Napíšte generujúcu funkciu postupnosti. Generujúca funkcia je jednoducho formálny mocninový rad, kde koeficient xn je n-tym členom postupnosti.[15]


Manipulujte s generujúcou funkciou podľa obrázka. Cieľom tohto kroku je nájsť rovnicu, ktorá nám umožní vyriešiť generujúcu funkciu A(x). Vypočítajte počiatočný člen. Aplikujte rekurenčný vzťah na zvyšné členy. Rozdeľte súčet. Vyberte konštantné členy. Použite definíciu A(x). Použite vzorec pre súčet geometrického radu.


Nájdite generujúcu funkciu A(x).[16]


Nájdite koeficient xn v A(x). Metódy, ako to urobiť, sa budú líšiť v závislosti od toho, ako presne vyzerá A(x), ale metóda parciálnych zlomkov v kombinácii so znalosťou generujúcej funkcie geometrickej postupnosti tu funguje podľa nasledujúceho postupu.


  • Napíšte vzorec pre an určením koeficientu xn v A(x).
  • Odkazy