V Brně 8. dubna 2001 Diplomová práce Diferenční rovnice ve středoškolské matematice Aleš Kobza Prohlašuji, že jsem diplomovou práci vypracoval samostatně podle pokynů vedoucího diplomové práce a s použitím uvedené literatury. Děkuji vedoucímu diplomové práce, Doc. RNDr. Ondřeji Došlému, DrSc. za cenné rady a připomínky k tématu diplomové práce. Obsah 1 Úvod 2 2 Základy diferenčního počtu 7 2.1 Pojem a vlastnosti diference funkce................. 7 2.2 Diference některých elementárních posloupností.......... 10 2.3 Diference vyšších řádů........................ 12 2.4 Úlohy na procvičení......................... 14 3 Základy sumačního počtu 15 3.1 Pojem a vlastnosti sumace...................... 15 3.2 Sumace některých elementárních posloupností........... 17 3.3 Součet n členů posloupnosti..................... 21 3.4 Určité sumy.............................. 23 3.5 Sumace vyšších řádů......................... 25 3.6 Úlohy na procvičení......................... 27 4 Pojem diferenční rovnice 29 5 Pojem a vlastnosti lineární diferenční rovnice 33 6 Homogenní lineární diferenční rovnice s konstantními koeficienty 37 6.1 Charakteristická rovnice má k různých reálných kořenů...... 38 6.2 Charakteristická rovnice má imaginární kořeny.......... 39 6.3 Charakteristická rovnice má vícenásobný kořen.......... 40 6.4 Úlohy na procvičení......................... 41 7 Nehomogenní lineární diferenční rovnice s konstantními koeficienty 43 7.1 Metoda neurčitých koeficientů.................... 43 7.2 Metoda variace konstant....................... 45 7.3 Úlohy na procvičení......................... 49 8 Lineární diferenční rovnice 1. řádu s nekonstantními koeficienty 50 Literatura 53 1 1 Úvod V případě, že definiční obor funkce jsou ekvidistantní body, jak je tomu např. u posloupností, používá se k jejich vyšetřování diferencí (místo derivací) a sumací (místo integrálů). Diferenční rovnice jsou tedy obdobou diferenciálních rovnic pro funkce s diskrétním definičním oborem. Najdeme je v ekonomii, v počtu pravděpodobnosti, matematické statistice, fyzice, chemii a všude tam, kde je povaha problému taková, že vyžaduje řešení metodami diskrétního charakteru. i ve středoškolské matematice se setkáme s některými problémy, které je výhodné řešit pomocí diferenčních rovnic, a to především v kombinatorice a v učivu o posloupnostech. Některé diferenční rovnice totiž představují rekurentní vzorce pro posloupnosti u(n) nebo součty jejích členů s(n). Řešit tyto rovnice znamená najít vzorce pro u(n) (resp. s(n)) jako funkce n. Tuto práci je možné využít jako výukový text tématu „Diferenční rovnice" na gymnáziích s rozšířenou výukou matematiky. Vyložíme zde základy diferenčního a sumačního počtu nutné k tomu, abychom v dalším dokázali řešit jisté typy lineárních diferenčních rovnic, na něž se především zaměříme. K mechanickému řešení lineárních diferenčních rovnic přitom stačí středoškolské znalosti. Teoretický výklad je vždy doplněn řešenými příklady, navíc v závěru skoro každé kapitoly je větší počet úloh na procvičení včetně výsledků a případně i návodů k jejich řešení. Poznamenejme, že podobně jako pro diferenciální rovnice, tak i pro diferenční rovnice neexistuje obecná metoda řešení. Pro některé funkce platí jisté analogie mezi spojitým a diskrétním případem. Na některé z nich upozorníme i v této práci. Tyto poznámky však nejsou nutné pro pochopení ostatního textu, proto jsou psány menším písmem. Čtenář s hlubším zájmem o probíranou problematiku má v textu možnost najít odkazy na další literaturu. Dříve, než přistoupíme k samotnému výkladu, uveďme několik motivačních příkladů, které naznačí, jaké typy úloh zvládneme po prostudování této práce řešit. Příklad 1.1: Určete nej větší možný počet u(n) oblastí, na které lze rovinu rozdělit pomocí n přímek, které v ní leží. Řešení: Mějme v rovině n přímek Pi,P2, ■■■,Pn v obecné poloze, tj. n přímek takových, že žádné tři se neprotnou v jednom bodě (v termínech geometrie to znamená, že žádné tři přímky nepatří do tzv. svazku přímek 1.druhu - viz skripta [7]) a žádné dvě nejsou rovnoběžné (tedy žádné dvě z těchto přímek neurčují svazek přímek 2.druhu). Těmito přímkami je rovina rozdělena právě na u(n) oblastí. Přidejme přímku pn+i tak, aby všech n + 1 přímek opět bylo v obecné poloze, tzn. přímkapn+i je rozdělena průsečíky s přímkamipi,p2, ...,pn nan + 1 částí. Každá z těchto částí dělí jednu z původních oblastí roviny na dvě „nové". Přidáním přímky pn+i tedy počet částí roviny vzrostl o n + 1. Je zřejmé, že počet oblastí, na které je rovina rozdělena přímkami pi,p2, ...,pn+i je u(n + 1). Tímto jsme odvodili vztah u(n + 1) = u(n) + n + 1. Označíme-li u(n + 1) — u(n) = Au(n), pak Au(ri) = n + 1. (1.1) Z kapitoly 3 vyplyne, že u(n) lze předpokládat ve tvaru: u(n) = ar? + bn + c, kde a, b, c jsou konstanty, které musíme určit. Tedy Au(ri) = a(n + l)2 + b(n + 1) + c - (on2 + bn + c), 2 což po úpravě dá Ati(n) = 2an + a + b. (1.2) Pravé strany rovnic (1.1) a (1.2) se musí identicky rovnat n + 1 = 2an + a + b a konstanty a, b proto můžeme určit porovnáním koeficientů u stejných mocnin: n1 : 2a = 1 =>- a = -2 n° : a + b = l =^ h=\ Zbývá určit konstantu c. Zřejmě platí m(1) = 2, tedy u(l)=a + b + c =^ 2=2 + 2+C ^ C=1" Pro hledaný počet w(n) oblastí jsme odvodili vztah u(n) = i(n2 +n + 2). (1.3) Příklad 1.2: Určete hodnotu součtu 1 • 2 • 3 + 2 • 3 • 4 + ... + n{n + l)(n + 2) pro libovolné n € N. Řešení: Máme najít vzorec pro součet prvních n členů posloupnosti s{n) = m(1) + m(2) + ... + u{n), kde u(n) = n(n + l)(n + 2). V podkapitole 3.3 se dozvíme, že platí s(n) = u(n + 1). Naším úkolem je určit tzv. sumaci u(n + 1). Seznámíme se rovněž s pojmem zobecněná mocnina (viz Definice 2.18), pomocí níž tento výpočet snadno provedeme. Platí totiž s(n) = ^(n + l)(n + 2)(n + 3) = J](n + 3)(3) = i(„ + 3)W + c = = ^n(n+ l)(n + 2)(n + 3) + c. Konstantu c určíme z faktu, že s(l) = m(1), tj. Í-l-2-3-4 + c = l-2-3 =^ c = 0. 4 Vypočetli jsme 1 • 2 • 3 + 2 • 3 • 4 + ... + n(n + l)(n + 2) = ^n(n + l)(n + 2)(n + 3). (1.4) Právě vyřešený příklad lze nalézt např. ve sbírce [10], která je určena pro gymnázia, ovšem v zadání se mluví o důkazu vzorce (1.4). To lze samozřejmě provést matematickou indukcí, zvídavý student si však jistě položí otázku, jak lze vzorce podobné (1.4) odvodit. Odpovědna ni podává i tato práce. 3 Rovněž Příklad 1.1 lze najít ve středoškolské sbírce [9]. I ten je formulován jako důkaz vzorce (1.3) matematickou indukcí. Ve stejné knize je ale popsána metoda, jak lze u posloupnosti dané rekurentně najít vzorec pro n—tý člen (funkční vzorec). Postup je následující. Po vypsání několika prvních členů vyslovíme hypotézu, jejíž platnost potvrdíme matematickou indukcí. Tímto způsobem lze „uhodnout" funkční vzorce, které nejsou příliš komplikované a Příklad 1.1 bychom takto možná vyřešili. Již v následujícím příkladu by byl tento postup těžko proveditelný a oceníme v něm výhody diferenčního počtu. Příklad 1.3: Kolika způsoby můžete vyběhnout n schodů, děláte-li kroky o jeden nebo o dva schody (n € N)? Řešení: Označme v(n) počet způsobů pro n schodů. Uvažujme o vyběhnutí n + 2 schodů. Uděláme-li první krok o jeden schod, pak nám zbývá v(n + 1) způsobů pro další schody. Ve druhém případě, tj. uděláme-li první krok o dva schody, zbývá vyběhnout n schodů, což lze udělat v(n) způsoby. Tímto jsme odvodili rekurentní vztah v(n + 2) =v(n+l) + v(n), (1.5) přičemž zřejmě platí v(l) = 1, v{2) = 2. Podle terminologie zaváděné ve 4. a 5. kapitole je vlastně (1.5) homogenní lineární diferenční rovnice 2. řádu s konstantními koeficienty a danými počátečními podmínkami. Rovnici (1.5) nyní vyřešíme způsobem podrobně vyloženým v 6. kapitole. Její charakteristická rovnice A2 — A — 1 = 0 má kořeny Ai,2 = 1±2V^. Obecné řešení je proto tvaru v{n) = Ci —-— + C2 Konstanty c\, C2 určíme z počátečních podmínek 1 = Cll-±^ + c21--^ Rozřešíme-li tuto soustavu, dostaneme c\ = , C2 = 5 ^■ Vypočetli jsme v{n) = ^ô--[^) —xô— » —=— ■ • (L6) Posloupnost, se kterou jsme pracovali v Příkladu 1.3 se nazývá Fibonacciho posloupnost (Fibonacci, vlastním jménem Leonardo Pisánský (1170 - 1240), italský matematik). Všimněme si, že kdybychom postupně počítali její jednotlivé členy z rekurentního vzorce (1.5) při podmínkách v(l) = 1, v{2) = 2, dostali bychom přirozená čísla 1,2,3,5,8,13,21,... Proto i hodnotami vypočtenými ze vzorce (1.6) musí být pro libovolné n € N přirozená čísla, i když tvar (1.6) obsahuje zlomky a iracionální čísla. Poslední příklad, který v této kapitole uvedeme, je z oblasti počtu pravděpodobnosti. Příklad 1.4: (Hráčův problém) Hráč se účastní hry, v jejímž každém kole sází vždy stejnou částku (1$). S pravděpodobností p (0 < p < 1) přitom vyhraje dvojnásobek vsazené částky, v opačném případě sázku ztrácí. Hru končí, jestliže dosáhne stanovené výhry N$, nebo 4 prohraje-li výchozí částku M$ (0 < M < N). Vypočtěte, jaká je pravděpodobnost toho, že hráč prohraje výchozí částku M$. Řešení: Označme P(n) pravděpodobnost, že hráč prohraje částku n$. Pak zřejmě platí P(0) = 1 a P(N) = 0. Nechť 0 < n + 1 < JV. Ze stavu, kdy má hráč (n+l)$ se může dostat buď do stavu, kdy má (n + 2)$, a to s pravděpodobností p a nebo se s pravděpodobností 1—p dostane do stavu, kdy má n$. Tuto skutečnost vyjadřuje vzorec P(n + 1) =pP{n + 2) + {l-p)P{n), což je lineární diferenční rovnice 2. řádu, kterou můžeme přepsat do tvaru P(n + 2) - -P(n + 1) + —-P(n) = 0. (1.7) p p Tuto rovnici nyní vyřešíme způsobem podrobně vyloženým v 6. kapitole. Nejprve najděme kořeny charakteristické rovnice A2 — p-A + = 0 : 1 _|_ fl 4(l-p) , p± VF-^T^ 1 1 , 1± 2p-l 2p 2pv 2p Tedy Ai = 1 a A2 = —-. p Nyní musíme rozlišit dva případy. Charakteristická rovnice totiž má buď dvojnásobný kořen a nebo dva reálné různé kořeny. 1. Případ Ai = A2 = 1 nastane právě když p = |. Obecné řešení rovnice (1.7) je v tomto případě P(n) = Ci + C2n. Konstanty Cl, C2 určíme z podmínek P(0) = Ci = 1, P(JV) = Ci+C2iV = 0 c2 = -jj. Pro p = I jsme vypočetli 2. V případě, kdy Ai / A2, což nastane právě když p / |, je obecné řešení rovnice (1.7) tvaru P(n) = Ci + C2 \ p Podobným způsobem jako výše vypočteme konstanty Cl, C2. P(0) = Ci + c2 = 1, /l - \^ P(N) = Ci + C2 íJ = 0. Vyřešením této soustavy dostaneme Cl = ^ip^_piv a C2 = pn_^i_p^n ■ Tedy k> (i-p)n-pn pn-(i-p)n Po úpravě pro pý \ máme: 5 Pro konkrétnější představu vypočtěme hodnotu P(n) pro dva případy: 1. Je-li M = 20$, N = 40$ a, p = §, pak podle (1.8) vypočteme: P(20) = 0,5. 2. Je-li M = 20$, N = 40$ a p = || (což zachycuje reálnou situaci, sází-li hráč v ruletě s jednou nulou na červenou resp. černou barvu), pak podle (1.9) vypočteme: P(20) = 0,75. 6 2 Základy diferenčního počtu Než se budeme moci zabývat diferenčními rovnicemi, musíme se seznámit s pojmem „diference", což v překladu znamená „rozdíl". V následující podkapitole uvedeme definici diference funkce a ukážeme si její základní vlastnosti. 2.1 Pojem a vlastnosti diference funkce Definice 2.1: Nechť je dán bod xq a číslo h > 0. Nechť funkce y = f (x) je definována v bodech xo a xo + h. Číslo /(a;o + h) — f(xo) nazveme diference funkce f(x) v bodě xo. Píšeme A/(z0) = f(x0 + h)- f(x0) a čteme „delta /(a;o)". Číslu h říkáme diferenční krok, bodu xo počáteční bod diference. Pokud by nebylo jasné, jaký diferenční krok právě uvažujeme, případně pokud chceme zdůraznit jeho délku, pak diferenci označíme: A^/(a;o). Nechť h je pevně zvolený diferenční krok. Je-li f(x) definována v bodech xo a xo + h, můžeme v bodě xo vypočítat diferenci A/(a;o). Abychom však mohli určit diferenci v bodě xo + h, musí být funkce f(x) definována i v bodě xo + 2h. Toto podobně platí i pro každý další bod xo + nh, n € N definičního oboru. K tomu, abychom mohli určit diferenci funkce f(x) v bodech xo,xo + h,...,xo + nh, n € N, musí definiční obor Ai funkce f(x) obsahovat množinu {xo,xo + h,xo + nh, xo + (n + l)h}. Definice 2.2: Nechť funkce f(x) je definována ve všech bodech neprázdné množiny M. Funkci, která každému bodu x £ M s vlastností (x + h) £ M přiřazuje hodnotu A/(a;) nazýváme diferencí funkce f (x) a značíme Af(x) = f(x + h)-f(x), x€M. Příklad 2.3: Vypočítejte 1. A f (x) pro obecný diferenční krok h, 2. A/(l) pro h = 2, je-li f (x) = x3. Řešení: 1. A/(a;) = f {x + h)- f {x) = {x + h)3 - x3 = 3hx2 + 3h2x + h3, 2. A/(l) = 3 • 2 • l2 + 3 • 22 • 1 + 23 = 26. Všimněme si, že diferenci je možno použít i k definici pojmu derivace. Je totiž /»= Hm ^ÍW. ft->o+ h Příklad 2.4: Vypočtěte derivaci funkce f (x) = x3. Řešení: Z Příkladu 2.3 víme, že Ax3 = 3hx2 + 3h2x + h3. (x3)'= Um 3^2+3fr2* + fr3 = lim (3x2+3hx + h2)=3x2. ft->o+ h ft->o+ Poznámka 2.5: V úlohách na diference a diferenční rovnice bývá obvykle definiční obor diference neprázdná množina M - tzv. diskrétni množina ekvi-distantních bodů {xo + nh}, kde n = 0,1,2,..., počáteční bod diference xo a diferenční krok h jsou předem daná čísla. Označme: M = {x0,x0 + h, x0 + 2h,...}. 7 Poznámka 2.6: Nechť je dáno ři>0a nechť f (x) je libovolná funkce definovaná na množině Ai = {a;o,a;o + h,xo + 2h,...}. Proveďme lineární substituci x = xo + h(t — 1), kde t je nová proměnná. Označme g(t) = f(x) = f(xo + h(t — 1)), potom Afc/(a;) = f(x + h)-f(x)=f(x0 + h(t-l) + h)-f(x0 + h(t-l)) = = f{x0 + ht)-f{x0+h{t-l))=g{t+l)-g{t) = Al9{t). Touto substitucí jsme dostali diferenční krok 1. Substituce t = x~ix°~h) navíc nemění typ vyšetřované funkce (tj. např. polynom stupně k zůstane i po substituci polynomem stupně k). Pro x = xo bude t = 1, pro x = xo + nh bude t = 1 + n. Množina Ai se touto substitucí změní v množinu všech přirozených čísel N. Popsanou substitucí lze vždy docílit toho, že xq = 1 a h = 1, tzn. Ai = N. Definice 2.7: Funkce, jejímž definičním oborem je množina všech přirozených čísel N, se nazývá posloupnost. Je-li u : N —>■ R, bývá obvyklé místo u(n) psát un. Aby však v dalším nemohlo dojít k nedorozumění, kdy jde o index a kdy máme na mysli proměnnou, zůstaneme u označení u(n), jak je tomu např. i v knihách [2] a [3]. Příklad 2.8: Najděte posloupnost, která má stejnou diferenci jako funkce f(x) = 36a;2 + 120a; + 100 definovaná na množině M = {— |, — |, — |, |, |,...}. Řešení: Hledáme posloupnost g(n) takovou, aby platilo Aig(n) = A^/(a;). Podle Poznámky 2.6 víme, že požadovanou posloupnost nalezneme pomocí substituce x = xo + h(n — 1), tedy x = — | + \{n — 1) = f — Protože g(n) = f(x) = /(f - ^), dostáváme , N in 11\2 (n 11\ , 3(n)=36Í--— J +120Í - - — ) +100 = 9n2-6n+l. Hledaná posloupnost je tedy g{n) =9n2-6n + l. Poznamenejme, že v některé literatuře (např. v knize [1]) jsou diferenční rovnice uvažovány na obecné množině Ai (viz Poznámka 2.5). Výklad další problematiky se však zpřehlední i zjednoduší, učiníme-li následující úmluvu. Úmluva 2.9: Nebude-li řečeno jinak, v dalším se vždy budeme zabývat posloupnostmi, tzn. budeme předpokládat, že xq = 1 a h = 1, tedy Ai = N, což lze podle Poznámky 2.6 předpokládat bez újmy na obecnosti. Obdobným způsobem, jakým jsme přešli od funkce k poslopnosti, můžeme přejít od posloupnosti k funkci s libovolným definičním oborem Ai ve smyslu Poznámky 2.5. Proto všechny věty, které uvedeme v dalším pro posloupnosti, platí rovněž pro zmíněné funkce s definičním oborem Ai. Věta 2.10: Pro všechna n, pro něž jsou současně definovány posloupnosti Au(n), Av(n) platí: 1. A[u(n) ± v(n)] = Au(n) ± Av(n) 2. A[c ■ u(n)] = cAií(n), kde c € R je libovolná konstanta 3. A[u(n)v(n)] = v(n)Au(n) + u(n + 1)Av(n) = u(n)Av(n) + v(n + l)Ait(n) 8 a Aľw(n)i v(n)Au(n) — u(n)Av(n) • v / \ / ■ -i \ / n 4- A[^f] = ^(nMn+l) > Je"h «(")«(" + 1) ŕ O Důkaz: 1. A[u(n) ±u(n)] = [íí(n+l)±u(n + l)]-[íí(n)±u(n)] = [u{n + l)-u{n)]± [v(n + 1) - u(n)] = Au(ri) ± Au(n) 2. A[c • u(n)] = cw(n + 1) — cu(n) = c[u(n + 1) — u(n)] = cAw(n) 3. A[u(n)u(n)] = u(n+l)v(n+l)—u(n)v(n) = u(n+l)v(n+l)—u(n+l)v(n) + v(n)u(n + l)—u(n)v(n) = v(n)[u(n + l)—u(n)]+u(n+l)[v(n + l) — v(n)] = v(n)Au(n) + u(n + l)Av(n) Podobně bychom dokázali druhou rovnost. 4. Nechť v{n)v{n + 1) / 0 ^lu(n) 1 _ u(n+l) _ u(n) _ v(n)u(n+l)—u(n)v(n+l) _ <-v(n) -I v(n-\-l) v(n) v(n)v(n-\-l) _ v(n)u(n+l)— v(n)u(n)— u(n)v(n+l)+u(n)v(n) _ v(n)v(n+l) _ v(n)\u(n+l) — u(n)]—u(n)\v(n+l)— v(n)] _ v(n)Au(n) — u(n)Av(n) v(n)v(n+l) v(n)v(n+l) Obdobné vlastnosti, které jsme uvedli ve Větě 2.10 platí i pro počítání s derivacemi. Za povšimnutí stojí tzv. posuny (viz vlastnost 3. a 4.), které se ve spojitém případě neobjevují. Tyto posuny rovněž způsobují jisté odlišnosti mezi diskrétním a spojitým případem. Ale pozor: v diferenciálním poctu platí vzorec pro derivaci složené funkce [f(g(x))]' =f(g(x))-g'(x), v diferenčním počtu však žádná analogie k tomuto vzorci neexistuje! V dalším textu vyslovíme věty, které jsou opět diskrétními analogiemi známých vět z diferenciálního počtu. Pro tuto práci však zmíněné věty nejsou stěžejními, proto je zde nebudeme dokazovat. Zájemce o hlubší proniknutí do nastíněné problematiky odkážeme např. na knihu [2]. Čtenář seznámený s diferenciálním počtem se případně může pokusit o samostatný důkaz těchto tvrzení. Nejprve stručně vysvětlíme některé pojmy, které budou použity: • Budeme používat následující označení: N(a) = {a, a + 1,...}; N(a,6) = {a, a + 1, ...,6}, kde a<6 Pm - 1. Věta 2.12: (Diskrétní Lagrangeova věta) Nechť posloupnost u(n) je definována na N(a, 6). Pak existuje »o G N(a + 1,6 — 1) takové, že . , \ __ "(6) — u(a)____. / \ , A , . . «(6) — «(a) . _ , . Aii(u0) < -i-i-i-i < Vm(ho) nebo Au(n0) > -i-i > Vu(n0), b — a b — a kde Vu(no) := «(»o) — «(»o — !)■ Věta 2.13: (Diskrétní VHospitalovo pravidlo) Nechť u(n),v(n) jsou definovány na N(a). Dále nechť v(n) > 0, Av(n) < 0 a limn-xxj u(n) = limn-joo v(n) = 0 (resp. v(n) > 0,Av(n) > 0 a limn-joo v(n) = oo). Potom platí: jestliže existuje limita limn-xxj ^"(n) > P3^ existuje i limita limn-xxj a obě limity jsou si rovny. Příklad 2.14: Vypočtěte: Hmn_nx, n'\n Řešení: Nejprve bude vhodné provést úpravu: n-2"+1 In km - = hm ——r-^-. n—>oo 3n n—>oo 9 Snadno se přesvědčíme, že jsou splněny předpoklady Věty 2.13 a k výpočtu tedy lze použít 1'Hospitalovo pravidlo 2n 2(n + l)-2n 2 lim -;—r-=- = lim-- = lim -;—r-=- = 0. Čtenář si jistě všiml, že podmínky Věty 2.13 byly splněny již u zadané limity. Kdybychom ovšem použili 1'Hospitalovo pravidlo už na tomto místě, dostali bychom však opět výraz typu "oo ■ Pro výpočet této limity je rovněž možno použít 1'Hospitalovo pravidlo známé z diferenciálního počtu (což po formální stránce znamená nahradit diference derivacemi). Čtenáři obeznámenému s touto problematikou doporučujeme provést příslušný výpočet, čímž si ověří, že výsledek vyjde v obou případech stejně. 2.2 Diference některých elementárních posloupností Nyní si odvodíme vzorce pro diference nejběžnějších posloupností, které se nám budou hodit pro praktické počítání. Dohodněme se ještě, že polynom stupně k nad přirozenými čísly budeme značit k Pk(n) = oo + 01 n + ... + aknk = y^Ojn3, j=o kde 0& ý 0- Nenulovou konstantu přitom budeme chápat jako polynom nultého stupně (Po(n) = oo,oo / 0). Věta 2.15: Pro všechna n € N platí: 1. Ac = 0, kde c € R je libovolná konstanta 2. Ank = Pfc_i(n), kde k € N a Pu-i(n) je jistý polynom stupně k — l 3. Aqn = qn(q - 1), kde q € R 4. A sinán = (cos a — 1) sinán + sin a cos an, kde a € R je libovolná konstanta 5. A cos an = (cos a — 1) cos an — sin a sinán, kde a € R je libovolná konstanta Důkaz: 1. Ac = c-c = 0 2. An* = (n + l)k - nk = nk + (í)n*"1 + g)"*"2 + ... + (^Jn + 1 - nk = = fcn*"1 + \k(k - l)nk~2 + ... + kn+l = Pk-i{n) 3. Aqn = qn+1 - qn =qn(q- 1) 4. A sinán = sin(an + a) — sinán = sinán cos a + cos an sin a — sinán = (cos a — 1) sin an + sin a cos an 5. A cos an = cos(an + a) — cos an = cos an cos a — sin an sin a — cos an = (cos a — 1) cos an — sin a sin an Důsledek 2.16: Pro všechna n € N platí: 1. AP&(n) = Qk-i(n), kde Qk-i{n) je jistý polynom stupně k — 1 2. pro q € R - {1} je A[Pk(n)qn] = Qk{n)qn, kde Qk{n) je jistý polynom stupně k 10 Důkaz: 1. APk{n) = A£*=0a,-nJ'. Podle Vět 2.10.1 a 2.10.2 platí: AEj=o°jnJ = 2j=o QjAni = Sj=o aóRj-Án) (V1Z Věta 2.15.2). Protože výsledný koeficient u mocniny nft_1 je nenulový, platí:^*L0 ajRj-i(n) = Qk-i(n). 2. Podle Věty 2.10.3 platí: A[Pk(n)qn] = qnAPk(n) + Pk(n + l)Aqn = qnRk-i (n) + £*=0 a, (n + l)jqn(q - 1) (viz Důsledek 2.16.1 a Věta 2.15.3). Tedy A[Pk(n)qn] = 9"[ižft_i(n) + (q - 1) £kj=0 aj{n + 1)']. Koeficient u nejvyšší mocniny n, tj. nk, je ak(q — 1) a ten je nenulový, neboť podle předpokladu q / 1. Výraz v závorce je tudíž jistý polynom stupně n a důkaz je tím hotov. Podobných vzorců jako v Důsledku 2.16 bychom mohli uvést více, ale nebylo by to účelné. Vypočtěme raději příklad, který nás přesvědčí, že patřičné výpočty můžeme provádět i bez znalosti zmíněných vzorců. Příklad 2.17: Vypočtěte diferenci posloupnosti u(n) = 2(n2 + 1) cos |n. Řešení: Nejprve využijeme vztahu pro diferenci součinu, dále pak vlastností uvedených ve Větě 2.15. Ati(n) = A |2(n2 + l)cos ^nl = 2 • A (n2 + l) cos + + 2[(n + l)2 + l] A cos = 2 [(n + l)2 + 1 - (n2 + 1)] cos + ó ó „ r 2 „ „-i IV 7T . 7T 1 + 2 [n + 2n + 2J I cos — — 11 cos — n — sin — sin — n = l \ o / ó ó o-l -i \ i" „ / 9 „ „n/1 7T VŠ . 7T \ = 2 (2n + 1) cos -n + 2 (n2 + 2n + 2) --cos -n - ^— sin -n = ó \ Z Ó JĹI ó l = [4n + 2 - (n2 + 2n + 2)] cos - y/Š (n2 + 2n + 2) sin = ó ó = - (n2 - 2n) cos - VŠ (n2 + 2n + 2) sin ^n. ó ó V diferenčním počtu je někdy vhodné pracovat s tzv. zobecněnými mocninami, se kterými se nyní seznámíme. Definice 2.18: Nechť n, k € N. Zobecněnou mocninu značíme n^' a definujeme vzorcem = n(n — l)...(n — k + 1). Pokud čtenář zná základy diferenciálního počtu, ví, že pro derivaci mocniny platí (z*) = kxk~1. Vidíme, že tento vzorec a vzorec pro diferenci mocniny nk uvedený ve Větě 2.15.2 se sobě příliš nepodobají. Ukážeme, že právě diference zobecněné mocniny je analogií k derivaci mocniny. Věta 2.19: Nechť n, k € N. Pak pro diferenci zobecněné mocniny platí: An« = kn^~1\ Důkaz: Ant*' = (n + 1)W - n^' = (n + l)n(n - l)...(n -k + 2)--n{n-l)...{n-k + 2)(n-k+l) = [{n +1) - (n- k + l)]n(n - l)...(n- k + 2) = = fcn(ft-1'. Výhodu zobecněných mocnin doceníme hned v následující podkapitole, kdy uvedeme příklad, ve kterém nám jejich znalost výrazně usnadní výpočet. 11 2.3 Diference vyšších řádů Nechť u(n) a v(n) jsou posloupnosti, pro něž platí Ati(n) = v(n). Počítejme Av(n) = A[Aw(n)] = A[u(n + 1) - u(n)] = Au(n + 1) - Ati(n) = = u(n + 2) - u(n + 1) - [u(n + 1) - w(n)] = w(n + 2) - 2u(n + 1) + w(n). Posloupnost Ad(ti) = A[Aw(n)] nazveme druhou diferencí posloupnosti u(n) a označíme A2u(n). Ihned vidíme, že k tomu, abychom mohli určit hodnotu druhé diference posloupnosti u(n) v bodě no € N, musíme znát její hodnoty v bodech n0,n0 + l,n0 + 2. Podobně můžeme uvažovat dále, což nás vede k vyslovení rekurentní definice k—té diference. Definice 2.20: Nechť n, k £ N a u(n) je posloupnost. Položme A°u(n) = u(n), A1w(n) = Ati(n). Potom k-tou diferenci posloupnosti u(n) značíme Aku(n) a definujeme ji rekurentně vzorcem Aku(n) = AfA*"1^)]. Pro k = 1 místo první diference říkáme jen diference. Pro k > 1 kromě termínu k—tá diference říkáme též diference k—tého řádu nebo souhrnně hovoříme o diferencích vyšších řádů. Nechť u(n) je posloupnost. Její k— tá diference je opět posloupností. Jestliže do této posloupnosti dosadíme za n dané přirozené číslo no, dostaneme „k—tou diferenci posloupnosti u(n) v bodě no", což je určitá hodnota této posloupnosti (určité číslo). V tomto případě budeme psát Aku(no)- Věta 2.21: Nechť n, k £ N a u(n) je posloupnost. Pak Aku(n) = u(n + k) - (^ju(n + k - 1) + (^ju(n + k - 2) - - ••• +(-!)*«(«) = E(-1)*"JÍ-) + 3=0 ^Jj/ Důkaz: Provedeme úplnou matematickou indukcí: 1. k = l: A^n) = u(n + 1) + (-l)1w(n) = u(n + 1) - w(n) = Au(n), tedy pro & = 1 vzorec platí. 2. Předpokládejme, že vzorec platí pro jisté k a dokažme jeho platnost i pro k + 1 : A*+1M(n) = A[A*M(n)] = [u(n + k + l) - (§u(n+k) + (§u(n + k-1) -...+ +(-iy (k)u(n + k + l-j) + ...+ (-l)*u(n + 1)] - [u(n + k)--(k)u(n + k - 1) +... + (-iy (k)u(n + k-j) +... + (-I)*"1 +1)+ +(-l)*u(n)] = u(n + k + 1) - [(*) + l]u(n + *) + [(*) + (*)]u(n + k - 1)- + (-l)i [(*) + + & + 1 - j) + ... + (-1)* [1 + (kk_Mn + 1) + +(-l)*+1m(n). Použitím identit (*) = 1 = (*) a (*) + ( *J = C**1) dostaneme A*+1M(n) = u(n + k + 1) - (^ufii + *) + (^ufa + * - 1) + •••+ +(-1)í (*+>(n + k + 1 - i) + ... + (-l)k {kf)u{n + 1) + (-l)*+1u(n), což jsme měli dokázat. 12 Příklad 2.22: Nalezněte čtvrtou diferenci posloupnosti u(n) =e°a čtvrtou diferenci této posloupnosti v bodě no = 2. Řešení: Využijeme Větu 2.21: A4u(n) = A V = e"+4 - Q) e"+3 + Q e"+2 - Q e"+1 + e" = = en(e4 -4e3 + 6e2 -4e + l). Dosazením no = 2 dostáváme: A4w(n0) = e2(e4 - 4e3 + 6e2 - 4e + 1). Příklad 2.23: Vypočítejte třetí diferenci polynomu u(n) = n5 — 6n4 + lln3 — 4n2 - 3. Řešení: I v tomto případě lze použít Větu 2.21: A3w(n) = A3 (n5 - 6n4 + lln3 - 4n2 - 3) = = (n + 3)5 - 6 (n + 3)4 + 11 (n + 3)3 - 4 (n + 3)2 - 3 - - Q [(n + 2)5 - 6(n + 2)4 + ll(n + 2)3 - 4(n + 2)2 - 3] + + Q) [(n + l)5 - 6(n + l)4 + ll(n + l)3 - 4(n + l)2 - 3] - - (n5-6n4 + lln3-4n2-3) = ••• Vidíme, že pokračování ve výpočtu elementárními algebraickými úpravami by bylo relativně pracné. Postupujme proto rekurentně přímo podle Definice 2.20. Zapišme zadaný polynom pomocí zobecněných mocnin. To provedeme postupným dělením n, (n — 1),(n — 4), což pomocí Hornerova schématu zapisujeme následujícím způsobem: 1 -6 11 -4 0 -3 1 1 -5 6 2 2 2 1 -3 0 2 3 1 0 0 4 1 4 Tedy: u(n) = n5 - 6n4 + lln3 - 4n2 - 3 = n^ + 4n^ + 2n^ + 2n - 3. Podle Vět 2.10.1, 2.10.2 a 2.19 platí: Au(ri) = A (n(5) + 4n(4) + 2n(2) + 2n - 3) = 5n(4) + 16n(3) + 4n + 2, A2w(n) = A [Au(ri)] = A (ôn^ + 16n<3) + 4n + 2) = 20n<3) + 48n<2) + 4, A3w(n) = A [A2w(n)] = A (20n^ + 48n<2) + 4j = QOn^ + 96n = = 60n(n - 1) + 96n = 60n2 + 36n. Vypočetli jsme: A3(n5 - 6n4 + lln3 - 4n2 - 3) = 60n2 + 36n. Věta 2.24: Pro j = 1,2,k je AjPk{n) = Qk-j{n), 13 kde Qk-j(n) je jistý polynom stupně k — j. Speciálně: AkPk(n) = c^O, kde c je jistá konstanta a tudíž Ak+1Pk{n) = 0. Důkaz: Zřejmé, plyne z Důsledku 2.16.1. 2.4 Úlohy na procvičení Úloha 2.25: Vypočtěte Au(n) a Aw(no), je-li: 1. u{n) = ^, n0 = 2 2. u(n) = sin Jn, no = 5 [Au(ri) = - | sin f n + ^ cos f n, Am(5) = ^] Úloha 2.26: Spočtěte Au(n), je-li: 2" 1. u(n) - 2 2. u(n) = 3" cos f n 3. u(n) = (3n2 - 2n - 4)2" 4. it(n) = (£), kde k € N Úloha 2.27: Vypočtěte Aku{n), je-li: 1. u(n) = n2 • 3™, fc = 3 2. u(n) = n5 - 4n4 + 2n3 - n2 + 3n + 1, = 4 [ 2"(ra2-2ra-2) ] |_(n-l)n(n+l)(n+2)J [§ • 3"(cos f n - 3^3 sin f n)] [(3n2 + 10n-2)2"] [8(n2 + 9n + 18)3"] [120n+ 144] Úloha 2.28: Najděte posloupnost, která má stejnou diferenci jako funkce f(x) definovaná na množině M = {xo, xo + h,xo + 2h,...}, je-li: 1. f{x) = 36a;2 + 15a; + 1, x0 = \, h = \ [g{n) = 4n2 + 3n] 2. /(a;) = 64a;3 + 144a;2 + 108a;+ 30, x0 = = £ [ff(n) = n3 + 3] Úloha 2.29: Určete přímo z definice derivace f'(x), je-li: 1. f{x) = x2 [2x] 14 3 Základy sumačního počtu Doposud jsme znali posloupnost a počítali jsme její diferenci, nyní stojíme před úlohou opačnou. Budeme znát diferenci a budeme hledat posloupnost, kterou jsme diferencovali. Hledanou posloupnost nazveme sumací dané posloupnosti a budeme se zabývat jejími vlastnostmi. Tak jako v předešlé kapitole jsme si všímali některých analogií mezi diferenčním a diferenciálním počtem, rovněž v této kapitole poukážeme na podobu mezi sumačním a integrálním počtem. 3.1 Pojem a vlastnosti sumace Definice 3.1: Nechť u(n) a U(n) jsou posloupnosti takové, že pro všechna n € N platí AU {n) = u(n). Posloupnost U(n) nazýváme sumací posloupnosti u(n) a značíme [7(n) = J>(n). Věta 3.2: Nechť u(n) je posloupnost. Pak platí: Au(fi) = 0 u(n) = c, kde c € R je libovolná konstanta. Důkaz: „<^" Platí podle Věty 2.15.1. „=^" Ati(n) = 0 =^ u(n + 1) - u(n) = 0 =^ pro Vn € N platí u(n) = u(n + 1). Tuto vlastnost má libovolná konstanta. Věta 3.3: Nechť u(n) a v(n) jsou posloupnosti. Potom Au(n) = Av(n) pro Vn € N u(n) = v(n) + c, kde c € R je libovolná konstanta. Neboli, u(n) a v(n) jsou sumacemi téže posloupnosti právě tehdy, když se liší o aditivní konstantu. Důkaz: „-$=" u(n) = v(n) + c =^ Au(n) = A[v(n) + c] = Av(n) + Ac = Av(n). „=^" Ati(n) = Av(n) =^ Ati(n) - Av(n) = 0 =^ A[u(n) - v(n)] = 0, což podle Věty 3.2 znamená, že u(n) — v(n) = c, tedy u(n) = v(n) + c. Poznámka 3.4: Z Věty 3.3 vyplývá, že je-li U(n) sumací u(n), pak existuje nekonečně mnoho posloupností y(n), které jsou sumacemi u(n) a každou z nich lze vyjádřit ve tvaru y(n) = ^2 m(n) =U{n)+ c, kde c je vhodná konstanta. Je-li navíc dána dvojice {no,y(no)} (tzv.počáteční podmínka), pak je konstanta c (a tím i sumace y(n)) určena jednoznačně. Podobně jako pojem sumace se v integrálním počtu definuje tzv. primitivní funkce, která má rovněž vlastnosti podobné těm, které byly popsány ve Větě 3.3. Příklad 3.5: Rozhodněte, zda posloupnosti U(n) = — | cos J n a V(n) = sin2 -|n jsou sumacemi téže posloupnosti. Řešení: 1. způsob: Postupujme podle Definice 3.1, tzn. hledejme posloupnosti u(n) a v(n), jejichž sumacemi jsou U(n) a V(n) : 15 u(n) cos ■ 1 7T - cos — n 2 3 11 cos —n / ó /7T 7T\ Sl3n+3Í 7T 7T "I in — sin — n = 3 3 J cos 1 7T „ i cos —n 2 l 2 3 — sin — n 2 3 1 7T VŠ~ _ 7T - cos — n H—— sin — n, 4 3 4 3 / \ att/ \ a . 2 . 2 /'7r ^ . 2 t1" u(n) = AK(n) = Asin —n = sin ^—n + — J — sin —n = / . 7T 7T 7T . 7T\ 2 .271" = sin—n cos—h cos —n sin— —sin — n = V 6 6 6 6/ 6 y/3 7T 1 7T \ 2 7T — sin — n + - cos — n — sin — n = 2 6 2 6 y 6 3 . o TT .71" 7T 1 9 7T . 2 )T = - sin — n H--sin — n cos — n + — cos — n — sin — n = 4626646 6 1 ( 2 • 2 7T \ = - cos — n — sin — n 4 V 6 6 / 1 7T VŠ . 7T = - cos — n H—— sin — n. 4 3 4 3 H—— • 2 sin — n cos —n = 4 6 6 Vypočetli jsme, že posloupnosti U(n) a V(n) jsou sumacemi téže posloupnosti a to: , 1 7T VŠ . 7T w(nj = u(nj = - cos — n H—— sin — n. *k ó *k ó 2. způsob: Využijme Větu 3.3, tzn. počítejme rozdíl U(n) — V(n) : jjí \ -tri \ 1 7T . 2 7T 1 / 2 7T . 2 7T \ . 2 7T U(n) — V(n) = — -cos— n — sin — n=— — cos —n — sin —n — sin — n = ^ ' ^ ' 23 6 2 l 6 6/ 6 1 A • 2 *" \ I.271" 1 = —^ 1 —sin — n — -sin — n = — -. 2 V 6/2 6 2 Zjistili jsme, že posloupnosti U(n) a V(n) se liší o konstantu, což znamená, že jsou sumacemi téže posloupnosti. Tento výpočet je sice kratší, nenalezli jsme však posloupnost, jejímiž sumacemi jsou U(n) a V(n). Věta 3.6: Nechť u(n),v(n) jsou posloupnosti. Pak platí: 1. ENn) ± v(n)] = E u(n)± E 2. EtCM(n)] = cEM(n)> kde c € R je libovolná konstanta 3. EtM(n) Au(n)] = w(n)t;(n) — E[u(n + 1) Au(n)] /tzv. sumace per partes/ Důkaz: Označme ^w(n) = Í7(n) tj. u{n) = AU{n), ^u(n) = F(n) tj. u(n) = AV(n). 1. Potřebujeme dokázat, že ^[M(n)±t;(n)] = Z7(n)±F(n), tj., že w(n)±t;(n) = A[[/(n) ± F(n)]. To ovšem platí podle Věty 2.10.1. 2. Potřebujeme dokázat, že EtCM(n)] = cU(n), tj., že cu(n) = A[cU(n)]. To však platí podle Věty 2.10.2. 16 3. Podle Věty 2.10.3 platí: A[u{n)v{n)] = u(n)Av(n) + v(n + l)Au(n). Proveďme sumaci a s využitím části 1 této Věty upravme: ^2 A[u(n)v(n)] = y^[u(n) Av(n) + v(n + l)Aw(n)] u(n)v(n) = y^[u(n)Av(n)] + y^[v(n + l)Au(n)] ^[tí(n)A«(n)] = u(íi)!)(fi) - ^[»(n + l)Ati(n)] 3.2 Sumace některých elementárních posloupností Věta 3.7: Nechť je dán polynom P&(n) = Sj=o aini■ Potom existuje polynom Qk+i{n) takový, že AQk+1(n) = Pk{n), tj- ^Pjt(n) = Qk+1{n). Důkaz: Hledejme koeficienty bj polynomu Qk+i{n) = SjÍo bjTii, kde má být bk+i ŕ 0 : k+i k+i k+i AQk+1(n) = W» + 1)' " E bin* = E * + l)j " "']• 3=0 3=0 3=0 Podle binomické věty platí: ft+i AQk+1(n) = E&J 3=0 Vidíme, že se „zruší" mocniny jý a také „vypadne" bo, tedy: (o»-+(o»-+-+e>»]. Polynom AQk+i{n) se má identicky rovnat danému polynomu Pk(n). Hledané hodnoty b j určíme porovnáním koeficientů u jednotlivých mocnin nJ, kde j = 0,1,...,*: nk : ^ft+i = Q>ki odtud vypočteme bk+i- nk~1 : ^t~^1)bk+i + (i)bk = Oft-i, odtud vypočteme bk, atd. n° : bk+i + bk + ■■■ + bi = oo, odtud vypočteme b\ Snadno nahlédneme, že hodnoty bk+i, bk, &i jsou určeny jednoznačně. Navíc bk+i ý 0, neboť a& / 0 (Pk(n) je polynom k—tého stupně), což jsme měli dokázat. Polynom Qk+i(n) je tedy skutečně (k + 1)—tého stupně. Číslo bo je však libovolné, protože se nevyskytuje v žádné rovnici. To nás ale nepřekvapuje, protože podle Poznámky 3.4 víme, že hledaných polynomů Qk+i{n) = S-^(n) existuje nekonečně mnoho a vzájemně se liší o aditivní konstantu, tj. o absolutní člen bo- Tímto je věta dokázána. Dodejme ještě, že právě dokončený důkaz je konstruktivní, tzn. při řešení konkrétních úloh postupujeme popsaným způsobem - tzv. metodou neurčitých koeficientů. Čtenář už jistě tuší, že nyní se jako o analogii integrálu mocniny zmíníme o sumaci zobecněné mocniny. AQk+i{n) = ^2,bj 17 Věta 3.8: Nechť n, k € N. Pak pro sumaci zobecněné mocniny platí: EnW = _l_n(*+i)+C) kde c € R je libovolná konstanta. Důkaz: Af-L-n^1) + c] = -^-A^+i) + Ac = ^(jfc + l)nW = n<*). Analogicky ke vzorcům pro diference platí vzorce pro sumace. Věta 3.9: Nechť c, c* € R jsou libovolné konstanty. Pak pro všechna n € N platí: 1. X> = cn + c* 2- E<7" = ^r<7n + c, kde(l)(n). Nechť a € N, b € N, a < b. Pak platí: b J2u(n) = [U(n)]ba+1=U(b + l)-U(a). n=a Důkaz: U{n) = £ u{n), tj. AU{n) = U{n + 1) - U{n) = u{n). Proto: U(a + 1) - U(a) = u(a), U(a + 2) - U(a + 1) = u(a + l), U{b)-U{b-1) = u{b-l), U{b + 1)-U{b) = u{b). Součtem těchto rovností dostaneme: U(b + 1) - U(a) = u(a) + u(a + 1) + ... + u(b - 1) + u{b), což jsme měli dokázat. Následující věta ukazuje, že určitá suma má tytéž vlastnosti, jaké jsme uvedli pro sumaci ve Větě 3.6. Věta 3.19: Nechť u(n) a v(n) jsou posloupnosti. Nechť o, b £ N, a < b. Pak platí: !• E!U kde c € R je libovolná konstanta 3- Ebn=a[u(n)Av(n)} = [u(n)v(n)}ba+1 - EÍU>(" + /tzv. sumace per partes pro určité sumy/ Důkaz: L EÍUXn) ± = ± +M(°+1)± v(a+ ••• + u(b) ± v(b) = = u{a) + u{a + 1) + ... + u{b) ± [v{a) + v{a + 1) + ... + v{b)] = T,bn=a u{n)± ±Y?n=av{n) 2- Hbn=a[cu(n)] = cu{á)+cu{a+l) + ...+cu{b) = c[u{a)+u{a+l) + ...+u{b)] = = cHbn=aU(n) 3. Podle Věty 2.10.3 lze psát: X)[u(n) Av(n) + v(n + 1) Aw(n)] = u{n)v{n). Podle Věty 3.18 platí: Yýn=a[u(n)Av(n) + v(n+ l)Aw(n)] = [u(n)v(n)]ba+1. Rovnost upravme s využitím části 1 této věty: EL>(")M")] = Wn)v(n)]b+^ - SÚM" + l)Au(n)]. Tímto je věta dokázána. 24 Příklad 3.20: Vypočtěte jýn=a[nqn], kde a, b € N, a < b a q / 1. Řešení: Postupujme podle Věty 3.19.3: u(n) = n Av(n) = qn Au(n) = l v(n) = ^qn, v(n + 1) = ^qn+1 Em Tedy: n n 6+1 6 r n+11 n-r 9-lJ„ ^Lí-iJ _[(& + 1)^+1 _a(řa] (9-1) (9-1) L(,6+1 3.5 Sumace vyšších řádů 6+1 aq (9-1 Známe-li k—tou diferenci a hledáme posloupnost, kterou jsme diferencovali, potřebujeme zavést pojem k— té sumace. Definice 3.21: Nechť n, k £ N a u(n) je posloupnost. Položme £(°Mn) = «(n), = £«(*)• Potom fc-íow sumaci posloupnosti u(n) značíme M(n) a definujeme rekurentně vzorcem X)w«(n) = E[E('"1)«H- Pro & = 1 místo první sumace říkáme jen sumace. Pro k > 1 kromě termínu ft—tá sumace říkáme též sumace k—tého řádu. Čtenář si jistě všiml, že definice k—té sumace je naprosto analogická definici k—té diference. Výpočet k—té sumace provádíme rekurentně podle Definice 3.21, tj. analogicky jako výpočet k— té diference, pokud postupujeme podle Definice 2.20 (viz Příklad 2.23). Příklad 3.22: Nalezněte alespoň jednu posloupnost y(n), která je třetí sumací posloupnosti u(n) = 3™. Řešení: Využijme Větu 3.9.2, kde stačí zvolit c = 0 : E«(") = Er = 5-r' E(2M") = £[£«(»)]=£ E(3M") = E[E(2)«H=E Zadání vyhovuje např. posloupnost: 1 qn 2 'ó _ 1 \ ^ qn _ 1 qn 3" = -V3" = - - 3". y(n) = --3n. 25 Podle Poznámky 3.4 víme, že sumace E u(n) není určena jednoznačně, ale že těchto posloupností je nekonečně mnoho. Je tedy zřejmé, že nekonečně mnoho je i posloupností, které jsou k—tou sumací posloupnosti u(n). Hledejme tedy obecný vzorec, který by nám umožňoval nalézt všechny posloupnosti y(n), pro které platí Nejprve ale zformulujme a dokažme následující větu. Věta 3.23: Nechť n, k £ N a u(n) je posloupnost. Pak platí: Aku{n) = 0 & u{n) = ck-1nk~1 + ck-2nk~2 + ... + c0, kde c, € R pro i = 0, l,...,k — 1 jsou libovolné konstanty. Důkaz: „=^" Důkaz této implikace provedeme postupnými sumacemi, přičemž využijeme Věty 3.2 a 3.7. Nechť Aku{n) = 0, pak A*-1^) = J> = coi, Ak-2u(n) = J](2)0 = ^coi =ci2n + c02, Ak-iu(n) = U)° = Efe-^-^'"2 + ^-3J-i"J"3 + - + coj-i) = = Cj-ijU-'-1 + Cj-2,jTl:'~2 + ... + Coj, u(n) = J2{k)° = J2(Ck-2'k-ink~2+Ck~3'k-ink~z+ ---+c°'k-1)= = ck-i}knk~1 + ck-2,knk~2 + ... + cok. V prvním řádku je konstanta coi podle Věty 3.2 libovolná. Ve druhém řádku je podle Věty 3.9.1 konstanta C02 libovolná a konstanta C12 se rovná konstantě coi, která je ovšem libovolná, takže i konstanta C12 nabývá libovolné hodnoty. Takto lze postupně s využitím Věty 3.7 zdůvodnit, že všechny konstanty v posledním řádku jsou libovolné. „■$=" Nechť u(n) = ck-ink~1 +ck-2nk~2 + ...+c0, kde Cj € R pro i = 0,1,k — l jsou libovolné konstanty. Posloupnost u(n) je v tomto případě polynomem a to nejvýše stupně k — 1. Proto tvrzení platí podle Věty 2.24. Věta 3.24: Nechť n, k £ N a nechť u(n) a v(n) jsou posloupnosti. Pak Aku(n) = Akv(n) pro Vn € N & u(n) = v(n) +ck-1nk~1 +ck-2nk~2 +... + c0, kde c, € R pro i = 0,1,k — 1 jsou libovolné konstanty. Neboli, u(n) a v(n) jsou k—tými sumacemi téže posloupnosti právě tehdy, když se liší o polynom nejvýše stupně k — 1. Důkaz: Nejprve s využitím Vět 2.21 a 3.19.1 ukažme platnost vzorce, kterého využijeme při důkazu obou implikací. Pro libovolné posloupnosti u(n) a v(n) platí: Aku(n) ± Akv(n) = E^„(-l)*"' J) ± E^„(-l)*"' j) = = E-=o(-l)"-J (•) [«(" + Í) ± v{n + j)} = Ak[«(„) ± v(n)}. Aku{n)-Akv{n) = 0 =^ Ak[u{n)-v{n)] = 0 =^ u{n) = v{n) +ck-1nk~1 + 26 ck-2nk-2 + ... + c0 (viz Věta 3.23). „<=" Nechť u(n) = v(n) + cj-in'-1 + cu-2nk~2 + ... + co- Označme pro zjednodušení zápisu w(n) = Ck-ink~1 + cu-2nk~2 + ■■■ + co- Pak Aku(n) = Ak[v(n) + w{n)] = Akv{n) + Akw{n). Ale Akw{n) = 0 (viz Věta 3.23), tedy Aku{n) = Akv(n). Poznámka 3.25: Z Věty 3.24 vyplývá, že je-li U (n) k—tou sumací u(n), pak existuje nekonečně mnoho posloupností y(n), které jsou k— tými sumacemi u(n) a každou z nich lze vyjádřit ve tvaru: y(n) = (i)it(n) = U(n) + ck-1nk-1 + ck-2nk~2 + ... + c0, kde c, € R pro i = 0, l,...,k — 1 jsou libovolné konstanty. Právě vyloženou problematiku ilustrujeme příkladem v další kapitole, kde zjistíme, že úloha na výpočet k— té sumace je zvláštním případem diferenční rovnice k—tého řádu. Uvidíme také, že Poznámka 3.25 vlastně popisuje, jakého tvaru je obecné řešení diferenční rovnice Aky(n) = u(n). 3.6 Úlohy na procvičení Úloha 3.29: Nalezněte všechny posloupnosti y(n), pro které platí Ay(n) = u{n), je-li: 1. u(n) = 6n2 + 8n [y(n) = 2n3 + n2 - 3n + c] 2. u{n) = (2n2 - 4) • 3" [y(n) = (n2 -3n + l) • 3" + c] 3. u(n) = sin [y(n) = -\ sin f n - cos f n + c] Úloha 3.30: Nalezněte funkční vzorec pro součet prvních n členů posloupnosti u(n), je-li: 1. u(n) = (2n- l)2 [s{n) = f n3 - \n = \n{2n - l)(2n + 1)] 2. u(n) =n(\)n~1 [S(n)=4-(n + 2)(|)"-1] 3. u(n) = n3 [«(„) = i(n4 + 2n3 + n2) = [\n{n + l)]2] Úloha 3.31: Rozhodněte, zda posloupnosti U(n) = cos(7rn — f) a V(n) = |[(—1)™ — \/2] jsou sumacemi téže posloupnosti. [ano; AU(n) = AV(n) = (—l)n+1; U{n) - V{n) = ... = \ cosTrn-|(-l)n+ +# = i(-ir -|(-i)n + f = f] Úloha 3.32: Nalezněte všechny posloupnosti y(n), pro které platí y(n) = ^ n sin Jn. [Návod: Postupujte metodou sumace per partes. Jejím užitím dostanete: y(n) = Ensmfn = — f (sin |n + cos Jn) + | ^(cos Jn — sin Jn). Metodou neurčitých koeficientů vypočtete, že E(cos fn ~ sm fn) = sm fn-] [y(n) = |(1 - n) sin |n - | cos |n + c] 27 Úloha 3.33: Nalezněte vzorec pro součet prvních n členů aritmetické posloupnosti. [Návod: Aritmetická posloupnost je určená rekurentně: u(n + 1) = u(n) + d, kde m(1) a (i jsou daná čísla. Funkční vzorec pro aritmetickou posloupnost dostanete ve tvaru u (n) = u(l) + (n—l)d. Výpočtem s(n) = ^2(u(l)+nd), s(l) = u(l) obdržíte vzorec s(n) = |n2 + [u(l) — |]n, který ještě upravte na obvyklejší tvar.] [«(«) = f [«(1)+«(«)]] Úloha 3.34: Určete součet vnitřních úhlů konvexního n—úhelníka (n > 3). [Návod: Součet vnitřních úhlů konvexního n—úhelníka A\A?....An je s(n). Uvažte konvexní (n + 1)—úhelník AiA2...An+i. Součet jeho vnitřních úhlů je dán součtem vnitřních úhlů n—úhelníka AiA2...An a trojúhelníka AiAnAn+i.] [Řešením As(n) = 180°, s(3) = 180° vyjde s(n) = (n - 2) • 180°.] Úloha 3.35: Určete počet úhlopříček konvexního n—úhelníka (n > 4). [Návod: Jeden ze způsobů, jak vyřešit tuto úlohu je sestavit rekurentní vztah. Počet úhlopříček v konvexním n—úhelníku AiA2...An je u(n). Uvažte konvexní (n + 1)—úhelník AiA2...An+i. Jeho úhlopříčky tvoří právě všechny úhlopříčky n-úhelníka AiA2...An plus „nové" úhlopříčky AiAn, A^An+i, AsAn+i, An-lAn+i.] [Řešením Au(n) = n - 1, m(4) = 2 vyjde u(n) = |n2 - |n = f(n - 3).] Úloha 3.36: Určete největší možný počet u(n) oblastí, na které lze rovinu rozdělit pomocí n kružnic. [Návod: Mějme n kružnic k\, &2, kn v obecné poloze, tj. n kružnic takových, že každé dvě z nich se protnou ve dvou bodech a žádné tři z nich neprocházejí jedním bodem. Uvažte kružnici ftn+i tak, aby všech n + 1 kružnic bylo opět v obecné poloze. Kružnice ftn+i je 2n průsečíky s kružnicemi ki,k^, — ,kn rozdělena na 2n oblouků, přičemž každý z těchto oblouků dělí jednu z původních oblastí roviny na dvě „nové".] [Řešením Ati(n) = 2n, m(1) = 2 vyjde u(n) = n2 — n + 2.] Úloha 3.37: Určete největší možný počet v(n) oblastí, na které lze rozdělit prostor pomocí n kulových ploch. [Návod: Mějme n kulových ploch Ki,K2, --^Kn v obecné poloze, tj. n kulových ploch takových, že každé tři se protínají a žádné čtyři neprocházejí týmž bodem. Uvažte kulovou plochu -řTn+i tak, aby všech n + 1 kulových ploch bylo opět v obecné poloze. Průniky -řTn+i C\Kj, j = 1, ...,n jsou kružnice, které rozdělí kulovou plochu Kn+i na n2 — n + 2 oblastí (viz Úloha 3.36), přičemž každá z těchto oblastí dělí jednu z původních částí prostoru na dvě „nové".] [Řešením Av(n) = n2 - n + 2, v(l) = 2 vyjde v(n) = |n3 - n2 + |n = = f(n2 -3n + 8).] 28 4 Pojem diferenční rovnice Definice 4.1: Nechť /: N x B.k+1 ->■ R je funkce k + 2 proměnných. Rovnici tvaru /(n,2/,A2/,A22/,...,A^)=0, (4.1) ve které je neznámou posloupnost y = ip(n), nazýváme diferenční rovnici k-tého řádu a 1. typu definovanou v N. Každou posloupnost y = ip(n), která pro všechna n € N splňuje rovnici (4.1), nazveme partikulárním řešením této rovnice. Obecným řešením pak rozumíme vzorec zahrnující všechna partikulární řešení. Definice 4.1 je analogická k definici diferenciální rovnice fc-tého řádu, nahradíme-li diference derivacemi příslušného řádu. Příklad 4.2: Diferenční rovnice 1. typu: 1. Ay — y = 4 je pro Vn € N rovnice 1. řádu 2. 3A2y + nAy = 0 je pro Vn € N rovnice 2. řádu 3. (n — l)2Ay = 5™ je pro n / 1 rovnice 1. řádu 4. (A3y)2 + 2n + 1 = 0 je pro Vn € N rovnice 3. řádu 5. A3y = 6 je pro Vn € N rovnice 3. řádu Ačkoliv ještě diferenční rovnice neumíme řešit, snadno si zdůvodníme, že 4. rovnice nemá reálné řešení, protože (A3y)2 > 0, 2" > 0 a součet na levé straně rovnice nikdy nemůže dát nulu. Povšimněme si nyní 5. rovnice. To je však úloha na k-tou sumaci (k =3), kterou jsme se zabývali v předchozím textu. Zvláštním případem diferenčních rovnic 1. typu jsou rovnice tvaru Aky = u(n). Je-li ?/i = ■ R je funkce * + 2 proměnných. Rovnici tvaru g{n,y{n),y{n + l),...,y{n + k)) = 0, (4.2) kde y(n + j) = ip(n + j), j = 0,1,2,*, ve které neznámou je posloupnost y(n) = ip(n), nazýváme diferenční rovnici 2. typu definovanou v N. Říkáme, že rovnice je k-tého řádu, jestliže se v (4.2) pro každé n € N skutečně objeví y(n) i y (n + k) („skutečně" se myslí tak, že nejsou např. vynásobeny koeficientem, který je pro nějaké n nulový). Každou posloupnost y(n) = ip(n), která pro všechna n € N splňuje rovnici (4.2), nazýváme partikulární řešení diferenční rovnice 2. typu v N. Obecným řešením rovnice 2. typu pak rozumíme vzorec zahrnující všechna partikulární řešení. Počáteční podmínky tvoří * daných dvojic hodnot {no + j, ifi(no + j)} pro j = 0. 1.2....,* - 1, kde n0 € N. Příklad 4.5: Diferenční rovnice 2. typu: 1. y2(n + 1) — 3y(n) = 4 je pro Vn € N rovnice 1. řádu 2. y(n + 2) = 1+fy™tyy{n) Je Pr0 n ^ 2 rovnice 2- řádu 3. y(n + 2) — y(n + 1) = 0 je pro Vn € N rovnice 1. řádu (rovnice neobsahuje členy y(n), tzn. řád rovnice určíme až po provedení substituce t = n + 1, když dostaneme rovnici y(t + 1) — y(t) = 0) Příklad 4.6: Rovnici 1. typu A2y + Ay = 0 převeďte na rovnici 2. typu. Řešení: Platí: Ay = y(n + 1) - y{n), A2y = y(n + 2)-2y(n + l)+y(n). Dosadíme-li do dané rovnice, dostáváme: y{n + 2) - y{n + 1) = 0. Všimněme si, že zatímco řád rovnice 1. typu byl 2, rovnice 2. typu je 1. řádu (viz Příklad 4.5.3), tedy řád nezůstal zachován. Obvyklejší je druhá definice diferenční rovnice včetně definice jejího řádu. Příklad 4.7: Rovnici y(n + 3) — 3y(n + 2) + y(n) = 5n převeďte na rovnici 1. typu: Řešení: Ze vztahů Ay = y(n+l)-A2y = y(n + 2)-A3y = y(n + 3)- vyjádříme y(n + l),y(n + 2) a y(n y(n+l) = y{n + 2) = y{n + 3) = 31 -y{n), -2y(n+l)+y(n), -3y{n+2)+3y{n+l)-y{n) + 3), přičemž značíme y(n) = y : &y + y, A2y + 2Ay + y, A3y + 3A2y + 3Ay + y. Dosadíme do dané rovnice a dostáváme Azy - 3Ay - y = 5n. Jak jsme již naznačili, v dalším budeme pracovat s rovnicemi 2. typu. Úloha 4.8: Nalezněte obecné a partikulární řešení dané rovnice, je-li: 1. A2y = 9 • 22n+1, 2/(1) = 5, Ay(l) = 20 [ Oft: y = 22n+1 + cm + c0, PŔ: y = 22n+1 - 4n + 1 ] 2. A2í/ = 12n, í/(1) = 5, Aj/(1) = -4 [ OŘ: 2/ = 2n3 - 6n2 + cm + c0, PŘ: y = 2n3 - 6n2 + 9 ] Úloha 4.9: Nalezněte obecné řešení dané rovnice, je-li: 1. A2y = & sin |n - | cos f n [ í/ = cos + cm + co ] 2. A32/ = (8n + 36) • 3" [ y = n ■ 3™ + C2n2 + cm + co ] 32 5 Pojem a vlastnosti lineárni diferenční rovnice Definice 5.1: Diferenční rovnici tvaru a0{n)y{n) + ai(n)y(n + 1) + ... + ak(n)y(n + k) = u(n), (5.1) kde u(n),ao(n),ai(n), ...,ak(n) jsou libovolné posloupnosti definované v N, přičemž oo(n) ý 0) ak{n) ý 0 pro všechna n € N, nazýváme lineární diferenční rovnicí k-tého řádu; ao(n),ai(n),..., ak(n) nazýváme koeficienty, u(n) pravou stranou. Jestliže jsou posloupnosti oo (n), oi (n),..., ak (n) konstantami, píšeme oo (n) = oo, oi(n) = oi,..., Oft(n) = Oft a říkáme, že rovnice má konstantní koeficienty. V opačném případě hovoříme o rovnici s nekonstantními koeficienty. Je-li pro všechna n € N u(n) = 0, říkáme, že rovnice je homogenní (bez pravé strany). V opačném případě mluvíme o rovnici nehomogenní (s pravou stranou). Příklad 5.2: 1. 2y {n + 2) — y (n + 1) + 3y (n) = 0 je homogenní lineární diferenční rovnice 2. řádu s konstantními koeficienty 2. y(n)y(n + 1) — y(n) = 1 není lineární diferenční rovnice 3. y(n + 1) + (n2 + l)y(n) = 5™ je nehomogenní lineární diferenční rovnice 1. řádu s nekonstantními koeficienty Věta 5.3: (Existenční věta pro lineární diferenční rovnici) Nechť je dáno k hodnot y(c),y(c + l),...,y(c + k — 1) v k po sobě jdoucích bodech c,c + 1, ...,c + k — lz definičního oboru N lineárni diferenční rovnice (5.1). Potom existuje v N právě jedno řešení rovnice (5.1), které splňuje zadané počáteční podmínky. Důkaz: Provedeme úplnou indukcí. Nechť daný bod c € N lze psát ve tvaru c = 1 + N, kde N je jisté přirozené číslo. Nejprve dokážeme, že řešení y(n) existuje pro n > c + k; k tomu nejdříve nalezneme y(c + k). Dosaďme n = c do rovnice (5.1): a0(c)y(c) + oi (c)j/(c + 1) + ... + ak(c)y(c + k) = u(c). Protože o;t(c) / 0, můžeme jednoznačně vypočítat y (c + k), neboť hodnoty y(c),y(c + 1), ...,y(c + k — 1) jsou předepsány. y(c + k) = —^--[íi(c) - a0(c)y(c) - oi(c)j/(c + 1) - ... - ak-i{c)y{c + k - 1)]. ak(c) Předpokládejme, že takto lze jednoznačně vypočítat hodnoty y(c + k),y(c + k + 1),y(c + K) pro jisté K > k. Z toho dokážeme, že lze jednoznačně vypočítat i y(c + K + 1) a to následovně: do rovnice (5.1) dosadíme n = c + K — k + 1 (n € N); protože K — k>0, je n > c + 1 : a0{n)y{c+K-k+l)+a1{n)y{c+K-k+2)+...+ak{n)y{c+K+l) = u{c+K-k+ľ). Neboť ak(n) / 0, lze jednoznačně vyjádřit y(c + K+l) = —^-—\u{c + K-k + ľ] - a0(n)y(c + K - k + 1) -ak(n) - ai(n)y(c + K - k + 2) - ... - ak-i(n)y(c + K)}. Protože c + K — k + l>c+l, jsou tedy hodnoty y(c + K — k + l),y(c + K — k + 2),y (c + K) podle indukčního předpokladu určeny jednoznačně. To ale znamená, že řešení existuje, a to jediné, pro všechna n> c + k. 33 Nyní vypočtěme řešení pro n = 1,2,...,c — 1. Dosaďme do rovnice (5.1) n = c-l € N: o0(c - l)y(c - 1) + oi(c - l)y(c) + ... + ak{c- l)y(c - 1 + k) = u(c - 1). Odtud můžeme jednoznačně vypočítat y(c — 1), protože v diferenční rovnici předpokládáme oo(n) / 0. Dále, dosadíme-li n = c — 2, vypočteme podobně y(c — 2) atd., až po N (konečně mnoha) krocích vypočítáme y(c — N) = y(l). Nyní se budeme zabývat homogenní rovnicí. V následujících větách si ukážeme několik vlastností, které mají řešení této rovnice. Věta 5.4: Rovnice a0{n)y{n) + ax(n)y(n + 1) + ... + ak(n)y(n + k) = 0 (5.2) má pro všechna n € N vždy tzv. triviální řešení y(n) = 0. Důkaz: Je-li pro Vn € N y(n) = 0, pak y(n + j) = 0 pro j = 0,1,k a tedy a0{n)y{n) + oi(n)t/(n + 1) + ... + ak{n)y{n + k) = Y!j=o o-3{n)y{n + j) = 0. Věta 5.5: Nechť ifii(n) a ip2(n) jsou partikulární řešení rovnice (5.2) a nechť Ci, C2 jsou libovolné konstanty. Pak funkce y(n) = C\tpi (n) + C2ÍP2(n) je rovněž řešením rovnice (5.2). Důkaz: £)*=0 aj(n)[C1(n0 + l) k Cjifj (n0 + k - 1) = ip(n0 + k - 1). Podle předpokladu a Věty 5.9 existuje no € N, pro něž je determinant matice soustavy nenulový a tedy existuje jediné řešení C{, C%, ■ ■ ■, C£. Tím jsme dokázali, že ip(n) = J2j=i Cj2{n) je řešením rovnice Ej=o aj(n)y(n + i) = v(n). Pak aipi(n) + f3tp2(n) je řešením rovnice Ej=o aú(n)ž/(n + J) = Oiu{n) + j3v(n). Důkaz: Y%=o aú (n) [«^1 (n + J) + Pfo (n + J)] = a E*=o aú (n)^1 (« + j) + PEj=o aj(n)^2(n+j) = au(n) + f3v(n). 35 Důsledek 5.12: Jsou-li ipi{n),ip2{n>) libovolná řešení nehomogenní rovnice (5.1), pak je rozdíl ipi(n) — ip2(n) řešením homogenní rovnice (5.2). Důkaz: Vyplývá přímo z Věty 5.11, je-li a = 1, p = —1, u(n) = v(n). Důsledek 5.13: Nechť Y(n) = EjU Cj'ftW je obecné řešení homogenní rovnice (5.2), nechť Z(n) = ip(n) je partikulární řešení nehomogenní rovnice (5.1). Pak obecné řešení rovnice (5.1) je tvaru k y(n) = Z(n)+Y(n) = i&(n) + ^C^(n). (5.4) Důkaz: Potřebujeme dokázat, že libovolné řešení rovnice (5.1) (označme jej ipi(n)) lze zapsat ve tvaru (5.4). To však plyne z Důsledku 5.12, neboť k ^i(n) - tp(n) = J2CjPÁn)> tj- k ^i(n) = tp(n) + J2CjfAn)- Obecné řešení nehomogenní rovnice je tedy součtem jednoho partikulárního řešení nehomogenní rovnice a obecného řešení homogenní rovnice. Na závěr této kapitoly ukažme, jak najít partikulární řešení nehomogenní rovnice určené počátečními podmínkami. Nechť je dáno obecné řešení tvaru (5.4) rovnice (5.1). Hledejme partikulární řešení, které v daných k po sobě jdoucích bodech no, no + 1, ...,no + k — 1 z definičního oboru N nabývá daných hodnot y{n0) = Y0,y(n0 + 1) = Yi,...,2/(n0 + k - 1) = Yfc_i (počáteční podmínky). Z těchto podmínek lze určit jednoznačně konstanty C±, C2, Cft následujícím způsobem: dosaďme postupně do tvaru (5.4) za no a y(no) počáteční podmínky. Dostáváme soustavu k lineárních rovnic pro neznámé C±, C2, C k : k ^2Cjí = (A2-Ai)(A3-Ai)...(A*-Ai) 1 A2 1 A3 A: k-2 \k~2 1 Aj; \k-2 Ák Tedy Dl = (A2 - Ai)(A3 - Ai)...(A* - Ai)^. Podle předpokladu je (A2 — Ai)(A3 — \i)...(\k — Xi) Ý 0, což znamená, že potřebujeme dokázat, že D*k_x / 0. Dále postupujeme analogicky, až se dostaneme k determinantu 1 1 Dl A&-1 A& Aft - Aft_i / 0, což jsme potřebovali dokázat. Rovnice (6.2) má nejvýše k různých kořenů A,, a to podle Poznámky 6.3 nenulových, což podle Vět 6.2 a 6.4 znamená, že známe příslušný počet lineárně nezávislých partikulárních řešení rovnice (6.1). V dalším se budeme zabývat problémem, jak nalézt fundamentální systém řešení v závislosti na charakteru kořenů charakteristické rovnice (6.2). 6.1 Charakteristická rovnice má k různých reálných kořenů Věta 6.5: Nechť Ai, A2,A&, A, € R, A, / \j, kde i / j, i, j = 1,2, jsou kořeny rovnice (6.2). Pak rovnice (6.1) má v N obecné řešení tvaru y(n) =CiA? + C2A2l + ... + CifeA£, kde Ci, C2,C k jsou libovolné konstanty. Důkaz: Věta vyplývá z Vět 5.10, 6.2 a 6.4. Příklad 6.6: Nalezněte obecné řešení rovnice y(n+2)—9y(n+l)+20y(n) = 0. Řešení: Charakteristická rovnice má tvar A2 — 9A + 20 = 0. Její řešení určíme snadno pomocí rozkladu na součin: (A — 4) (A — 5) = 0, tedy Ai = 4, A2 = 5. Podle Věty 6.5 je obecné řešení této rovnice y(n) = Ci4n + C25". Příklad 6.7: Zjistěte, kolik „slov" délky n lze sestavit z písmen A, B, C tak, aby žádné z nich neobsahovalo „podslovo" typu AA,AB,BA,BB. Řešení: Označme s(n) počet hledaných slov. Rozdělme množinu slov délky n+ 2 vyhovujících zadání na tři disjunktní podmnožiny podle toho, jakým písmenem končí. Ovšem slova končící písmenem A (resp. B) musí mít předposlední písmeno C, aby neobsahovala zakázané podslovo. Touto úvahou dostáváme rekurentní vzorec s(n + 2) = s(n + 1) + 2s(n), což je vlastně lineární diferenční rovnice, kterou lze přepsat do obvyklejšího tvaru s{n + 2) - s{n + 1) - 2s{n) = 0. Zřejmě s(l) = 3, s{2) = 5. 38 Charakteristická rovnice je A2 — A — 2 = 0a její kořeny Ai = 2, \2 = — 1. Obecné řešení má tvar s(n) = C12n + C2(-l)n. Konstanty Ci,C2 určíme z počátečních podmínek = 3, s(2) = 5, dosadíme-li do obecného řešení za n = 1, n = 2 : 3 = 2CX-C2, 5 = 4Ci+C2. Řešením této soustavy jsou hodnoty Ci = |, C2 = — |. Pro hledaný počet slov jsme našli vzorec tedy s(n) = 1 [2"+2 + (-l)**1] . 6.2 Charakteristická rovnice má imaginární kořeny Nejprve si připomeňme známé poznatky o komplexních číslech, o které se opírá následující věta: • Jestliže má charakteristická rovnice (6.2) imaginární kořen Ai = a + i/3, pak má i kořen \2 = a — i/3. • Každé komplexní číslo a + i/3 / 0 lze vyjádřit pomocí jeho absolutní hodnoty a argumentu v goniometrickém tvaru r(cosw + i siná;) = a + i/3 • Moivreova věta [r(cos w + i sinuj)]n = rn (cos wn + i sin wn) Věta 6.8: Nechť má rovnice (6.2) imaginární kořeny Ai,2 = r(cosw±zsino;) (tj. r ^ 0 a w / kir, k £ N). Pak má rovnice (6.1) tato lineárně nezávislá partikulární řešení tpi(n) = rn cos um, (p2(n) = rn sinům, tedy má za řešení posloupnost yi,2(rc) = rn(C\ cosuin + C2 sinwn), kde Ci, C2 jsou libovolné konstanty. Důkaz: Má-li rovnice (6.2) kořeny \í}2 = r(cosw ± zsino;), pak podle Věty 6.2 je posloupnost A™2 partikulárním řešením rovnice (6.1). Ale A™2 = [r(cosa;± i sva.u))]n = [r(cos(±w) + i sin(±w))]n = rn[cos(±um) + i sin(±wn)] = rn (cos um ± i sin um). Tedy A™ 2 = rn (cos um ± i sin um) Podle Věty 5.5 jsou řešením rovnice (6.1) i posloupnosti z. Dostáváme z3 - 2>z - 2(z2 - 2) + 2>z - 4 = 0, tj- zz - 2z2 = 0, tedy z\ = 2, z2,z = 0. Vraťme se k původní proměnné A. Kořen z\ = 2 nás přivede k hodnotě Aii2 = 1, dvojnásobný kořen z2j3 = 0 pak ke dvojnásobným imaginárním kořenům A3,4 = i = cos J + i sin J a X^^ = —i = cos | — i sin Podle Věty 6.11 a Poznámky 6.12 lze obecné řešení zapsat 7T 7T 7T 7T y(n) = Ci + C2n + C3 cos — n + C^ncos —n + C5 sin — n + Cen sin — n. Po úpravě y(n) = Ci + C2n + cos -^n{Cz + C^n) + sin — n(Cs + Cen). 6.4 Úlohy na procvičení Úloha 6.14: Nalezněte obecné řešení a partikulární řešení určené počátečními podmínkami: 1. y(n + 2)+y(n+l)-6y(n)=0, y(l) = -13, 2/(2) =-11 [OŘ: y{n) = Cx2n + C2(-3)n, PŘ: y{n) = -5 • 2n + (-3)"] 2. ž/(n + 2)+4ž/(n + l)-12ž/(n) = 0, y(l) = -32, 2/(2) = 32 [OŘ: ?/(n) = Ci2" + C2(-6)n, PŘ: y(n) = -5 • 2n+1 + 2 • (-6)"] 3. 2/(n + 2)+4í/(n + l) + 162/(n) = 0, 2/(1) = 2, í/(2) =-40 [OŘ: y(n) = Ci4" cos ^n + C24" sin ^n, PŘ: y(n) = 2 • 4™ cos ^n + • 4™ sin ^n] Úloha 6.15: Nalezněte funkční vzorec pro posloupnosti dané rekurentně: 1. w(n + 2) =9w(n+l) - 18w(n), u(l) = 1, u{2) = 21 [u(n) = -5 • 3""1 + 6n] 2. u{n + 2) = 2w(n+ 1) +2w(n), u(l) =-1, u{2) = 1 [„(„) = 2d^I(i - VŠ)" + 2=^(1 + VŠ)n] 3. w(n + 2) = 2w(n+ 1) - 2w(n), m(1) = 2, u{2) = -2 [u(n) = ^(3 cos f n - sin f n)] Úloha 6.16: Nalezněte obecné řešení následujících diferenčních rovnic 1. ž/(n + 3) +8y{n) = 0 [y(n) = Ci (-2)" + C22" cos f n + C32" sin f n] 41 2. y(n + 3) - 12y{n + 2) + 48y (n + 1) - 64j/(n) = O [y(n) = Ci4" + C2n4" + C3n24"] 3. y (n + 3) - 5j/(n + 2) - 4j/(n + 1) + 20y (n) = O [y(n) = C12n + C2(-2)n + C35n] 4. y (n + 3) - 3j/(n + 2) + 4y (n + 1) - 12j/(n) = O [j, (n) = Ci2" cos f n + C22" sin f n + C33n] 5. y(n + 4) - 2j/(n + 2) + j/(n) = 0 [y(n) = Ci + C2n + C3(-l)n + C4n(-1)»] Úloha 6.17: Rešete rovnice 1. typu: [Návod: Rovnice 1. typu nejprve převeďte na rovnice 2. typu, které jsou již doposud vyloženými prostředky řešitelné] 1. A2y - Ay = 0 [y(n) = d + C22n] 2. Azy + 3A2y + 3Ay = 0 [y{n) =d + C2 cos + C3 sin ^n] Úloha 6.18: Zjistěte, kolik „slov" délky n lze sestavit z písmen ^4,5, C tak, aby žádné z nich neobsahovalo „podslovo" typu ^4^4 nebo BA. [Návod: Uvažujte podobně jako v Příkladu 6.7. Je zřejmé, že slova končící písmenem A musí mít na předposledním místě písmeno C] [Řešením rovnice s(n + 2) — 2s(n + l) — s(n) = 0, s(l) = 3, s(2) = 7 dostanete s(n) = |[(1 + V2)n+1 + (1 - V2)n+1].] Úloha 6.19: Zjistěte, kolik „slov" délky n lze sestavit z písmen A,B,C,D tak, aby žádné z nich neobsahovalo „podslovo" typu AB, BB, BC, CB, CC. [Návod: Promyslete si, že slova končící písmenem B musí mít na předposledním místě písmeno D a slova končící C mohou mít na předposledním místě pouze A nebo D] [Řešením rovnice s(n + 2) - 2s(n + 1) - 3s(n) = 0, s(l) = 4, s(2) = 11, dostanete s{n) = |[5 • 3" + (-l)n+1].] 42 7 Nehomogenní lineární diferenční rovnice s konstantními koeficienty Zabývejme se rovnicí s konstantními koeficienty aoy{n) + aiy(n + 1) + ... + aky(n + k) = u(n), (7.1) kde oo Ý 0 a a& / 0 jsou reálné konstanty. Připomeňme, že obecné řešení rovnice (7.1) je dáno součtem obecného řešení zhomogenizované rovnice a libovolného partikulárního řešení rovnice nehomogenní (viz Důsledek 5.13). Homogenní rovnice již umíme řešit, soustřeďme se nyní na nalezení partikulárního řešení nehomogenní rovnice. K tomu lze použít dva postupy: metodu neurčitých koeficientů (též nazýváme jako metodu odhadu partikulárního řešení) a nebo metodu variace konstant, což vyložíme v následujících podkapitolách. 7.1 Metoda neurčitých koeficientů Tuto metodu je možno použít jen pro speciální pravé strany u(n), a to pro posloupnosti typu konst, nk, qn, sinán, cos an a posloupnosti utvořené součtem nebo součinem z nich. Z faktu, že jejich diference 1., 2.,... až k— tého řádu a jejich lineární kombinace jsou opět posloupnosti téhož typu (viz kapitola 2), usuzujeme, že toto platí i obráceně. Známe-li výslednou posloupnost u(n) utvořenou lineární kombinací Ej=o ajZ{n + j)i Pak posloupnost Z(n) je stejného typu jako u(n). Platí následující věta. Věta 7.1: Nechť je dána rovnice s konstantními koeficienty aoy(n) + aiy(n + 1) + ... + aky(n + k) = Pm(n)qn cosan, (7.2) kde Pm(n) je polynom stupně m > 0. 1. Nechť má charakteristická rovnice kořeny Xj / q(cosa + z sin a). Pak je partikulárním řešením rovnice (7.2) posloupnost tvaru Z(n) = [Qm(n) sinán + Rm(n) cosan]qn, kde Qm(n) a Rm(n) jsou jisté polynomy stupně m. 2. Nechť má charakteristická rovnice některý kořen Xj = q(cos a+i sin a) a to s—násobný, s > 1. Pak je partikulárním řešením rovnice (7.2) posloupnost tvaru Z(n) = ns[Qm(n) sinán + Rm(n) cosan]qn, kde Qm(n) a Rm(n) jsou jisté polynomy stupně m. Poznámka 7.2: Analogické tvrzení platí pro rovnici «ož/(") + aiy(n + 1) + ... + auy{n + k) = Pm(n)qn sinán. Důkaz zde nebudeme provádět, protože je poměrně obtížný. Pokud se čtenář chce o této problematice dozvědět více, můžeme jej odkázat na knihu [3], kapitola 2.4, str. 70. Při hledání partikulárního řešení nehomogenní rovnice postupujeme tak, že do dané diferenční rovnice dosadíme odhadnutý tvar Z(n) (podle Věty 7.1, resp. Poznámky 7.2) s neurčitými koeficienty, které pak získáme porovnáním s koeficienty pravé strany u(n). Příklad 7.3: Najděte obecné řešení rovnice y(n + 2) — 8y(n + 1) + 15y(n) = 130 sinfn. 43 Řešení: Nejprve najdeme obecné řešení zhomogenizované rovnice y(n + 2) — 8y(n +1) + 15t/(n) = 0. Její charakteristická rovnice A2 — 8A +15 = 0 má kořeny Ai = 3 a A2 = 5, takže obecné řešení homogenní rovnice je Y(n) =C13n + C25n. To znamená, že partikulární řešení nehomogenní rovnice předpokládáme ve tvaru ryl \ . 7 7i" Z(n) = asm —n + o cos — n. Dosaďme do dané rovnice: osin^(n + 2) + 6cos^(n + 2) - 8[asin^(n+ 1) + 6cos^(n + 1)]+ 7T 7T 7T +15[asin — n + 6 cos —n] = 130 sin —n. Užitím součtových vzorců po úpravě dostáváme: 7T 7T 7T (14a + 86) sin — n + (-8a + 146) cos — n = 130 sin — n. Nyní porovnejme koeficienty: 14a + 86 = 130 -8a +146 = 0, odkud a = 7, 6 = 4. Partikulární řešení rovnice je Z(n) = 7 sin — n + 4 cos — n. Konečně obecné řešení jsme nalezli ve tvaru y{n) = Ci3n + C25n + 7sin|n + 4cos|n. Příklad 7.4: Nalezněte obecné řešení rovnice y(n + 2) + 6y(n +1) + 9y(n) = (4n2+4n)(-3)"+3. Řešení: Charakteristická rovnice zhomogenizované rovnice je A2 + 6A + 9 = 0 a má dvojnásobný kořen Aii2 = —3. Obecné řešení homogenní rovnice je tedy Y(n) = Ci(-3)n + C2n(-3)n. Proto partikulární řešení nehomogenní rovnice musíme hledat ve tvaru Z(n) = n2{an2 + bn + c)(-3)n. Po dosazení do dané rovnice dostaneme: (n+2)2[a(n+2)2+6(n+2)+c](-3)n+2+6(n+l)2[a(n+l)2+6(n+l)+c](-3)n+1+ +9n2(an2 + bn + c)(-3)n = (4n2 + 4n)(-3)n+3. Rovnici vydělíme (—3)™ a zjednodušíme: 108an2 + (216a + 546)n + 126a + 546 + 18c = -108n2 - 108n. Porovnáním koeficientů snadno vypočteme: 108a =-108 =^ a = -l, 216a+ 546=-108 =^ 6 = 2, 126a+ 546+ 18c = 0 =^ c = 1. 44 Hledané partikulární řešení je Z(n) = n2{-n2 + 2n + l)(-3)n. Obecné řešení diferenční rovnice je tvaru „(„) = Ci(-3)n + C2n(-3)n + n2(-n2 + 2n+ l)(-3)n. Snadno nahlédneme, že právě probíraný odhad partikulárního řešení Z(n) úzce souvisí s výpočtem k—té sumace vyloženém v předchozím textu. Podle Věty 2.21 je Y,(-l)k-J[kk_J)y(n + j) = Aky a tedy rovnice 1. typu Aky = Pk{n)qn cosan je speciálním případem rovnice (7.2). Poznámka 7.5: Metodou neurčitých koeficientů lze řešit i rovnice se „složitější" pravou stranou, než bylo uvedeno ve Větě 7.1. Je-li pravá strana rovnice (7.1) součtem ui(n) + U2(n), kde ui(n) a U2(n) jsou speciálního tvaru ve smyslu Věty 7.1, je-li Zi(n) partikulární řešení rovnice Ej=o ajH(n +Í) = ui(n) a je-li Z2(n) partikulární řešení rovnice Ej=o °jž/(n + J) = M2(^), pak podle principu superpozice (Věta 5.11) víme, že Zi(n) + Z2(n) je partikulární řešení rovnice Ej=o ajy(n + i) = Mi(n) + Ma(n). V následující podkapitole uvedeme příklad, ve kterém zmíněné skutečnosti využijeme. 7.2 Metoda variace konstant Tato metoda je obecná a nevyžaduje speciální tvar pravé strany řešené rovnice (7.1). Nechť k Y(n) = Y,Cmin) (7-3) je obecné řešení příslušné zhomogenizované rovnice aoy{n) + aiy(n + 1) + ... + aky(n + k) = 0. (7.4) Metoda variace konstant spočívá v nahrazení konstant Cj ve tvaru (7.3) posloupnostmi Cj(n). Hledejme tedy partikulární řešení rovnice (7.1) ve tvaru k Z(n) = Y,Cj(n)pj(n). j=i K určení k neznámých posloupností Cj(n) je třeba k rovnic. Jednou z nich je samozřejmě rovnice (7.1), zbylých k — 1 rovnic si vhodně zvolíme při tvoření hodnot Z(n + 1), Z(n + 2),Z(n + k). Z Definice 2.2 plyne Cj(n + l) = Cj(n) + ACj(n), proto k k k Z(n + 1) = Ci (n + !) W (" + 1) = 5 Cj {n)ipj (n + 1) + ^ ACÔ {n)ipj (n + 1). 45 Zvolme C j (n) tak, aby k ^AC3-(n)W(n + l)=0, 3=1 tedy Z(n + l) = J2Cj(n) + 1)AC» = o, EL^(" + 2)AC» = 0, (7.5) E}=i¥>j(n + *-l)AC» = 0, 46 Protože posloupnosti ip±(n),ip2(n), ■ ■■, 0 lze rovnici upravit na tvar 71 + 1 y(n + 1)--y(n) = n2 + 4n + 3, n A(n) = B(n) = n2 + 4n + 3. Nejprve podle (8.4) vypočtěme, jakého tvaru je obecné řešení zhomogenizované rovnice: n-l n-l . 1 o -3 Y(n)=Cl[A{j) = Cl[l±± = C.2rl.....^-1=Cn. j=í j=í J Partikulární řešení nehomogenní rovnice vypočteme podle vzorce (8.7). K tomu pro větší přehlednost výpočtu nejprve vyjádřeme u(n) a«(n). Již víme, že n-l u{n) = Y[ A{j) = n 3=1 a zbývá nám provést výpočet: v(n] = y BW _y^J2+4j + 3_^(j + l)(j + 3) _ n-l 3=1 2 i c-ln ľ + 5j 1 2 Partikulární řešení nehomogenní rovnice je tedy (n2 + 5n-6). J i 2 Z(n) = u(n) • v(n) = -^\n + on — o) = — -\—---3n. Konečně pro obecné řešení platí: y(n) = Y(n) + Z(n) = Cn + - + — - 3n = (C - 3)n + y + —. Výraz C — 3 je libovolná konstanta (neboť C je libovolné), označme ji K. Nalezli jsme obecné řešení ve tvaru y(n) =Kn+ — + —. Poznamenejme, že o správnosti výsledku se můžeme přesvědčit zkouškou. To však již ponecháme na čtenáři. Úloha 8.4: Nalezněte obecné řešení následujících rovnic: «±3, n+1 ' 1. y(n + 1) - ?#ž/(n) = n3 + 6n2 + lln + 6 [y(n) = K(n2 + 3n + 2) + |(n4 + 4n3 + 5n2 + 2n)] 2. ny{n + 1) - (n + 2)t/(n) = n4 + 3n3 + 2n2 [y(n) = K(n2 +n) + \(nA -n2)] 52 Literatura [1] A.Prágerová, Diferenční rovnice, SNTL, Praha, 1971. [2] R.P.Agarwal, Difference Equations and Inequalities, Theory, Methods, and Applications, Pure and Appl. Math., M.Dekker, New York, Basel, Hong Kong, 1992. [3] S.N.Elaydi, An Introduction to Difference Equations, Springer Uerlag, New York, 1996. [4] W.G.Kelly, A.C.Peterson, Difference Equations: An Introduction with Applications, Academic Press, San Diego, 1991. [5] J.Herman, R.Kučera, J.Šimša, Metody řešení matematických úloh I, skripta MU, Brno, 1996. [6] J.Herman, R.Kučera, J.Šimša, Metody řešení matematických úloh II, skripta MU, Brno, 1997. [7] P.Horák, J.Janyška, Analytická geometrie, skripta MU, Brno, 1997. [8] P.Horák, Algebra a teoretická aritmetika I, skripta MU, Brno, 1994. [9] I.Bušek, R ešené maturitní úlohy z matematiky, Prometheus, Praha, 1999. [10] F. Vejsada, F. Talafous, Sbírka úloh z matematiky pro gymnasia, SPN, Praha, 1969. 53