Рекурзивна функција решава одређени задатак позивајући своју копију. Пример проблема решаваног рекурзијом су „Куле Ханоја“. Ханојске куле су три штапа (A, B и C) и n дискова. У почетку сви дискови су на штапу A, наслагани одозго на доле по растућој величини. Циљ слагалице је премештати дискове један по један да је увек мањи изнад већег и на крају имати их све на шипки C.

Kule Hanoja

Горња слика приказује решење проблема Ханојских кула са n = 3 диска у 7 потеза.

1. Линеарна

Општа линеарна рекурзивна релација је

xn = c1xn-1 + c2xn-2 + ... + ckxn-k

са константним коефицијентима c1, c2, ..., ck и варијаблама xn, xn-1, ..., xn-k при чему индекси узимају вредности целих бројева, обично n = 0, 1, 2, 3, ..., а тада k = 1, 2, ..., n-1.

1.1. Пример. Дато је x1 = 5 и xn = 5xn-1. Тиме је x2 = 52, x3 = 53 и уопште xn = 5n. □

Водећи се за овим примером (1.1), налазимо уобичајено решење опште линеарне рекурзије помоћу геометријских низова, у облику xn = arn, где су a и r неке константе. Сменом, налазимо:

arn = c1arn-1 + c2arn-2 + ... + ckarn-k,

rk = c1rk-1 + c2rk-2 + ... + ck,

rk - c1rk-1 - c2rk-2 - ... - ck = 0,

а то је полином по непознатој r. Дакле, решење дате рекурзије задовољава је само када је корен овог карактеристичног полинома рекурзије. Разликујемо ову карактеристичну једначину са различитим коренима (1.2), од корена који се понављају (1.4) и од корена комплекснх бројева (1.5), мада су исте форме.

1.2. Пример. Почетни услови су x1 = 6, x2 = 3 и xn = xn-1 + 2xn-2 за све n > 2. Израчунавамо:

x3 = x2 + 2x1 = 3 + 2⋅6 = 15,
x4 = x3 + 2x2 = 15 + 2⋅3 = 21,
x5 = x4 + 2x3 = 21 + 2⋅15 = 51,
...

Међутим, ми тражимо и експлицитно xn = f(n), функцију самог броја n ∈ ℕ.

Решење: Дата линеарна рекурзивна једначину има карактеристичну једначину

r² - x - 2 = 0

чија су решења r1,2 ∈ {2, -1}. Отуда је опште решење тражене рекурзије

xn = β1(2)n + β2(-1)n,

са произвољним константама β1 и β2. Константе одређују почетни услови:

x1 = 2β1 - β2 = 6,
x2 = 4β1 + β2 = 3.

Сабирање ове две једнакости даје 6β1 = 9, а множење прве са -2 па сабирање са другом даће 3β2 = -9. Према томе

xn = 1,5⋅2n - 3⋅(-1)n

је коначно решење. Проверавамо x1 = 1,5⋅21 - 3⋅(-1) = 6 и x2 = 1,5⋅22 - 3⋅(-1)2 = 3, затим:

x3 = 1,5⋅23 + 3 = 15,
x4 = 1,5⋅24 - 3 = 21,
x5 = 1,5⋅25 + 3 = 51,
...

а то је тачно. Погледајте и решење методом својствених величина у наставку (пример 2.2). □

Тешкоће око решавања рекурзија долазе из (не)могућности налажења нула, корена полинома, као што видимо, нарочито код дужих израза и полинома виших степена. У тим тежим случајевима довијамо се како знамо, јер за решење једначине полинома већег степена од петог нема готове формуле попут оне добро нам познате за квадратну.

1.3. Пример. Наћи рекурзију xn = 2xn-1 + xn-2 - 2xn-3, са почетним условима x0 = 2, x1 = 2 и x2 = 4. То је низ бројева; израчунавамо их један по један:

x3 = 2⋅4 + 2 - 2⋅2 = 6,
x4 = 2⋅6 + 4 - 2⋅2 = 12,
x5 = 2⋅12 + 6 - 2⋅4 = 22,
...

Решење: Кубну карактеристичну једначина ове рекурзије растављамо на факторе и налазимо корене:

r³ - 2r² - r + 2 = 0,

(r + 1)(r - 1)(r - 2) = 0,

r1 = -1,   r2 = 1,   r3 = 2.

Опште решење је линеарна комбинација:

xn = β1(r1)n + β2(r2)n + β3(r3)n,

xn = β1(-1)n + β2(1)n + β3(2)n.

На основу почетних услова формирамо три једначине за непознате константе, три бете:

x0 = β1 + β2 + β3 = 2,
x1 = -β1 + β2 + 2β3 = 2,
x2 = β1 + β2 + 4β3 = 4.

Решење овог система су бројеви β1 = 1/3, β2 = 1 и α3 = 2/3. Знајући их, то је затим лако проверавати уврштавањем у дати систем. Према томе, експлицитно решење дате рекурзије је

\[ x_n = \frac13\cdot(-1)^n + 1 + \frac23\cdot 2^n, \quad n = 0, 1, 2, ... \]

Проверавамо редом, почетне x0 = 2, x1 = 2, x2 = 4, а онда и следеће x3 = 6, x4 = 12, x5 = 22, ... . Решење истог задатка својственим величинама је у наставку (пример 2.3). □

Општи метод решавања линеарних рекурзија са поновљеним коренима можемо елаборисати у четири корака. Прво, налазимо карактеристични полином степена k. Друго, налазимо све различите корене r1, r2, ..., rm, где је mk, који се понављају редом s1, s2, ..., sm пута. Треће, решења су линеарна комбинација свих низа чланова облика njrin где је 0 ≤ jsi - 1 и 1 ≤ im. Четврто, користимо почетне вредности да нађемо константе решења. Ево примера.

1.4. Пример. Почетни услови су x0 = a и x1 = b, а xn = 6xn-1 - 9xn-2 (∀n ≥ 2). Треба наћи xn.

Решење: Линеарна рекурзивна једначину има карактеристичну једначину

r² - 6r + 9 = 0,

са двоструким решењем r1 = r2 = 3. Да је un = 3n једно решење видимо из следећег:

3n = 6⋅3n-1 - 9⋅3n-2,

3n = 2⋅3n - 3n,

3n = 3n,

што је тачно. Да је vn = n⋅3n друго решење видимо из:

n⋅3n = 6(n - 1)3n-1 - 9(n - 2)3n-2,

n⋅3n = 2(n - 1)3n - (n - 1)3n,

n⋅3n = (2n - 2 - n + 2)3n,

n⋅3n = n⋅3n,

што је такође тачно. Онда је опште решење линеарна комбинација ова два:

xn = β1un + β2vn,

xn = β1⋅3n + β2n⋅3n,

xn = (β1 + 2)3n.

Из почетних услова лако налазимо константе β1 = a и β2 = b/3 - a. □

Решавање линеарне рекурзије са коренима који су комплексни бројеви једнако сводимо на претходне случајеве, а затим даље и на тригонометријске функције. Демонстрираћу то примером.

1.5. Пример. Решити у xn = xn-1 - xn-2 (∀n ≥ 2) са почетним условима x0 = x1 = 1.

Решење: Линеарна рекурзивна једначину има карактеристичну једначину

r² - r + 1 = 0

чија су решења

\[ r_{1,2} = \frac{1 \pm i\sqrt{3}}{2} = e^{\pm i\theta}, \quad \theta = 60^\circ, \]

где користимо Ојлерову формулу e = cos θ + i sin θ. Уопште, израчунавамо:

\[ r_{1,2} = a \pm ib = \sqrt{a^2 + b^2} \left(\frac{a}{\sqrt{a^2 + b^2}} + i\frac{b}{\sqrt{a^2 + b^2}}\right), \] \[ r_{1,2} = \rho e^{\pm i\theta}, \quad \rho = \sqrt{a^2 + b^2}, \quad \text{tg}\,\theta = \frac{b}{a}. \]

Решења рекурзије пишемо као линеарну комбинацију ових:

xn = β1ρn⋅cos() + β2ρn⋅sin(),   n = 0, 1, 2, ...,

а у овом задатку је ρ = 1 и θ = 60°. Користећи почетне услове налазимо:

\[ \begin{cases} x_0 = \beta_1\cos(0) + \beta_2\sin(0) = 1 \\ x_1 = \beta_1 \cos(60^\circ) + \beta_2\sin(60^\circ) = 1 \end{cases} \]

па је β1 = 1 и β2 = 1/√3. □

2. Својствене величине

Метода својствених вредности-вектора такође се користи за решавање линеарних рекурзија (Mellon College). Изнећу је сасвим укратко и понављајући неколико прошлих задатака ради лакшег поређења решавањем претходним и овим поступком.

2.1. Нека је опет дата општа линеарна рекурзивна једначина

xn = c1xn-1 + c2xn-2 + ... + ckxn-k,

где је n = 0, 1, 2, ..., k = 1, 2, ..., n - 1, xi су променљиве вредности, а ci су константе. Посматрајмо векторе:

\[ \textbf{y}_n = \begin{pmatrix} x_{n-1} \\ x_{n-2} \\ \vdots \\ x_{n-k+1} \end{pmatrix}, \quad \textbf{y}_{k-1} = \begin{pmatrix} x_{k-1} \\ x_{k-2} \\ \vdots \\ x_0 \end{pmatrix}, \]

где први садржи променљиве, а други почетне вредности рекурзивне једначине. Сада ту једначину можемо писати матрично yn+1 = Ayn, са матрицом

\[ A = \begin{pmatrix} c_1 & c_2 & c_3 & ... & c_{k-1} & c_k \\ 1 & 0 & 0 & ... & 0 & 0 \\ 0 & 1 & 0 & ... & 0 & 0 \\ \vdots & & & \vdots & & \\ 0 & 0 & 0 & ... & 1 & 0 \end{pmatrix}. \]

Претпоставимо да се A може дијагонализирати и да су (λi, vi) парови одговарајућих својствених вредности и вектора, Avi = λivi. Напишимо вектор почетних вредности као линеарну комбинацију својствених

yk-1 = β1v1 + βv2 + ... + βkvk,

где су β1, β2, ..., βk константе линеарног развоја. Како је yn = An-k+1yk-1, односно:

yn = An-k+1yk-1 = An-k+1(β1v1 + βv2 + ... + βkvk),

yn = β1λ1n-k+1v1 + β2λ2n-k+1v2 + ... + βkλkn-k+1vn.

Примећујући да је променљива xn прва координата вектора yn, можемо очитати прву координату вектора и добити формулу за xn.

2.2. Пример. Рекурзија је xn = xn-1 + 2xn-2, са почетним вредностима x1 = 6 и x2 = 4 (пример 1.2).

Решење: Посматрамо векторе:

\[ \textbf{y}_n = \begin{pmatrix} x_{n-1} \\ x_{n-2} \end{pmatrix}, \quad \textbf{y}_2 = \begin{pmatrix} 3 \\ 6 \end{pmatrix}, \]

први чије су компоненте променљиве рекурентног низа, а други са њиховим почетним вредностима. Сада дату једначину пишемо yn+1 = Ayn, са матрицом

\[ A = \begin{pmatrix} 1 & 2 \\ 1 & 0 \end{pmatrix} \]

са својственим вредностима λ1 = -1 и λ2 = 2, и одговарајућим својственим векторима:

\[ \textbf{v}_1 = \begin{pmatrix} 1 \\ -1 \end{pmatrix}, \quad \textbf{v}_2 = \begin{pmatrix} 2 \\ 1 \end{pmatrix}, \]

што је лако проверити непосредним множењем (Av = λv). Вектор почетних вредности представљамо линеарном комбинацијом ових својствених и израчунавамо константе β1 и β2:

y2 = β1v1 + β2v2,

\[ \begin{pmatrix} 3 \\ 6 \end{pmatrix} = \beta_1 \begin{pmatrix} 1 \\ -1 \end{pmatrix} + \beta_2 \begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} \beta_1 \\ \beta_2 \end{pmatrix}, \] \[ \begin{pmatrix} \beta_1 \\ \beta_2 \end{pmatrix} = \frac13\begin{pmatrix} 1 & -2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 3 \\ 6 \end{pmatrix} = \begin{pmatrix} -3 \\ 3 \end{pmatrix}. \]

Множили смо инверзном матрицом и добили β1 = -3 и β2 = 3, односно y2 = -3v1 + 3v2. Отуда:

yn = An-2y2 = An-2(-3v1 + 3v2) = -3(λ1)n-2v1 + 3(λ2)n-2v2 = -3(-1)n-2v1 + 3(2)n-2v2,

\[ \begin{pmatrix} x_{n-1} \\ x_{n-2} \end{pmatrix} = 3(-1)^{n-2}\begin{pmatrix} 1 \\ -1 \end{pmatrix} + 3(2)^{n-2}\begin{pmatrix} 1 \\ 1 \end{pmatrix}, \]

па је xn = 3(-1)n-1 + 3⋅2n-1 тражено решење. Провера:

x1 = 3 + 3 = 6,
x2 = -3 + 3⋅2 = 3,
x3 = 3 + 3⋅4 = 15,
x4 = -3 + 3⋅8 = 21,
x5 = 3 + 3⋅16 = 51,
...

што је тачно. □

Својствене парове можемо израчунавати компјутером (kod.eigen), помоћу детерминанте и решавањем својствених једначина, или дијагонализацијом развојем дате помоћним матрицама. У примеру тај део прескачем као елементарну ствар и остављам читаоцу да бира методу. Уосталом, такав је резултат лако проверљив непосредним множењем (Av = λv), када је већ наведен.

2.3. Пример. Решити xn = 2xn-1 + xn-2 - 2xn-3 за почетне вредности x0 = 2, x1 = 2 и x2 = 4 (пример 1.3).

Решење: Посматрамо векторе:

\[ \textbf{y}_n = \begin{pmatrix} x_{n-1} \\ x_{n-2} \\ x_{n-3} \end{pmatrix}, \quad \textbf{y}_3 = \begin{pmatrix} 4 \\ 2 \\ 2 \end{pmatrix}, \]

где први садржи променљиве, а други почетне вредности дате рекурзивне једначине. Сада ту једначину можемо писати матрично yn+1 = Ayn, или детаљније

\[ \begin{pmatrix} x_{n} \\ x_{n-1} \\ x_{n-2} \end{pmatrix} = \begin{pmatrix} 2 & 1 & -2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} x_{n-1} \\ x_{n-2} \\ x_{n-3} \end{pmatrix}. \]

Како је y3 први вектор, биће yn+1 = An-2y3, па то можемо представљати дијагонализацијом, помоћу својствених вектора матрице. Налазимо (λi, vi) парове својствених вредности-вектора. Векторима:

\[ \textbf{v}_1 = \begin{pmatrix} 1 \\ -1 \\ 1 \end{pmatrix}, \quad \textbf{v}_2 = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, \quad \textbf{v}_3 = \begin{pmatrix} 4 \\ 2 \\ 1 \end{pmatrix} \]

одговарају редом својствене вредности λ1 = -1, λ2 = 1 и λ3 = 2. Формирамо линеарну комбинацију својствених вектора као вектор почетних вредности:

y3 = β1v1 + β2v2 + β3v3,

\[ \begin{pmatrix} 4 \\ 2 \\ 2 \end{pmatrix} = \beta_1\begin{pmatrix} 1 \\ -1 \\ 1 \end{pmatrix} + \beta_2\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} + \beta_3\begin{pmatrix} 4 \\ 2 \\ 1 \end{pmatrix}. \]

Добијамо систем линеарних једачина:

\[ \begin{cases} \beta_1 + \beta_2 + 4\beta_3 = 4 \\ -\beta_1 + \beta_2 + 2\beta_3 = 2 \\ \beta_1 + \beta_2 + \beta_3 = 2 \end{cases} \]

са решењима тражених константи β1 = 1/3, β2 = 1 и β3 = 2/3. Отуда:

yn = An-2y3 = An-2(β1v1 + β2v2 + β3v3) =

= An-2(v1/3 + v2 + 2v3/3)

= An-2v1/3 + An-2v2 + 2An-2v3/3

= (λ1)n-2v1/3 + (λ2)n-2v2 + 2(λ3)n-2v3/3

= (-1)n-2v1/3 + (1)n-2v2 + 2(2)n-2v3/3,

\[ \begin{pmatrix} x_n \\ x_{n-1} \\ x_{n-2} \end{pmatrix} = \frac13(-1)^{n-2}\begin{pmatrix} 1 \\ -1 \\ 1 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} + \frac23 \cdot 2^{n-2}\begin{pmatrix} 4 \\ 2 \\ 1 \end{pmatrix}, \]

xn = (-1)n/3 + 1 + 2n⋅2/3,   n = 0, 1, 2, ...

што је коначно решење задатка. □

Када је нека својствена вредност матрице A, рецимо λ1, многострукости рецимо d1 = 1, 2, 3, ..., онда постоји бесконачно много својствених вектора који јој одговарају. Такав је v1 и бар сваки добијен множењем овога неким бројем. Када одбацимо нулти вектор, за скуп свих својствених вектора λ1 добићемо векторски простор, ознаке E1, који се зове својствени простор својствене вредности λ1, димензије не веће од броја понављања λ1 те матрице. Дакле, димензија својственог простора E1 највише је d1.

Следећи својствени вектор vk својствене вредности λ1 многострукости d1 простора E1 задовољава релацију (A - λ1I)vk = vk-1 корацима, редом од 1 до d1, када је познат претходни vk-1. Међутим, има других начина за разапињање простора E1. Нешто од тога можете и сами, рецимо поредећи ову са претходном методом (пример 1.4), али то је посебна тема.

3. Системи рекурзија

Системе рекурзивних једначина често решавамо хеуристичи, од случаја до случаја као у следећем примеру (3.1).

3.1. Пример. Решити линеарни систем рекурзивних једначина:

xn = 5xn-1 + 2yn-1
yn = 4yn-1 + xn-1

са почетним условима x0 = 2 и y0 = 1.

Решење: Уврштавајући почетне услове и даље, налазимо једну по једну компоненту ових низова:

(x1 = 12 и y1 = 6), (x2 = 72 и y2 = 36), (x3 = 432 и y3 = 216), ...

Међутим, требају нам и опште формуле облика xn = f(n) и yn = g(n), где су чланови два низа функције самог броја n = 0, 1, 2, ... . Стога сабирањем једначина налазимо:

xn + yn = 6(xn-1 + yn-1) = ... = 6n(x0 + y0) = 3⋅6n-1.

То користимо у систему и израчунавамо:

xn - 3xn-1 = 2(xn-1 + yn-1) = 2⋅(3⋅6n-1) = 6n
yn - 3yn-1 = yn-1 + xn-1 = 3⋅6n-1 = 6n/2.

Затим сабирамо разлике са опадајућим индексима:

xn = (xn - 3xn-1) + 3(xn-1 - 3xn-2) + ... + 3n-1(x1 - 3x0) + 3nx0 =
= [(6n) + (3⋅6n-1) + ... + (3n-1⋅6) + 3n] + 3n
= [(6n+1 - 3n+1)/(6 - 3)] + 3n,
xn = 2⋅6n,

yn = (yn - 3yn-1) + 3(yn-1 - 3yn-2) + ... + 3n-1(y1 - 3y0) + 3ny0 =
= (6n/2) + 3(6n-1/2) + ... + 3n-1(6/2) + 3n
= (6n + 3⋅6n-1 + ... + 3n-1⋅6 + 3n]/2 + 3n/2
= (2⋅6n - 3n)/2 + 3n/2,
yn = 6n.

Дакле xn = 2⋅6n и yn = 6n. Проверу остављам читаоцу. □

Познајући решења лако је за њих састављати различите задатке рекурзија, као и решавати исте задатке различитим методама. Уочавамо принципијелну разноликост неопходну (мојој) теорији информације, па ћемо исти (3.1) задатак решити матричном методом.

3.2. Пример. Решавамо рекурзију дату матричном једначином zn = Azn-1, прецизније

\[ \begin{pmatrix} x_n \\ y_n \end{pmatrix} = \begin{pmatrix} 5 & 2 \\ 1 & 4 \end{pmatrix} \begin{pmatrix} x_{n-1} \\ y_{n-1} \end{pmatrix}, \]

матричном методом. Почетни услови су вектор z0 = (2, 1).

Решење: Узастопном применом датог налазимо zn = Az0. Дакле, задатак се своди на налажење степена дате матеице. Стога, налазимо својствене вредности λ1 = 6 и λ2 = 3 матрице и одговарајуће својствене векторе:

\[ \textbf{v}_1 = \begin{pmatrix} 2 \\ 1 \end{pmatrix}, \quad \textbf{v}_2 = \begin{pmatrix} -1 \\ 1 \end{pmatrix}, \]

иначе парове дефинисане карактеристичном једначином Av = λv.

Зна се, ови вектори су колоне помоћне матрице P = P[v1, v2] такве да је A = PDP-1, где је D дијагонална матрица са својственим вредностима дате на дијагонали, а P-1 инверзна помоћној. Заиста

\[ \begin{pmatrix} 5 & 2 \\ 1 & 4 \end{pmatrix} = \begin{pmatrix} 2 & -1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 6 & 0 \\ 0 & 3 \end{pmatrix} \begin{pmatrix} \frac13 & \frac13 \\ -\frac13 & \frac23 \end{pmatrix}, \]

што је лако проверити. Због A² = (PDP-1)(PDP-1) = PD²P-1 и даље индуктивно, је An = PDnP-1, што је:

\[ \begin{pmatrix} 5 & 2 \\ 1 & 4 \end{pmatrix}^n = \begin{pmatrix} 2 & -1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 6^n & 0 \\ 0 & 3^n \end{pmatrix} \begin{pmatrix} \frac13 & \frac13 \\ -\frac13 & \frac23 \end{pmatrix} = \] \[ = \frac13 \begin{pmatrix} 2\cdot 6^n + 3^n & 2\cdot 6^n - 2\cdot 3^n \\ 6^n - 3^n & 6^n + 2\cdot 3^n \end{pmatrix}. \] \[ \begin{pmatrix} x_n \\ y_n \end{pmatrix} = \begin{pmatrix} 5 & 2 \\ 1 & 4 \end{pmatrix}^n \begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 2\cdot 6^n \\ 6^n \end{pmatrix}. \]

Дакле, решења су xn = 2⋅6n и yn = 6n, идентична претходном задатку. □

3.3. У недавном блогу (Pest) користио сам ову методу. Приметимо да матрична рекурзија, zn = Azn-1, без обзира којег је реда m била квадратна матрица A, можемо решавати помоћу својствених вредности те матрице. Укратко, тада налазимо

\[ \textbf{z}_n = \beta_1(\lambda_1)^n\textbf{v}_1 + \beta_2(\lambda_2)^n\textbf{v}_2 + ... + \beta_m (\lambda_m)^n \textbf{v}_m, \]

где су βk, индекса редом k = 1, 2, ..., m, константе које зависе од почетних услова, а λk су својствене вредности матрице A и vk и њима одговарајући својствени вектори. Да сваки од ових сабирака заиста задовољава дату једначину лако проверавамо:

zn = βλnv,   zn-1 = βλn-1v,
βλnv = βλn-1Av,
zn = Azn-1,

а онда је решење и линеарна комбинација ових.

4. Посебне рекурзије

У посебне примере убрајам нарочито познате какви су неки историјски низови, али и нелинеарне једначине које се решавају од случаја до случаја, хеуристички.

4.1. Фибоначијев низ дефинисан је са:

Fn = Fn-1 + Fn-2,     F0 = 0,   F1 = 1.

За неколико следећих чланова налазимо F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, ... и тражимо општи члан. Метода полинома (пример 1.2) даће:

r² - r - 1 = 0,

\[ r_{1,2} = \frac{1 \pm \sqrt{5}}{2} = \begin{cases} r_1 = \varphi, & \varphi = \frac{\sqrt{5} - 1}{2} \\ r_2 = -\psi, & \psi = \frac{\sqrt{5} - 1}{2} \end{cases} \]

Већи од ових бројева (φ = 1,61803...) је „златни пресек“, или подела дужи таква да се цела односи према већем делу као већи према мањем. Мањи од „пресека“ је реципрочан том (ψ = 1/φ = 0,61803...). Опште решење је линеарна комбинација

Fn = β1(r1)n + β2(r2)n,

из којег, примењујући га на почетне услове:

β1 + β2 = 0
β1φ - β2ψ = 1

налазимо β1 = 1/√5 и β2 = -1/√5. Коначно, општи члан Фибоначијевог низа је

\[ F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}. \]

4.2. Бинарни Марков ланац је преносник дво-компонентне поруке, попут „има-нема“ струје струјног кола, који у k-том кораку јавља да „стања има“ вероватноћом pk ∈ (0, 1) и да га „нема“ вероватноћом која прву допуњава до јединице, qk = 1 - pk. Матрица ланца је стохастичка, јер су јој и колоне бинарне расподеле вероватноћа (a, b ≥ 0 и a + b = 1), а дупла је стохастичка ако су такве и врсте, као у следећем случају (yn = Myn-1):

\[ \begin{pmatrix} p_n \\ q_n \end{pmatrix} = \begin{pmatrix} a & b \\ b & a \end{pmatrix} \begin{pmatrix} p_{n-1} \\ q_{n-1} \end{pmatrix}. \]

Број a је условна вероватноћа, да ће послати сигнал бити тачно пренешен, док је b таква вероватноћа да неће. Тако је apk-1 вероватноћа да ће први сигнал проћи k-ти корак ланца као први сигнал, дочим је bqk-1 вероватноћа да ће и други изћи као други. Напротив, bpk-1 и aqk-1 су шансе њихове промене. То је смисао система једначина карике ланца:

\[ \begin{cases} p_n = ap_{n-1} + bq_{n-1} \\ q_n = bp_{n-1} + aq_{n-1} \end{cases} \]

који има исто значење као претходна матрична.

Две су својствене вредности матрице канала, λ1 = 1 и λ2 = a - b, са припадним својственим векторима:

\[ \textbf{v}_1 = \begin{pmatrix} \frac12 \\ \frac12 \end{pmatrix}, \quad \textbf{v}_2 = \begin{pmatrix} \frac12 \\ -\frac12 \end{pmatrix}, \]

где подразумевамо ab ≠ 0. Тада је опште решење ове рекурзије:

yn = β11)nv1 + β22)nv2,

yn = β1v1 + β2(a - b)nv2.

\[ \begin{cases} p_n = \frac12 + \frac12 \beta (a-b)^n \\ q_n = \frac12 - \frac12 \beta (a-b)^n \end{cases} \]

са константом β, тако да је резултат увек нека расподела вероватноћа.

Користећи својствене векторе за налажење помоћне и дијагоналне матрице (M = PDP-1) налазимо n-ти степен (Mn = PDnP-1) Марковљеве (Дијагонализација):

\[ \begin{pmatrix} a & b \\ b & a \end{pmatrix}^n = \begin{pmatrix} \frac12 & \frac12 \\ \frac12 & -\frac12 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & (a-b)^n \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = \frac12 \begin{pmatrix} 1 + (a-b)^n & 1 - (a-b)^n \\ 1 - (a-b)^n & 1 + (a-b)^n \end{pmatrix}. \]

Када n → ∞, ова матрица конвергира црној кутији која ће сваки улазни вектор расподеле избацити као вектор максималне информације (оптерећен максималним шумом). То каже и претходно решење, где вероватноће теже изједначавању, pn, qn → 1/2. Још један увид у ово „сужавање распона“ вероватноћа процесом преноса информације, на сасвим другачији начин изведено, је у прилогу Копије.

4.3. Изометријске трансформације, оне које чувају удаљеност између тачака, увек су неке ротације. Ако се систем Oxyz окреће око z-осе сваки пут за угао θ, онда имамо низ (n = 1, 2, 3, ...) корака:

\[ \begin{cases} x_n = x_{n-1}\cos\theta - y_{n-1}\sin\theta \\ y_n = x_{n-1}\sin\theta + y_{n-1}\cos\theta \end{cases} \]

или матрично (wn = Rwn-1) писано

\[ \begin{pmatrix} x_n \\ y_n \end{pmatrix} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} \begin{pmatrix} x_{n-1} \\ y_{n-1} \end{pmatrix}. \]

Две су својствене вредности ове ротације λ1 = e = cos θ + i⋅sin θ и λ2 = e-iθ = cos θ - i⋅sin θ са припадним својственим векторима, редом:

\[ \textbf{v}_1 = \begin{pmatrix} 1 \\ -i \end{pmatrix}, \quad \textbf{v}_2 = \begin{pmatrix} 1 \\ i \end{pmatrix}, \]

где за имагинарну јединицу важи i² = -1. Опште решење ове рекурзије је

wn = β1einθv1 + β2e-inθv2,

\[ \begin{pmatrix} x_n \\ y_n \end{pmatrix} = \beta_1e^{in\theta}\begin{pmatrix} 1 \\ -i \end{pmatrix} + \beta_2e^{-in\theta}\begin{pmatrix} 1 \\ i \end{pmatrix}. \]

Када је почетна позиција ротација x0 = 1 и y0 = 0 за θ = 0, тада из

\[ \beta_1\begin{pmatrix} 1 \\ -i \end{pmatrix} + \beta_2\begin{pmatrix} 1 \\ i \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]

следи β1 = β2 = 1/2. Отуда коначно решење:

xn = cos(),   yn = sin().

Тачка wn = (xn, yn) кружи (скакуће) по јединичној кружници око исходишта.

4.4. Разломљена рекурзија, попут

\[ x_{n+1} = \frac{a_{11}x_n + a_{12}}{a_{21}x_n + a_{22}} \]

може се свести на линеарни систем рекурзија сменом:

\[ \begin{cases} y_{n+1} = a_{11}y_n + a_{12}z_n, \\ z_{n+1} = a_{21}y_n + a_{22}z_n. \end{cases} \]

Овај систем, означимо га wn+1 = Awn, можемо решавати помоћу својствених вредности (пример 3.2), али и рецимо сменом варијабле (zn) из прве једначине у другу, након чијег сређивања налазимо:

yn+2 - (a11 + a22)yn+1 + (a11a11 - a21a12)yn = 0,
yn+2 - (tr A)yn+1 + (det A)yn = 0,
yn+2 - (λ1 + λ2)yn+1 + (λ1⋅λ2)yn = 0,
r² - (λ1 + λ2)r + (λ1⋅λ2) = 0,
r1 = λ1,   r2 = λ2,

јер је траг (tr A) матрице збир својствених вредности (λ1 + λ2) матрице A, а детерминанта (det A) њихов производ (λ1⋅λ2), што је познато из алгебре (Траг и Детерминанта). Према томе, имамо прву варијаблу:

yn+1 = β1(r1)n + β2(r2)n,

помоћу које израчунавамо другу (претпоставка је a12 ≠ 0):

zn = (yn+1 - a11yn)/a12 =
= [β1r1n + β2r2n - a11(β1r1n-1 + β2r2n-1)]/a12
= [β1(r1 - a11)r1n-1 + β2(r2 - a11)r2n-1]/a12,
zn+1 = [β1(r1 - a11)r1n + β2(r2 - a11)r2n]/a12.

Затим, користимо смену

\[ x_n = \frac{y_n}{z_n}, \quad x_0 = \frac{y_0}{z_0} = \alpha, \quad y_0 = \alpha, \ z_0 = 1, \]

јер добијамо:

\[ x_{n+1} = \frac{y_{n+1}}{z_{n+1}} = \frac{a_{11}y_n + a_{12}z_n}{a_{21}y_n + a_{22}z_n} = \frac{a_{11}\frac{y_n}{z_n} + a_{12}}{a_{21}\frac{y_n}{z_n} + a_{22}} = \frac{a_{11}x_n + a_{12}}{a_{21}x_n + a_{22}}, \] \[ x_{n+1} = \frac{a_{12}(\beta_1 r_1^n + \beta_2 r_2^n)}{\beta_1(r_1 - a_{11})r_1^n + \beta_2(r_2 - a_{11})r_2^n}. \]

Количник варијабли линеарног система (A) је решење датог, полазне разломљене рекурзије.

4.5. Пример. Решимо разломљену рекурзију

\[ x_{n+1} = \frac{2x_n - 1}{2x_n + 5}, \quad x_1 = 0. \]

Решење: Имамо: a11 = 2, a12 = -1, a21 = 2, a22 = 5, па је r1 = 3 и r2 = 4. Отуда

\[ x_{n+1} = -\frac{\beta_1 3^n + \beta_2 4^n}{\beta_1 3^n + 2\beta_2 4^n} = -1 + \frac{\beta_2}{\beta_1\cdot 0,75^n + 2\beta_2}, \] \[ x_{n+1} = \frac{1}{2-0,75^n} - 1, \quad n = 0, 1, 2, ... \]

након уврштавања почетне вредности. □