Lineární rekurence
Úloha číslo: 3699
Nalezněte vzorec (analytické vyjádření) pro \(n\)-tý člen posloupnosti zadané pomocí rekurence:
Varianta
\(a_0=1, a_{n+1}=a_n+1\)
Řešení
I když je řešení očividné, ilustrujeme si na úloze obecný postup pro řešení rekurencí.
Sestavíme vytvořující funkci pro posloupnost \((a_0,a_1,a_2,…)\) a dostaneme \(a(x)=xa(x)+\frac{1}{1-x}\).
Člen \(xa(x)\) odpovídá výrazu \(a_{n}\) v pravé straně předpisu pro \(a_{n+1}\). Funkce \(\frac{1}{1-x}\) odpovídá posloupnosti samých jedniček, což odpovídá přičtení 1 v pravé straně předpisu pro \(a_{n+1}\).
Hledaná funkce je \(a(x)=\frac{1}{(1-x)^2}\) a ta odpovídá posloupnosti \((1{,}2,3,…)\).
Varianta
\(a_0=1, a_{n+1}=2a_n+3\)
Řešení
Sestavíme vytvořující funkci pro posloupnost \((a_0,a_1,a_2,…)\) a dostaneme \(a(x)=2xa(x)+\frac{3}{1-x}-2\).
Člen \(2xa(x)\) odpovídá výrazu \(2a_{n}\) v pravé straně předpisu pro \(a_{n+1}\). Funkce \(\frac{3}{1-x}-2\) odpovídá posloupnosti \((1{,}3,3{,}3,…)\), jejíž prvky postupně přičítáme v pravé straně předpisu pro \(a_{n+1}\).
Hledaná vytvořující funkce je \(a(x)=\frac{1}{1-2x}\left(\frac{3}{1-x}-2\right)\).
Abychom dostali analytické vyjádření, je třeba \(a(x)\) postupně derivovat, resp. nalézt příslušný Taylorův rozvoj. K tomu se využívá rozklad \(a(x)\) na parciální zlomky, v našem případě ve tvaru \(\frac{\alpha}{1-\lambda_1x}+\frac{\beta}{1-\lambda_2x}\).
Všimněte si, že levý sčítanec rozkladu je vytvořující funkce pro \((\alpha,\alpha\lambda_1,\alpha\lambda_1^2,\alpha\lambda_1^3,…)\) a pravý \((\beta,\beta\lambda_2,\beta\lambda_2^2,…)\) tedy \(n\)-tý člen posloupnosti lze bezprostředně vyjádřit jako \(a_n=\alpha\lambda_1^n+\beta\lambda_2^n\).
Prorovnáním jmenovatelů v \(a(x)\) a v hledaném rozkladu dostaneme \(\lambda_1=1\) a \(\lambda_2=2\).
Koeficienty \(\alpha\) a \(\beta\) spočítáme ze soustavy jejíž řádky odpovídají rovnostem pro \(a_0\) a \(a_1\):
\(a_0=1=\alpha 1^0+\beta2^0=\alpha+\beta\\ a_1=5=\alpha 1^1+\beta2^1=\alpha+2\beta\)
odtud \(\alpha=-3\) a \(\beta=4\).Odpověď
Posloupnost lze vypočítat podle předpisu \(a_n=2^{n+2}-3\).
Varianta
\(a_0=a_1=1, a_{n+2}=a_{n+1}+6a_n\)
Nápověda
Poznámky k zjednodušení postupu v obecném případě:
Nehomogenní rekurence typu \(a_n=q_1a_{n-1}+q_2a_{n-2}+…+q_ka_{n-k}+b\) mají ve vytvořující funkci vždy člen \(\frac{b}{1-x}\). Přítomnost tohoto členu způsobí, že se v analytickém vyjádření vždy objeví mocnina kořene polynomu \(1-x\) (případně s příslušnou násobností jako v předchozí variantě). Tento kořen se v následujících příkladech značí \(\lambda_0=1\).
Ostatní \(\lambda_1,…,\lambda_k\) se spočítají z homogenní rekurence \(a_n=q_1a_{n-1}+q_2a_{n-2}+…+q_ka_{n-k}\) jako kořeny tzv. charakteristického polynomu \(y^k- q_1y^{k-1}-q_2y^{k-2}-…-q_k\).
Důvod pro to je následující. Hledáme-li rozklad,
\(1-q_1x-q_2x^2-…-q_kx^k=(1-\lambda_1x)(1-\lambda_2x)…(1-\lambda_kx)\)
můžeme celou rovnici vynásobit \(y^k\) pro \(y=\frac1x\) a dostaneme:
\(y^k-q_1y^{k-1}-q_2y^{k-2}-…-q_ky^0=(y-\lambda_1)(y-\lambda_2)…(y-\lambda_k)\).
Tedy \(\lambda_i\) je vhodným koeficientem v rozkladu, právě když je kořenem charakteristického polynomu.
Je-li \(\lambda_i\) \(k\)-násobným kořenem, vyskytnou se v rozkladu na parciální zlomky členy se jmenovatelem \((1-\lambda_i)^l\), a potom v analytickém vyjádření členy \(n^{l-1}\lambda_i^n\) pro \(l=1,…,k\).
Řešení
Charakteristický polynom \(\lambda^2-\lambda-6 = (\lambda+2) (\lambda-3)\) má kořeny
\(\lambda_1=-2, \lambda_2=3\), tedy \(a_n=\alpha (-2)^n + \beta 3^n\). Dosadíme za \(n=0{,}1\):
\( 1 = \alpha+\beta \\ 1 = -2\alpha+3\beta \)
a získáme \(\alpha=\frac{2}{5}, \beta=\frac{3}{5}\).
Odpověď
Posloupnost lze vypočítat podle předpisu \(a_n=\frac{2}{5} (-2)^n + \frac{3}{5}\; 3^n\).
Varianta
\(a_0=a_1=1, a_{n+2}=a_{n+1}+6a_n-4\)
Řešení
Kvůli nehomogenitě diferenční rovnice přidáme ke kořenům předchozího řešení ješte
\(\lambda_0=1\) a budeme mít \(a_n=\alpha (-2)^n + \beta 3^n+\gamma\). Dopočteme z rekurence \(a_2= 3\) dosadíme za \(n=0{,}1,2\):
\( 1= \alpha+\beta+\gamma \\ 1 = -2\alpha+3\beta+\gamma \\ 3 = 4\alpha+9\beta+\gamma \)
a získáme \(\alpha=\frac{2}{15}, \beta=\frac{1}{5}, \gamma=\frac{2}{3}\).
Odpověď
Posloupnost lze vypočítat podle předpisu \(a_n=\frac{2}{15} (-2)^n + \frac{1}{5}\; 3^n+\frac{2}{3}\).
Varianta
\(a_0=0, a_1=1, a_{n+2}=4(a_{n+1}-a_n)\)
Řešení
Tentokrát nám vyjde z charakteristického polynomu \(\lambda^2-4\lambda+4=(\lambda-2)^2\)
dvojnásobný kořen \(\lambda_{1{,}2}=2\). Při rozkladu na parciální zlomky je tedy nutné přidat zlomek se jmenovatelem v druhé mocnině a v posloupnosti člen tvaru \(n\lambda^n\).
Tedy \(a_n=\alpha 2^n+\beta n 2^n\). Opět dosadíme pro \(n=0{,}1\)
\( 0=\alpha \\ 1=2\alpha+2\beta \)
dává \(\alpha=0, \beta=\frac{1}{2}\).
Odpověď
Posloupnost lze vypočítat podle předpisu \(a_n=n\ 2^{n-1}\).
Varianta
\(a_0=0, a_1=1, a_{n+2}=4(a_{n+1}-a_n)+1\)
Řešení
Opět stačí přidat kořen \(\lambda_0=1\), dopočítat \(a_2=5\) a vyřešit soustavu
\( 0=\alpha+\gamma \\ 1=2\alpha+2\beta+\gamma \\ 5=4\alpha+8\beta+\gamma \)
dávající \(\alpha=1, \beta=-1, \gamma=1\).
Odpověď
Posloupnost lze vypočítat podle předpisu \(a_n=1+(n-1)2^n\).
Varianta
\(a_0=2, a_1=3, a_{n+2}=3a_n-2a_{n+1}\)
Odpověď
Posloupnost lze vypočítat podle předpisu \(a_n=\frac{9-(-3)^n}{4}\).
Varianta
\(a_0=0, a_1=1, a_{n+2}=a_{n+1}+2a_n+2\)
Odpověď
Posloupnost lze vypočítat podle předpisu \(a_n=2^n-1\).
Varianta
\(a_0=a_1=1, 5a_{n+2}=4a_{n+1}-a_n\)
Varianta
\(a_0 = 4, a_1 = 3, a_n = a_{n-1} + 2 a_{n-2} + 3{\cdot} 2^n\) pro \(n \geq 2\)
Nápověda
Toto je těžší varianta. Snažte se rekurenci vyřešit pomocí vytv. funkcí.
Odpověď
\((2n + 1)2^n + 3\cdot(-1)^n\)