Řešení homogenních lineárních rekurentních formulí s konstantními koeficienty Budeme muset nejprve připomenout některé známé poznatky o rozkladech racionálních lomených funkcí na parciální zlomky. Buď M[x] algebra formálních mocninných řad nad tělesem IR. všech reálných čísel Ukážeme, že pro každou mocninnou řadu Yl^Lo a"x" z takovou, že ao 7^ 0, existuje v M[x] mocninná řada Yl^Lo ^n*" taková, zeje splněno 00 00 5>x" . J>x" =1. A7=0 / \n=0 / Jinak řečeno, každá mocninná řada X^oa"x"' v n^ ao 0» je jednotkou okruhu M[x]. Skutečně, podle definice násobení mocninných řad výše uvedená podmínka žádá, aby platilo 3ob0 = 1, n 3obn + äibn-i = 0 pro všechna kladná celá čísla n. i=l Tyto požadavky je ale možno splnit. Poněvadž ao 7^ 0, potřebné koeficienty bo, fai, b2,..., bn,... je odtud možno jeden po druhém postupně vypočítat. Právě zjištěný fakt zejména znamená, že k libovolnému polynomu g z M[x] s nenulovým absolutním členem existuje v M[x] mocninná řada, která je k němu inverzním prvkem. Tuto mocninnou řadu pak můžeme zapsat jako -. S využitím tohoto počítání invezních prvků v algebře M[x] je pak možno obecněji racionální lomené funkce, tedy zlomky tvaru ^, kde f,g jsou polynomy z M[x] a g je polynom s nenulovým absolutním členem, převádět na formální mocninné řady. Jsou známy následující fakty o rozkladech racionálních lomených funkcí na parciální zlomky. Nechť /"je polynom z M[x] a nechť g je nenulový normovaný polynom z M[x]. Nechť g = /?i.....hm, kde m je kladné celé číslo a ..., hm jsou vzájemně nesoudělné normované polynomy z M[x]. Pak existují polynomy c, di,..., dm v M[x] splňující st c/i < st ... , st dm < st hm takové, že platí d f c/i - = c+- + + 1 m 'm Tyto polynomy c, c/i,..., c/m jsou určeny jednoznačně. Je-li st f < st g, pak c = 0. Uvedený fakt je zobecněním Bezoutovy věty a lze ho pomocí ní dokázat indukcí vzhledem k číslu m. Jsou-li všechny činitele v předchozím rozkladu g = h\.....hm mocninami normovaných lineárních polynomů, to jest jsou-li tvaru (x — r)k pro nějaké reálné číslo r a nějaké kladné celé číslo k, je možno jít ještě dále. (Takový rozklad polynomu g je vždy možný, jestliže pracujeme nad tělesem C všech komplexních čísel místo tělesa M všech reálnvch čísel Pak pro libovolný polynom d z M[x] splňující st d < k existují jednoznačně určená reálná čísla si, S2,..., Sk taková, že platí d + + ••• + x — r Abychom se o tom přesvědčili, stačí provést rozvoj polynomu d se středem v hodnotě r. Vraťme se teď k řešení naší homogenní lineární rekurentní formule /c-tého řádu s konstantními koeficienty pro neznámou funkci y(n). Tato funkce y(n) bude záviset na jedné nezáporné celočíselné proměnné n a jejími hodnotami budou nyní nějaká reálná čísla. Připomeňme, že tato rekurentní formule je podmínkou tvaru y(n + k) + aiy(A7 + k - 1) + a2y(n + k - 2) + • • • + aky(n) = 0, která ale má být splněna pro všechna nezáporná celá čísla n. Konstantami 3i, <325 • • •, 3k budou nyní nějaká reálná čísla. Hledáme všechna řešení této rekurentní formule, to jest všechny funkce y(n) vyhovující uvedené podmínce, či spíše uvedené soustavě podmínek. Množina všech těchto řešení je nekonečná, tvoří totiž vektorový prostor dimenze k nad tělesem M všech reálných čísel. (Předesíláme už teď, že budeme muset později přejít nad těleso C všech komplexních čísel.) Libovolná lineární kombinace funkcí, které jsou řešeními takové rekurentní formule, je totiž sama rovněž řešením této rekurentní formule. Navíc na prvních k hodnot y(0), y(l), y(2),..., y(/c — 1) libovolného řešení y(n) této rekurentní formule se nekladou žádná omezení, takže je lze volit libovolně. Odtud vyplývá, že k je dimenze vektorového prostoru všech řešení naší rekurentní formule. Jestliže však tyto počáteční hodnoty y(0),y(l),y(2),... ,y(/c — 1) jsou předem pevně stanoveny, to jest mají-li být navíc splněny takzvané počáteční podmínky y(o) = #o, y(i) = #i, y(2) = ů2,..., y(k-i) = ůk_u kde ůo, i?23 • • • 5 ůk-i jsou dané reálné hodnoty, pak je tím řešení y(n) určeno jednoznačně. Je-li známa nějaká báze vektorového prostoru všech řešení, pak toto poslední řešení je nějakou její lineární kombinací. K určení koeficientů v této lineární kombinaci stačí řešit soustavu lineárních rovnic očividným způsobem sestavenou na základě daných počátečních podmínek. Potřebujeme tedy najít nějakou bázi vektorového prostoru všech řešení naší homogenní lineární rekurentní formule s konstantními koeficienty. K tomu účelu definujeme takzvaný charakteristický polynom této rekurentní formule h(x) = xk + 3Xxk~x + a2xk~2 + • • • + 3k. Tento polynom lze nad tělesem C všech komplexních čísel rozložit na součin lineárních polynomů ve tvaru h(x) = (x - n)ei.....(x - rt) kde t je kladné celé číslo, exponenty ei,..., et jsou kladná celá čísla splňující ei + • • • + et = k a ri,..., rt jsou vzájemně různá komplexní čísla, která splňují ri.....neboť a^ 7^ 0, ježto naše rekurentní formule je řádu k. Položme Pak výše uvedený rozklad polynomu h(x) přejde na rozklad polynomu g(x) ve tvaru {y(n)}^Lo hodnot hledaného řešení y(n) naší rekurentní formule. Pak tato rekurentní formule říká přesně to, že v součinu w(x) • g(x) jsou koeficienty u mocnin xn+k pro všechna nezáporná celá čísla n rovny nule. Podle definice násobení mocninných řad je totiž koeficient u mocniny xn+k v součinu w(x) • g(x) roven y(n + k) + a\y{n + k — 1) + a^yin + k — 2) + • • • + a^y^n) = 0. dále To ale znamená, že existuje polynom f(x) = Pk-lX*'1 + pk-2Xk~2 + • • • + po, kde pk-i, Pk-2, • • •, Po jsou nějaká reálná čísla, takový, že platí w(x) ■ g{x) = f(x), v ■ I ■ Clil w{x) = WY neboť g(x) je polynom s absolutním členem rovným 1, takže jím lze dělit v okruhu formálních mocninných řad. Ukážeme, jak lze zlomek vpravo šikovným způsobem rozvinout v mocninnou řadu. Vzhledem k předchozímu rozkladu polynomu g(x) na součin lineárních faktorů víme podle výsledků o rozkladech na parciální zlomky, že existují komplexní čísla Sn, • • • 5 ^iei5 • • • 5 ^ři? • • • 5 $tet taková, že platí ŕ \ Sn i i Slei i i Sŕl i i Stet w[x) =---1-----h jz-r— H-----h---1-----h rix (1 - rix)ei 1 - rtx (1 - rtx)e'' Počet sčítanců v tomto vyjádření mocninné řady w(x) je roven ei + • • • + et = k. Generující řada w(x) libovolného řešení naší rekurentní formule je tedy lineární kombinací zlomků tvaru 1 ,e' (1 - rx} kde r = r, pro některé / = 1,..., t a e G {1,..., e,}. Takový zlomek ale lze rozvinout do mocninné řady následovně: oo (1 - rx)"e = ((1 - rx)-1)* = J>x)" A7=0 Poslední mocninu uvedené mocninné řady lze vypočíst s odkazem na definici kombinací s opakováním a na příslušné binomické koeficienty takto: OO \ OO / x OO/ \ A7=0 / A7=0 ^ ' A7=0 ^ ' Po rozepsání takového binomického koeficientu nakonec celkem vyjde 1 OO (e-1) A7=0 Generující řady w(x) všech řešení naší rekurentní formule jsou tedy lineárními kombinacemi mocninných řad tvaru oo £>+e-l]e-lTnXn, A7=0 kde r = r, pro některé / = 1,..., t a e G {1,..., e,}. Protože takových mocninných řad je celkem k a vektorový podprostor všech řešení má dimenzi k, musí zde jít o všechny možné lineární kombinace. Přitom funkce [n + e — l]e-r rn proměnné n pro všechna zmíněná r a e tvoří bázi vektorového prostoru všech řešení naší rekurentní formule. Poněvadž navíc klesající faktoriály [n + e — l]e-i jsou polynomy v proměnné n stupňů e — 1 pro všechna výše uvedená e, tvoří tyto faktoriály bázi v příslušném vektorovém prostoru polynomů. Lze je proto nahradit jednoduššími polynomy A7e_1 pro všechna uvedená e, které rovněž tvoří bázi dotyčného vektorového prostoru polynomů. Takže také funkce A7e_1- rn proměnné n pro všechna zmíněná r a e tvoří bázi vektorového prostoru všech řešení naší rekurentní formule. Celkem tedy generující řady w(x) všech řešení naší rekurentní formule jsou právě všechny lineární kombinace mocninných řad tvaru oo A7=0 kde r = r, pro některé / = 1,..., t a e G {1,..., e,}. Řešení této rekurentní formule jsou pak odpovídající lineární kombinace funkcí A7e_1- rn. Tyto funkce přitom tvoří bázi vektorového prostoru všech řešení rekurentní formule. Tyto závěry lze souhrnně formulovat takto: Nechi je dána homogenní lineární rekurentní formule s konstantními koeficienty. Necht ri,..., rt jsou všechny vzájemně různé kořeny jejího charakteristického polynomu v oboru komplexních čísel, necht ei,..., et jsou jejich násobnosti. Pak funkce jedné nezáporné celočíselné proměnné n tvaru A7e_1- r" pro všechna i = 1,..., t a e = 1,..., e,- tvoří bázi vektorového prostoru všech řešení této rekurentní formule nad komplexními čísly. □