Rekurence a vytvořující funkce

Aplikace řeší lineární rekurence s konstantními koeficienty libovolného řádu přes charakteristickou rovnici – i násobné a komplexní kořeny (komplexní tvar řešení a jeho převod na reálný podle Moivreovy věty) – a s pravou stranou ve tvaru P(n)·qⁿ (i cos nφ, sin nφ, rezonance a součet pravých stran). Počáteční podmínky určí konstanty; jako kontrolu aplikace spočítá další členy z rekurence a porovná je se vzorcem.

Čipem „Metoda“ jde zvolit i vytvořující funkci (A(x) = Σ aₙxⁿ, parciální zlomky, geometrické řady), mocniny matice (diagonalizace) nebo u 1. řádu sčítání. Rekurenci 1. řádu s proměnným koeficientem (aₙ₊₁ = (n + 1)aₙ) vyřeší součinem (faktoriály), převoditelné nelineární rekurence substitucí bₙ = 1/aₙ nebo bₙ = ln aₙ. Soustavu dvou rekurencí vyřeší vyloučením jedné posloupnosti nebo maticí, rekurenci „rozděl a panuj“ T(n) = aT(n/b) + f(n) substitucí n = bᵏ – i s odhadem podle mistrovské věty.

S operací „Vytvořující funkce“ aplikace najde vytvořující funkci posloupnosti zadané vzorcem (n² + 2ⁿ) nebo prvními členy (1, 0, 1, 0, …), a obráceně z funkce A(x) vzorec pro aₙ. Počet celočíselných nezáporných řešení rovnice x₁ + x₂ + … = N (i s mezemi nebo koeficienty – placení mincemi) spočítá jako koeficient vytvořující funkce.

Graf ukáže členy posloupnosti jako body (u soustavy obě posloupnosti).

Jak zadat

`a(n+2) = 5a(n+1) - 6a(n), a(0) = 1, a(1) = 4`	Zápis se závorkami, podmínky za čárkou.
`a_{n+2} = 5a_{n+1} - 6a_n`	Zápis s indexy (i z fotky). Bez podmínek vyjde obecné řešení s konstantami C₁, C₂.
`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`	Index může klesat (aₙ₋₁, aₙ₋₂); stejnou hodnotu lze zadat více členům.
`a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0`	Soustava – rovnice na řádcích, podmínky na posledním.
`T(n) = 2T(n/2) + n, T(1) = 1`	Rozděl a panuj – člen v n/b.
`n^2 + 2^n`	Vzorec posloupnosti s operací „Vytvořující funkce“ (i aₙ = …).
`1, 0, 1, 0, ...`	První členy posloupnosti oddělené čárkou.
`1/(1 - x - x^2)`	Vytvořující funkce v x (i A(x) = …) – vzorec pro aₙ.
`počet řešení x_1 + x_2 + x_3 = 10, x_1 <= 3`	Počet nezáporných celočíselných řešení s mezemi.

Ukázky

Dva různé reálné kořeny, kontrola dalšími členy.

Zadání: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Fibonacciho posloupnost – Binetův vzorec.

Zadání: F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

Komplexní kořeny 1 ± i – komplexní tvar a Moivreova věta.

Zadání: a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

Pravá strana n, dvojnásobný kořen 2.

Zadání: a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

Táž rekurence vytvořující funkcí.

Zadání: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Vytvořující funkce

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Táž rekurence mocninami matice.

Zadání: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Mocniny matice

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Rekurence 1. řádu sčítáním.

Zadání: a_{n+1} = 2a_n + 1, a_0 = 0 Sčítání

$a_{n+1} = 2a_n + 1, a_0 = 0$

$a_{n+1} = 2a_n + 1, a_0 = 0$ $a_{n+1} = 2a_n + 1, a_0 = 0$

Proměnný koeficient – součin vede na faktoriál.

Zadání: a_{n+1} = (n+1)a_n, a_0 = 1

$a_{n+1} = (n+1)a_n, a_0 = 1$

$a_{n+1} = (n+1)a_n, a_0 = 1$ $a_{n+1} = (n+1)a_n, a_0 = 1$

Nelineární rekurence – substituce bₙ = 1/aₙ.

Zadání: a_{n+1} = a_n/(1 + a_n), a_0 = 1

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$

Soustava dvou rekurencí vyloučením posloupnosti bₙ.

Zadání:

a_{n+1} = a_n + 2b_n
b_{n+1} = 3a_n + b_n
a_0 = 1, b_0 = 0

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

Rozděl a panuj (merge sort) – substituce n = 2ᵏ a mistrovská věta.

Zadání: T(n) = 2T(n/2) + n, T(1) = 1

Vytvořující funkce posloupnosti n² + 2ⁿ.

Zadání: n^2 + 2^n Vytvořující funkce

Z vytvořující funkce vzorec pro aₙ – parciální zlomky přes iracionální kořeny.

Zadání: 1/(1 - x - x^2) Vytvořující funkce

Počet řešení x₁ + x₂ + x₃ = 10 s podmínkou x₁ ≤ 3.

Zadání: počet řešení x_1 + x_2 + x_3 = 10, x_1 <= 3

Známá omezení

Zatím neumí: lineární rekurence s proměnnými koeficienty vyššího řádu, soustavy tří a více rekurencí, rozděl a panuj s více členy (T(n/2) a T(n/3)) a nelineární rekurence, které uvedené substituce nepřevedou na lineární.