Matematické Fórum

Alan122

Dobrý večer.

Tak som sa dnes trochu hral s postupnosťami a skúšal z rekurentného vyjadrenia postupnosti získať postupnosť danú vzorcom pre n-tý člen. Ak použijem postup pri ktorom si vypíšem zopár členov potom sformulujem hypotézu a indukciou ju overím tak nie je problém. Zamýšľal som sa ale nad postupom, ktorý by sa vyhol indukcii. Prišiel som na taký postup v prípade, že mám postupnosť danú rekurentne v tvare a_(n+1) = c.a_(n) kde c je nejaká konštanta a a1=k kde k je tiež konštanta. Podobne ak mám a_(n+1) = c + a_(n). Členy som medzi sebou vhodne ponásobil alebo posčítaval. Podobný postup sa mi však nedarilo nájsť v prípade, že som mal zadaný napr. takýto tvar a_(n+2)=c.a_(n+1) + a(n) (stále pre zadané a1,a2), prípadne a_(n+1) = c - a_(n) a analogické prípady.

Skrátka moja otázka znie či vôbec v tých ďalších mnou opísaných príkladoch sa indukcii dá nejak šikovne vyhnúť alebo nie, predsa len prijde mi to krajšie bez indukcie :) ďakujem

Olin · 26. 09. 2011 22:26

Existuje metoda, jak takovéto rekurence převádět do explicitních vzorců. Stručně nastíním: mějme posloupnost zadanou vztahem

$a_{n+2} + r a_{n+1} + s a_n = 0 \qquad(\spadesuit)$ .

Předpokládejme, že řešení bude ve tvaru $a_n = \lambda^n$ , kde $\lambda$ je nějaká konstanta (komplexní, bohužel nemusí být reálná, jak se ukáže). Potom musí jistě $\lambda$ splňovat

$\lambda^{n+2} + r\lambda^{n+1} + s\lambda^n = 0$

a po pokrácení $\lambda^n$ (nulové řešení nás v tuto chvíli nezajímá) dostaneme kvadratickou rovnici

$\lambda^2 + r \lambda + s = 0$ .

Pokud má dva různé kořeny $\lambda_1, \lambda_2$ , tak řešení rovnice $(\spadesuit)$ budou ve tvaru $K_1 \lambda_1^n + K_2 \lambda_2^n$ , kde $K_1, K_2$ jsou nějaké (komplexní) konstanty. Pokud má rovnice jeden dvojnásobný kořen, je situace složitější (pak místo $\lambda_2^n$ bude $n \lambda_1^n$ ).

Příklad: Fibbonaciho posloupnost je zadaná rekurentním vzorcem $F_{n+2} = F_{n+1} + F_n$ , přičemž $F_1 = F_2 = 1$ . Řešíme tedy rovnici

$\lambda^2 = \lambda + 1$ ,

jejíž kořeny jsou $\lambda_1 = \tfrac{\sqrt{5}+1}{2}$ , $\lambda_2 = \tfrac{-\sqrt{5}+1}{2}$ . Kořeny jsou různé, bude tedy platit $F_n = K_1\lambda_1^n + K_2\lambda_2^n$ , zbývá jen najít hodnoty konstant $K_1, K_2$ . Naštěstí známe první dvě hodnoty posloupnosti (jinak bychom ty konstanty najít nemohli), takže máme soustavu

$F_1 = 1 &= K_1\tfrac{\sqrt{5}+1}{2} + K_2\tfrac{-\sqrt{5}+1}{2}\\ F_2 = 1 &= K_1\left(\tfrac{\sqrt{5}+1}{2}\right)^2 + K_2\left(\tfrac{-\sqrt{5}+1}{2}\right)^2$ .

Když se to vyřeší (nejlépe strojově), dostaneme výsledky $K_1 = \tfrac{1}{\sqrt{5}}$ , $K_2 = -\tfrac{1}{\sqrt{5}}$ , takže konečný výsledek je

$F_n = \frac{1}{\sqrt{5}} \left [\left(\tfrac{\sqrt{5}+1}{2}\right)^n - \left(\tfrac{-\sqrt{5}+1}{2}\right)^n \right ]$ .

Něco se o tom dá vyčíst třeba zde, pak existuje ještě hromada dalších materiálů, ty jsou ovšem vesměs vysokoškolské.