Řešený příklad na rekurencí zadané posloupnosti (12. týden, Jaroslav Seděnka)
Zadání: Najděte nekonečnou posloupnost (aj)^0 zadanou rekurencí:
an = 4an_i — 3an_2 + 1
s počátečními podmínkami clq = l,a± = 2.
Řešení (pomocí charakteristického polynomu): První vyřešíme homogenní rekuretní rovnici (bez absolutního člene)
an = 4an_i — 3an_2
U lineární homogenní rekurence (tj. bez vyšších mocnin a bez absolutního člene) hledáme řešení tvaru an = cAn pro c £ M, A G C. Po dosazení An za an dostaneme rovnici
An = 4An-l _ 3An-2
Charakteristický polynom je tedy
An~2(A2 - 4A + 3)
Kromě triviálního řešení Ao = 0 můžeme ještě vyřešit kvadratickou rovnici A2 — 4A + 3 = 0 a získáme kořeny Ai = 3, A2 = 1. Obecné řešení homogenní rekurence je tedy
an = ci(ln) + c2(3n) = ci + c23n pro ci, c2 G M libovolné.
Nyní hledáme partikulární řešení původní rekurence an = 4an_i — 3an_2 + 1, zatím stále bez uvážení počátečních podmínek. Budeme hledat partikulární řešení (tj. libovolnou posloupnost splňující danou rekurenci) ve tvaru polynomu an = p{n). Začneme s konstantním polynomem
Qifi — k.
k = Ak - 3k + 1 0 = 1
Žádná konstantní posloupnost nevyhovuje, pokračujeme s lineárním polynomem an = ln + k:
ln + k = 4(l(n - 1) + k) - 3(l(n - 2) + k) + 1 In + k = Aln - AI + Ak - Sin + 6l-3k + l 0 = 21 + 1
í=-i
2
Tedy partikulárním řešením je posloupnost an = — ^ + k pro tel libovolné. Každé řešení nehomogenní rekurence je právě součet (libovolného) partikulárního řešení s nějakým řešením homogenní soustavy, obecné řešení zadané rekurence jsou
n
an = c1+ c23n - -
(Koeficient k se "schoval" do c\.)
Nyní zbývá zahrnout počáteční podmínky ao = 1, a± =2. Dosadíme obě do obecného řešení a získáme soustavu dvou rovnic o dvou neznámých:
1 = a0 = ci + c23 - - = ci + c2, tedy c\ = 1 - c2 2 = ai = ci + C231 — — = ci + 3c2 — —, dosadíme c\ = 1 — c2
2 = (1 - c2) + 3c2 - i = 1 - 2c2 - i
3 ,31
- = -2c2, tedy c2 = -, cx = -
Posloupností splňující všechny podmínky ze zadání je tedy
4        2 4
Můžete si dosazením za prvních několik n sami ověřit, že tato posloupnost splňuje počáteční podmínky i rekurentní rovnici.
Tento způsob řešení rekurencí je univerzální, jeho popis můžete najít například v učebnici na v Kapitole 3, podkapitole 2, odstavec 3.9 teorie.
Jiný způsob řešení (pomocí vytvořujících funkcí): Místo posloupnosti (ao, ai, ...an,...)
budeme hledat funkci odpovídající formální mocninné řadě
A(x) =      a^xk = ao + a\x + a2x2 + ...
k=o
Ze zadání navíc známe vztah pro koeficienty a& této řady:
a/c = 4<2fc_i — 3a&_2 + 1 (pro k > 2 nebo k = 0 , vždyť a; = 0 pro Z < 0)
ai = 4ao — 3a_i + 1 — 3 Můžeme nyní vynásobit každou z těchto rovností xk a pak je všechny sečíst. Dostaneme
A(x) = 4xA(x) - 3x2A(x) + í ^ xk \ - 3x
\k=o )
Z této rovnosti můžeme úpravami vyjádřit vytvořující funkci pro A{x).
A(x) - 4xA(x) + 3x2A(x) = I ^ xk ] - 3x
\k=0 )
(Ľ£o*fc)-3z_(££o*fc)-3z_      Eľ=o^ 3x
A(x)
3x2-4x + l       (l-x)(l-3x)     (l-x)(l-3x)     (1 - x)(l - 3x)
1 3x
(l-x)2(l-3x)     (1 - x)(l - 3x) Po rozkladu na parciální zlomky dostaneme
i z \    3     1 3     1 11
4(l-3x)    4(l-x) 2(l-x)s
Přechodem od parciálních zlomků zpět k formálním mocninným řadám (a s využitím našich znalostí o vytvořujících řadách z předchozích cvičení) dostaneme
\k=0 / \k=0     / \k=0 /
Explicitní vyjádření pro členy posloupnosti an dostaneme porovnáním koeficientů u jednotlivých mocnin xn na obou stranách rovnosti:
3 r.    3    1 ,       .     3 r.    1 ti an = -3n H----(n + 1) = -3n H----
4 4    2v;    4       4 2
Příklad vyšel (pochopitelně) stejně oběma způsoby. Tato metoda je však obecnější a dokážeme její pomocí explicitně vyjádřit i složitější rekurence. Návod na použití a podrobnější popis najdete v Kapitole 12 učebnice, mezi odstavci 12.42 a 12.43 teorie.