Rekurentní vztahy

Determinant $ D_n$ stupně $ n$ se nám může podařit vyjádřit pomocí determinantů $ D_{i}$, $ i<n$ (obvykle po rozvinutí podle řádku či sloupce). Získanou rovnost (viz například 46 či 45) nazýváme rekurentním vztahem pro posloupnost $ D_n$.

Z rekurentního vztahu se můžeme pokusit ,,uhodnout'' přímo ,,vzorec pro $ n$-tý člen'', tedy vyjádření $ D_n$ pouze pomocí $ n$ a nikoliv $ D_{n-1}$. Uhodnutý vzorec pak dokážeme obvykle nejsnáze matematickou indukcí. Při hádání nám může pomoci, pokud si vypíšeme prvních několik členů posloupnosti $ D_n$, nebo naopak, když například do vztahu $ D_n=f(D_{n-1})$ dosadíme za $ D_{n-1}=f(D_{n-2})$.

Často se setkáváme s lineárními rekurentními vztahy. Ukážeme, jak u nich lze nalézt explicitní vzorec pro $ D_n$. Nechť má rekurentní vztah tvar

$\displaystyle D_n=pD_{n-1}+qD_{n-2}\,,\quad n>2\,,$ (46)

kde $ p,q$ jsou konstanty nezávislé na $ n$.

Při $ q=0$ se vypočte $ D_n$ jako člen geometrické posloupnosti $ D_n=p^{n-1}D_1$, kde $ D_1$ je determinant prvního řádu (často je to prvek determinantu $ D_n$ ležící v levém horním rohu). Nechť $ q \neq
0$ a $ \alpha, \beta$ jsou kořeny charakteristické rovnice $ x^2-px-q=0$. Pak $ p=\alpha+\beta$, $ q=-\alpha\beta$ a rovnici 46 můžeme vyjádřit jako:

$\displaystyle D_n-\beta D_{n-1}$ $\displaystyle =$ $\displaystyle \alpha\left(D_{n-1}-\beta D_{n-2}\right)$ (47)
$\displaystyle D_n-\alpha D_{n-1}$ $\displaystyle =$ $\displaystyle \beta\left(D_{n-1}-\alpha D_{n-2}\right)$ (48)

První případ: Nejprve budeme předpokládat, že $ \alpha\neq\beta$. Podle formule pro $ (n-1)$-ní člen geometrické posloupnosti najdeme z rovnic 47 a 48

$\displaystyle D_n-\beta D_{n-1}$ $\displaystyle =$ $\displaystyle \alpha^{n-2}\left(D_2-\beta D_1\right)$  
$\displaystyle D_n-\alpha D_{n-1}$ $\displaystyle =$ $\displaystyle \beta^{n-2}\left(D_2-\alpha D_1\right)$  

a odtud řešením soustavy dvou lineárních rovnic

$\displaystyle D_n=\frac{1}{\alpha-\beta}\big(\alpha^{n-1}\left(D_2-\beta
D_1\right)-\beta^{n-1}\left(D_2-\alpha D_1\right)\big)
$

neboli

$\displaystyle D_n=C_1\alpha^n+C_2\beta^n\,,\
 C_1=\frac{D_2-\beta D_1}{\alpha(\alpha-\beta)}\,,\
 C_2=\frac{D_2-\alpha D_1}{\beta(\alpha-\beta)}\,.$ (49)

Poslední výraz pro $ D_n$ se snadno pamatuje: všimněte si, jak se podobá obecnému řešení lineární diferenciální rovnice druhého řádu s konstantními koeficienty $ y(n)=C_1\mathop{\rm e}^{\lambda_1 n}\nolimits +C_2\mathop{\rm e}^{\lambda_2
n}\nolimits $. Vztah 49 je sice odvozen pro $ n>2$ ale platí i pro $ n=1,2$. Konstanty $ C_1,C_2$ lze proto nalézt jednoduše řešením soustavy

$\displaystyle D_1=C_1\alpha+C_2\beta\,,\quad D_2=C_1\alpha^2+C_2\beta^2\,.$

Druhý případ: Nechť nyní je $ \alpha=\beta\not=0$. Rovnosti 47 a 48 přejdou v jednu

$\displaystyle D_n-\alpha D_{n-1}=\alpha\left(D_{n-1}-\alpha D_{n-2}\right)\,,
$

a odtud

$\displaystyle D_n-\alpha D_{n-1}=A\alpha^{n-2}\,,$ (50)

kde $ A=D_2-\alpha D_1$.

Zaměníme $ n$ za $ n-1$, dostaneme $ D_{n-1}-\alpha
D_{n-2}=A\alpha^{n-3}$ a odtud $ D_{n-1}=\alpha
D_{n-2}+A\alpha^{n-3}$. Když dosadíme toto do 50, dostaneme $ D_n=\alpha^2D_{n-2}+2A\alpha^{n-2}$. Opakujeme tento postup ještě několikrát ($ (n-3)$-krát) a dostaneme $ D_n=\alpha^{n-1}D_1+(n-1)A\alpha^{n-2}$ nebo

$\displaystyle D_n=\alpha^n\big((n-1)C_1+C_2\big)\,,\quad
C_1=\frac{A}{\alpha^2}\,,\ C_2=\frac{D_1}{\alpha}\,.$

Konstanty $ C_1,C_2$ lze opět určit z rovnic $ D_1=\alpha C_2$, $ D_2=\alpha^2(C_1+C_2)$. Všimněte si opět podobnosti s řešením lineárních diferenciálních rovnic, například $ y''-2y'+y=0$.


Příklad 5.     Vypočteme rekuretní metodou determinant z příkladu 2.


Řešení: Představíme si prvek v pravém dolním rohu determinatu ve tvaru $ a_n=x+\left(a_n-x\right)$ a pak můžeme determinat napsat jako jako součet dvou determinantů:

$\displaystyle D_n=\left\vert\begin{array}{ccccc}
a_1 & x & x & \dots & x \cr
...
... \cr
x&x& &a_{n-1}&0\cr
x &x & \dots & x & a_n-x\cr
\end{array}\right\vert
$

V prvním determinantu odečteme poslední sloupec od ostatních, čímž dostaneme matici v horním trojúhelníkovém tvaru. Druhý determinant rozložíme podle posledního sloupce

$\displaystyle D_n=x\left(a_1-x\right) \left(a_2-x\right)\dots \left(a_{n-1}-x\right)+\left(a_n-x\right)D_{n-1}
$

To je rekurentní vztah. Po dosazení analogického výrazu pro $ D_{n-1}$
$\displaystyle D_n$ $\displaystyle =$ $\displaystyle x\left(a_1-x\right) \left(a_2-x\right)\dots \left(a_{n-1}-x\right)+$  
    $\displaystyle +\, x\left(a_1-x\right)
\left(a_2-x\right)\dots\left(a_{n-2}-x\right)(a_n-x)+$  
    $\displaystyle +\, D_{n-2}\left(a_{n-1}-x\right)\left(a_n-x\right)\,.$  

Opakujme toto $ (n-2)$-krát, a jelikož $ D_1=a_1=x+\left(a_1-x\right)$, dostaneme:
$\displaystyle D_n$ $\displaystyle =$ $\displaystyle x(a_1-x)(a_2-x)\dots(a_{n-1}-x)+$  
    $\displaystyle +\, x\left(a_1-x\right)\dots\left(a_{n-2}-x\right)\left(a_n-x\right)+$  
    $\displaystyle +\ \dots\ +x\left(a_2-x\right)\dots\left(a_n-x\right)+$  
    $\displaystyle +\, (a_1-x)(a_2-x)\dots(a_n-x)\,,$  

což odpovídá výsledku příkladu 2.


Příklad 6.     Máme spočítat determinant $ n$-tého řádu

$\displaystyle D=\left\vert\begin{array}{ccccc}
5 &3 & 0 & \dots & 0 \cr
2 &5 ...
...dots & & & \ddots&\vdots \cr
0 & 0 & 0& \dots &5 \cr
\end{array}\right\vert
$


Řešení: Rozložíme $ D$ podle první řádky a druhý sčítanec rozložíme dle prvního sloupce. Najdeme tak rekurentní vztah

$\displaystyle D_n=5D_{n-1}-6D_{n-2}\,.
$

Rovnice $ x^2-5x+6=0$ má kořeny $ \alpha=2$, $ \beta=3$, tedy očekáváme $ D_n=C_12^n+C_23^n$ (rovnice 49). Konstanty $ C_1,C_2$ určíme z rovnic $ D_1=5$, $ D_2=19$ a dostaneme (srovnejte s příkladem 8.2)

$\displaystyle D_n=C_1\alpha^n+C_2\beta^n=3^{n+1}-2^{n+1}\,.
$