Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo oooo OOOO Matematika IV - 9. týden Vytvořující funkce Jan Slovák Masarykova univerzita Fakulta informatiky jaro 2014 Q Vytvořující funkce a Fibonacciho čísla Q| Vytvořující funkce - připomenutí Q Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení reki ooooo oooo OOOO • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí OOOO • Jan Slovák, Martin Panák, Michal Bulant Matematika drsně a svižně, e-text na www.math.muni.cz/Matematika_drsne_svizne. • Donald E. Knuth, The Art Of Computer Programming. • Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1994. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo oooo oooo Plán přednášky Q Vytvořující funkce a Fibonacciho čísla Ql Vytvořující funkce - připomenutí Ql Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla •OOOO Vytvořující funkce - připomenutí OOOO Řešení rekurencí OOOO Fibon acciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Literatura Vytvořující funkce a Fibonacciho čísla •OOOO Vytvořující funkce - připomenutí OOOO Řešení rekurencí OOOO Fibon acciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = 1], [2\n] a pod. Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí •oooo oooo oooo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fq = 0, Fi = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice (podrobně viz http://is.muni.cz/th/41281/prif_d/disertace.pdf). Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát] -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = 1], [2\n] a pod. Pro vyjádření koeficientu u x" ve vytvořující funkci F(x) se pak často používá zápis [x"]F(x). ■0 0.0 Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení reki o»ooo oooo OOOO Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fq = 0, F\ = 1 je to F{x) — xF{x) — x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení reki o»ooo oooo OOOO Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fq = 0, F\ = 1 je to F{x) — xF(x) — x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ A B 1 — X — X2 X — X\ X — X2 ' kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Literatura Vytvořující funkce a Fibonacciho čísla o»ooo Vytvořující funkce - připomenutí oooo Řešení rekurencí OOOO Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Při podmínkách Fq = 0, F\ = 1 je to F{x) — xF(x) — x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti. Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ A B 1 — X — X2 X — X\ X — X2 ' kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Po substituci Ai = l/xi,A2 = l/x2 dostáváme vztah x a b 1 — x — x2 1 — Aix 1 — A2X' odkud už vcelku snadno vyjde Fn = a • A" + b • AÍJ, jak to známe z dřívějška. , u „ < < 1 ► 1 -00.O Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí oooo* oooo oooo Rozklad na parciální zlomky - pokr. • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/(x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí oooo* oooo oooo Rozklad na parciální zlomky - pokr. • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/(x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. • Neznámé dopočítáme bud' roznásobením a porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí oooo* oooo oooo Rozklad na parciální zlomky - pokr. • V případě dvojice komplexně sdružených kořenů nahrazujeme sčítanec A/(x — a) sčítancem (Ax + B)/(x2 + px + q) včetně příslušných mocnin jmenovatele. • Neznámé dopočítáme bud' roznásobením a porovnáním koeficientů u jednotlivých mocnin x nebo dosazením jednotlivých kořenů. • Výrazy A/(x — a)k převedeme na výrazy tvaru 6/(1 — (3x)k vydělením čitatele i jmenovatele výrazem {—a)k. Tento výraz již umíme rozvinout do mocninné řady. Q Vytvořující funkce a Fibonacciho čísla Q| Vytvořující funkce - připomenutí Ql Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí •ooo Řešení rekurencí OOOO Definice Buď dána nekonečná posloupnost a = (an, ai, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo ^ 3/x' = 30 + 3lX + 32X2 H----. /=0 Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. n>0 1Používají se i další typy vytvořujících funkcí (napf.w teoši číset se peužívají -00.0 Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí •ooo Řešení rekurencí OOOO Tinice Buď dána nekonečná posloupnost a = (an, ai, 32,...). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru oo ^ 3/x' = 30 + 3lX + 32X2 H----. /=0 Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciální varianty1. n>0 Poznámka Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořující funkcí pro základní posloupnost (1,1,1,1,...). - f Používají se i další typy vytvořujících funkcí (např. v teorii čísel se používají Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí 0900 Řešení rekurencí OOOO Věta z matematické analýzy: Věta Bud (sq, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G M, že pro všechna n > 1 je \an\ < Kn, pak řada a{x) = ^2 an*n n>0 konverguje pro každé x G Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí 0900 Řešení rekurencí oooo Věta z matematické analýzy: Věta Bud (sq, 3i, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G M, že pro všechna n > 1 je \an\ < Kn, pak řada a{x) = ^2 an*n n>0 konverguje pro každé x G Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a(x). Hodnotami funkce a(x) na libovolném okolí 0 je jednoznačně určena původní posloupnost, nebot má a(x) v 0 derivace všech řádů a platí _ a(")(0) Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo 0090 oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: 4Ľ3k4l3*4 = k4 = * -š -O^O Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo 00»0 OOOO Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí 0090 Řešení rekurencí oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo 0090 oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo 0090 oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (an,..., a/c-i, 0,...) a poté podělíme vytvořující funkci xk. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo 0090 oooo Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (af- + b,) posloupností člen po členu odpovídá součet a(x) + b(x) příslušných vytvořujících funkcí. • Vynásobení (a • a,-) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a • a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (an,..., a/c-i, 0,...) a poté podělíme vytvořující funkci xk. • Substitucí polynomu f(x) s nulovým absolutním členem za x vytvoříme specifické kombinace členů původní posloupnosti. Jednoduše je vyjádříme pro f(x) = ax, což odpovídá vynásobení /c-tého členu posloupnosti skalárem ak. Dosazení f(x) = x" nám do posloupnosti mezi každé dva členy vloží Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rekurencí ooooo ooo« oooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 333,...), člen s indexem k je (k + 1)3^+1 (tj. mocninnou řadu derivujeme člen po členu). Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí ooo« Řešení rekurencí oooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce s'(x) vytvořuje posloupnost (ai, 2a2, 333,...), člen s indexem k je (k + l)a/(+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce f* a(t)dt vytvořuje posloupnost (0, 3o, \a\, ^32, \a-i-, ■ ■ ■), pro k > 1 je člen s indexem k roven \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce s(x)). Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí ooo« Řešení rekurencí oooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2, 333,...), člen s indexem k je (k + 1)3^+1 (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce f* a(t)dt vytvořuje posloupnost (0, 3o, \a\, ^32, \a-i-, ■ ■ ■), pro k > 1 je člen s indexem k roven \sk-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce s(x)). • Násobení řad: součin a{x)b{x) je vytvořující funkcí posloupnosti (cq, ci, C2,...), kde tj. členy v součinu až po c^ jsou stejné jako v součinu (a0 + aix + s2x2 H-----h akxk)(b0 + Z>ix + fa2x2 H----^x^). Posloupnost (c„) bývá také nazývána konvolucí posloupností i+j=k (an), (*M- Q Vytvořující funkce a Fibonacciho čísla Ql Vytvořující funkce - připomenutí Q Řešení rekurencí Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí •ooo Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí ( a to nejen lineárních!). Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n £ No (předpokládajíce a_i = a_2 = • • • = 0). Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí •ooo Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí ( a to nejen lineárních!). Tím je míněno vyjádření členu a„ jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", coz Je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí •ooo Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí ( a to nejen lineárních!). Tím je míněno vyjádření členu an jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", coz Je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). O Zjištěná rovnice se vyřeší vzhledem k A(x). Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí •ooo Mocninné řady jsou velmi silným nástrojem pro řešení rekurencí ( a to nejen lineárních!). Tím je míněno vyjádření členu a„ jako funkci n. Často se s pomocí řad podaří vyřešit na první pohled velmi složité rekurence. Obvyklý (takřka mechanický) postup pro řešení rekurencí se skládá ze 4 kroků: O Zapíšeme jedinou rovnicí závislost an na ostatních členech posloupnosti. Tento vztah musí platit pro všechna n G No (předpokládajíce a_i = a_2 = • • • = 0). O Obě strany rovnice vynásobíme x" a sečteme přes všechna n G No- Na jedné straně tak dostaneme J2n anx", coz Je vytvořující funkce A(x). Pravou stranu vztahu je pak třeba upravit na výraz rovněž obsahující A(x). O Zjištěná rovnice se vyřeší vzhledem k A(x). Q Výsledné A(x) se rozvine do mocninné řady, přičemž koeficient u x" udává an, tj. an = íx"l/4(x) . Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí o»oo ' Příklad ^ Řešte rekurenci a0 = 0, ai = 1 3n = 5an_i — 6a„_2 Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí o»oo ' Příklad ^ Řešte rekurenci a0 = 0, ai = 1 3n = 5an_i — 6a„_2 Řešení • Krok 1: an = 5an-i — 63^-2 + [n = 1]. Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí o»oo ' Příklad ^ Řešte rekurenci a0 = 0, ai = 1 3n = 5an_i — 6a„_2 Řešení • Krok 1: a„ = 5a„_i — 6a„_2 + [n = 1]. • Krok 2: A{x) = bxA(x) - 6x2A(x) + x. Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí o»oo ' Příklad ^ Řešte rekurenci a0 = 0, ai = 1 3n = 5an_i — 6a„_2 Řešení • Krok 1: a„ = 5a„_i - 6an_2 + [n = 1]. • Krok 2: A(x) = 5xA(x) - 6x2A(x) + x. • Krok 3: x 1 1 A(X' ~ 1 -5x + 6x2 ~ 1 -3x l-2x' Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí o»oo ' Příklad ^ Řešte rekurenci a0 = 0, ai = 1 3n = 5an_i — 6a„_2 Řešení • Krok 1: a„ = 5a„_i - 6an_2 + [n = 1]. • Krok 2: A(x) = 5xA(x) - 6x2A(x) + x. • Krok 3: x 1 1 A(X' ~ 1 -5x + 6x2 ~ 1 -3x l-2x' • Krok 4: an = 3"-2". Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí oo»o Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L = [ ]: return [] return qsort([x for x in L[l:] if x=L[0]]) Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení rek ooooo oooo oo»o Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L = [ ]: return [] return qsort([x for x in L[l:] if x=L[0]]) Q Počet porovnání při rozdělení (divide): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je k-tý největší, je ^. @ Velikost tříděných polí ve fázi conquer: k — 1 a n — k. Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí oo»o Ukázka implementace (divide and conquer, rozmyslete, proč není optimální): i f L = [ ]: return [] return qsort([x for x in L[l:] if x=L[0]]) O Počet porovnání při rozdělení (divide): n — 1. O (Předpoklad náhodnosti): Pravděpodobnost toho, že prvek L[0] je k-tý největší, je ^. O Velikost tříděných polí ve fázi conquer: k — 1 a n — k. Pro střední hodnotu počtu porovnání tak dostáváme rekurentní vzta h: " 1 Cn = n-1 + ^2- (Q_i + Cn_k). k=l Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí ooo» Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = Cx = 0 k=l pomocí uvedeného postupu. Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení reki ooooo oooo ooo» Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = d = 0 k=l pomocí uvedeného postupu. • E„>o "Cnxn = £n>0 n(n - l)x" + 2 £„>o ELi Q-ix" Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí ooo» Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = d = 0 k=l pomocí uvedeného postupu. • E„>o "Cnxn = J2n>o n{n - l)x" + 2 £„>o ELi Q-ix" • xC'(x) = ^ + 2Í| Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí ooo» Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = d = 0 k=l pomocí uvedeného postupu. • E„>o "Cnxn = J2n>o n{n - l)x" + 2 £„>o ELi Q-ix" • *C'(x) =(i^ + 2Í| • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = I^, Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí ooo» Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = d = 0 k=l pomocí uvedeného postupu. • E„>o "Cnxn = J2n>o n{n - l)x" + 2 £„>o ELi Q-ix" • *C'(x) =(i^ + 2Í| • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = I^, Literatura Vytvořující funkce a Fibonacciho čísla Vytvořující funkce - připomenutí Řešení reki ooooo oooo ooo» Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = d = 0 k=l pomocí uvedeného postupu. • E„>o "Cnxn = J2n>o n{n - l)x" + 2 £„>o ELi Q-ix" • *C'(x) =(i^ + 2Í| • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = 1^,atedy (1 - X)2 V 1 -X Literatura Vytvořující funkce a Fibonacciho čísla ooooo Vytvořující funkce - připomenutí oooo Řešení rekurencí ooo» Vyřešme nyní rekurenci n nCn = n(n - 1) + 2 C0 = Cx = 0 k=l pomocí uvedeného postupu. • E„>o "Cnxn = J2n>o n{n - l)x" + 2 £„>0 ELi Q-ix" • xC'(x) = ^ + 2Í| • Vyřešíme tuto lineární diferenciální rovnici prvního řádu ((l-x)2C(x))' = 1^,atedy (1 - X)2 V 1 -X odkud konečně Cn = 2(n + l)(H„+i — 1) — 2n.