Prijelaz iz rekurzivnog prikaza u prikaz općom formulom

20.01.2020. - Reading time: 13 minutes

Prikazati ćemo prijelaz iz rekurzivnog prikaza u prikaz općom formulom za linearne rekurzivne relacije s konstantnim koeficijentima.

To su relacije općeg oblika:

$$ a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + ... + c_{r}a_{n-r} + f(n), \qquad n\geq r \quad,$$

gdje je $r $ red relacije, $c_{1}, c_{2}, ... , c_{r}$ zadani realni koeficijenti ($c_{r} \neq 0$), a $f(n)$ je zadana funkcija koja prirodnim brojevima $n\geq r $ pridružuje realne brojeve. Niz $(a_{n})_{n \geq 0}$ je nepoznanica u ovoj rekurzivnoj relaciji.

Uočimo, $n$-ti član niza $(a_{n})$ određen je rekurzivno, s vrijednostima $r$ prethodnih članova.

Naš cilj je riješiti jednadžbu po $a_{n}$, tj. uz zadane početne uvjete $a_{0} , a_{1}, ... , a_{r-1}$ odrediti opći, $n$-ti član rekurzivno zadanog niza $(a_{n})$ kao eksplicitnu funkciju od $n$.

Linearne rekurzivne relacije s konstantnim koeficijentima dijelimo na homogene i nehomogene.

Linearna homogena rekurzivna relacija

Definicija: Rekurzivna relacija je homogena ako je $f(n) = 0$ za sve $n$, odnosno:

$$ a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + ... + c_{r}a_{n-r},\quad n\geq r $$

Do općeg rješenja ćemo doći tako da homogenu relaciju zapišemo pomoću Eulerove supstitucije:

$$ a_{n} = x^{n}.$$

Broj $x \neq 0$ ćemo odrediti uvrštavanjem u homogenu relaciju

$$ x^{n} = c_{1}x^{n-1} + c_{2}x^{n-2} + ... + c_{r}x^{n-r},\qquad n\geq r $$

Zatim dijelimo s $x^{n-r} \neq 0$

$$ x^{r} - c_{1}x^{r-1} - c_{2}x^{r-2} - ... - c_{r} = 0.$$

Dobili smo karakterističnu jednadžbu homogene rekurzivne relacije. To je polinom $r$-tog stupnja koji u skupu kompleksnih brojeva ima $r$ rješenja $x_{1}, x_{2}, ... , x_{r}$ (računajući i kratnost). S obzirom na ta rješenja razlikujemo dva slučaja:

1. Imamo $r$ različitih rješenja karakteristične jednadžbe

U ovom slučaju se opći član niza $a_{n}$ dobiva kao linearna kombinacija

$$a_{n} = \lambda_{1} x_{1}^{n} +\lambda_{2} x_{2}^{n}+...+\lambda_{r} x_{r}^{n}, \qquad n = 0 ,1, 2, ... $$

pri čemu koeficijente $\lambda_{1},\lambda_{2}, ... , \lambda_{r}$ računamo uz pomoć početnih vrijednosti $a_{0}, a_{1}, ... ,a_{r-1}$ kao linearni sustav $r$ linearnih jednadžbi s $r$ nepoznanica:

$$\lambda_{1}+\lambda_{2}+...+\lambda_{r} = a_{0}$$

$$\lambda_{1}x_{1}+\lambda_{2}x_{2}+...+\lambda_{r}x_{r} = a_{1}$$

$$\lambda_{1}x_{1}^{2}+\lambda_{2}x_{2}^{2}+...+\lambda_{r}x_{r}^{2} = a_{2}$$

$$\vdots$$

$$\lambda_{1}x_{1}^{r-1}+\lambda_{2}x_{2}^{r-1}+...+\lambda_{r}x_{r}^{r-1} = a_{r-1}$$

Primjer 1. Riješi rekurzivnu relaciju $a_{n} = 4a_{n-1} - a_{n-2} - 6a_{n-3}$ za $n \geq 3$ i početne vrijednost $a_{0} = 2$, $a_{1} = 1$ i $a_{2} = 5$.

Zadana je homogena rekurzivna relacija. Uvedimo supstituciju $a_{n} = x^{n}$ :

$$x^{n} = 4x^{n-1} - x^{n-2} - 6x^{n-3}$$

Podijelimo s $x^{n-3}$ i prebacimo sve na lijevu stranu:

$$x^{3} - 4x^{2} + x + 6 = 0$$

Rješenja karakteristične jednadžbe su: $x_{1}= -1, x_{2}= 2, x_{3}= 3$.

Dakle, opće rješenje je

$$a_{n} = \lambda_{1}(-1)^{n} + \lambda_{2}2^{n} +\lambda_{3}(3)^{n} .$$

Uvrštavanjem početnih vrijednosti u opće rješenje dobivamo sustav:

$$\lambda_{1}+\lambda_{2}+\lambda_{3} = 2$$

$$-\lambda_{1}+2\lambda_{2}+3\lambda_{3} = 1$$

$$\lambda_{1}+4\lambda_{2}+9\lambda_{3} = 5 .$$

Rješenje sustava je $\lambda_{1} = 1,\lambda_{2} = 1,\lambda_{3} = 0$.

Dakle, rješenje je:

$$a_{n} = (-1)^{n} + 2^{n}, \qquad n\geq 3 $$

2. Postoje višestruka rješenja karakteristične jednadžbe

Neka su $x_{1}, ..., x_{m}$ sva različita rješenja karakteristične jednadžbe homogene rekurzivne relacije, odgovarajućih kratnosti $k_{1}, ..., k_{m}$. Rješenje $a_{n}^{(i)}$ koje odgovara korijenu $x_i$ kratnosti $k_{i}$ je linearna kombinacija:

$$a_{n}^{(i)} = \lambda_{1}^{(i)}x_{i}^{n} + \lambda_{2}^{(i)}nx_{i}^{n}+...+\lambda_{k_{i}}^{(i)}n^{k_{i}-1}x_{i}^{n}, \qquad n\geq 0$$

Opće rješenje se tada dobiva kao:

$$a_{n} = a_{n}^{(1)} + ... + a_{n}^{(m)}$$

tj.

$$a_{n} = (\lambda_{1}^{(1)} + n\lambda_{2}^{(1)}+...+n^{k_{1}-1}\lambda_{k_{1}}^{(1)})x_{1}^{n}+$$

$$+(\lambda_{1}^{(2)} + n\lambda_{2}^{(2)}+...+n^{k_{2}-1}\lambda_{k_{2}}^{(2)})x_{2}^{n}+$$

$$\vdots$$

$$+(\lambda_{1}^{(m)} + n\lambda_{2}^{(m)}+...+n^{k_{m}-1}\lambda_{k_{m}}^{(m)})x_{m}^{n}$$

Koeficijente $\lambda_{1}^{(i)},...,\lambda_{k_{m}}^{(i)}$ računamo uvrštavanjem početnih vrijednosti u opće rješenje.

Primjer 2. Riješi rekurzivnu relaciju $a_{n}= 6a_{n-1}-9a_{n-2}$, $n \geq 2$, s početnim uvjetima $a_{0}=1$, $a_{1}=9$.

Uvedimo supstituciju $a_{n} = x^{n}$ :

$$x^{n}= 6x^{n-1}-9x^{n-2} .$$

Podijelimo s $x^{n-2}$ i prebacimo sve na lijevu stranu kako bi dobili karakterističnu jednadžbu

$$x^{2} + 6x + 9 = 0 .$$

Karakteristična jednadžba ima rješenje $x_{1} = 3$ kratnosti $k_{1}=2$.

Opće rješenje glasi:

$$a_{n}=a_{n}^{(1)}$$

$$a_{n}=\lambda_{1}^{(1)} \cdot 3^{n} + \lambda_{2}^{(1)} \cdot n\cdot 3^{n} .$$

Uvrštavanjem početnih vrijednosti u opće rješenje dobivamo sustav:

$$\lambda_{1}^{(1)} + \lambda_{2}^{(1)} \cdot 0 = 1$$

$$3\lambda_{1}^{(1)} + 3\lambda_{2}^{(1)} \cdot 1 = 9$$

Rješenje sustava je $\lambda_{1}^{(1)} = 1 , \lambda_{2}^{(1)} = 2 $

Dakle, rješenje je

$$a_{n}= 3^{n} + 2\cdot n\cdot 3^{n} .$$

Nehomogena rekurzivna relacija

Linearne nehomogene rekurzivne relacije s konstantnim koeficijentima su oblika:

$$ a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + ... + c_{r}a_{n-r} + f(n), \quad n\geq r $$

Opće rješenje nehomogene rekurzivne relacije je zbroj općeg rješenja pripadne homogene rekurzivne relacije ($a_{n}^{h}$) i partikularnog rješenja nehomogene rekurzivne relacije ($a_{n}^{p}$).

$$ a_{n} = a_{n}^{(h)} + a_{n}^{(p)}$$

Ovisno o obliku funkcije $f(n)$, postoje odgovarajući recepti za pronalaženje partikularnog rješenja:

Neodređene koeficijente u $a_{n}^{(p)}$ određujemo uvrštavanjem u zadanu rekurziju.

Primjer 3. Riješite rekurzivnu relaciju $a_{n} = 6a_{n-1} - 9a_{n-2}+ n \cdot 3^{n}, \quad a_{0} = 2, a_{1} = 3$

Pripadna homogena relacija zadane rekurzivne relacije je

$$a_{n}=6a_{n-1} - 9a_{n-2} .$$

Opće rješenje ove homogene relacije odredili smo u prethodnom primjeru

$$a_n^{(h)}=\lambda_{1} \cdot 3^{n}+n \cdot \lambda_2 \cdot 3^{n} .$$

U zadanoj nehomogenoj rekurzivnoj relaciji $f(n) = n \cdot 3^{n}$ što je funkcija oblika $C \cdot n^m \cdot b^n$. Slijedimo upute iz ranije opisanog recepta za dobivanje partikularnog rješenja (Vidimo da 3 je rješenje pripadne karakteristične jednadžbe). Partikularno rješenje je oblika

$$a_n^{(p)} = n^2 \cdot (an+b) \cdot 3^n .$$

Uvrštavanjem $a_n^{(p)} = n^2 \cdot (an+b) \cdot 3^n$ u zadanu rekurziju $a_{n} = 6a_{n-1} - 6a_{n-2}+ n \cdot 3^{n}$ imamo:

$$ n^{2} \cdot(a n+b) \cdot 3^{n} = 6 \cdot(n-1)^{2} \cdot(a(n-1)+b) \cdot 3^{n-1}-9 \cdot (n-2)^{2} \cdot(a(n-2)+b)\cdot 3^{n-2}+n \cdot 3^{n} \qquad/: 3^{n} $$

$$ n^{2} \cdot(a n+b) = 2 \cdot\left(n^{2}-2 n+1\right)(a n-a+b)-\left(n^{2}-4 n+4\right) \cdot(a n-2 a+b)+n $$

$$ (1 - 6a)n + (6a - 2b) = 0 $$

$$ (1 - 6a)n + (6a - 2b) = 0 \cdot n + 0 $$

Izjednačavajući koeficijente s lijeve i desne strane jednakosti dobivamo $a = \frac{1}{6}$, $b = \frac{1}{2}$.

Partikularno rješenje je:

$$ a_{n}^{(p)}=n^{2} \cdot\left(\frac{1}{6} n+\frac{1}{2}\right) \cdot 3^{n} $$

Opće rješenje zadane nehomogene rekurzivne relacije

$$ a_{n} = a_{n}^{(h)} + a_{n}^{(p)}$$

$$ a_{n}=\lambda_{1} \cdot 3^{n}+n \cdot \lambda_{2} \cdot 3^{n}+n^{2} \cdot\left(\frac{1}{6} n+\frac{1}{2}\right) \cdot 3^{n} $$

$$ a_{n}=3^{n}\left(\lambda_{1}+n \cdot \lambda_{2}+\frac{1}{6} n^{3}+\frac{1}{2} n^{2}\right)$$

Uvrstimo početne vrijednosti $a_{0} = 2, a_{1} = 3$.

Dobivamo $\lambda_1 = 2, \lambda_2 = - \frac{5}{3}$.

Konačno, uz malo sređivanja, dobivamo rješenje

$$ a_{n}=\frac{3^{n-1}}{2}\left(n^{3}+3 n^{2}-10 n+12\right) .$$

Zadaci za vježbu

1. Riješite rekurzivnu relaciju $a_{n+1} = a_{n} + 6n$, $a_1 = 1$.

(Rješenje: $a_n = 3n^2 - 3n + 1$)

2. Riješite rekurzivnu relaciju $a_{n+1} = 2a_{n} + 1$, $a_1 = 2$.

(Rješenje: $a_n = 3 \cdot 2^{n-1} - 1$)

3. Riješite rekurzivnu relaciju $a_n = 2a_{n-1} + a_{n-2} - 2a{n-3}$ , $a_0 = 1$, $a_1 = 2$, $a_2 = 3$.

(Rješenje: $a_n = \frac{(-1)^n}{6}+\frac{1}{2}+\frac{2^n}{3}$)

4. Riješite rekurzivnu relaciju $a_n - 7a_{n-1} + 15a_{n-2} - 9a_{n-3} = 0$ , $a_0 = 1$, $a_1 = 2$, $a_2 = 3$.

(Rješenje: $a_n = (1 - \frac{n}{3}) \cdot 3^n$)

5. Riješite rekurzivnu relaciju $a_{n+1} - 5a_n = 4n^2 + 2n + 6$ , $a_1 = 1$.

(Rješenje: $a_n = 5^n - n^2 - n - 2$)

6. Riješite rekurzivnu relaciju $a_n - 3a_{n-1}+2a_{n-2} = 2^n$ , $a_0 = 2$, $a_1 = 8$.

(Rješenje: $a_n = (2n+1)\cdot 2^n + 2$)

Literatura

D. Žubrinić, Matematika 3 Uvod u diskretnu matematiku, Element, Zagreb, 2006.
Materijali iz kolegija Kombinatorna i diskretna matematika : https://web.math.pmf.unizg.hr/nastava/kidm/rekurzije.pdf, Pristupljeno 9.11.2019.

Citiraj

Novak, Siniša (20.01.2020.). Prijelaz iz rekurzivnog prikaza u prikaz općom formulom. Sustav. Preuzeto s https://sustav.sino.com.hr/prijelaz-iz-rekurzivnog-u-prikaz-opcom-formulom ()