Obecný postup na řešení lineárních rekurencí

Definice. Nechť

k \in ℕ

α_{0}, \dots, α_{k - 1}, f : ℂ^{ω}

. Rovnice

a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i} = f (n)

se nazývá lineární rekurentní vztah (diferenční rovnice) řádu

k

pro posloupnost

a

s pravou stranou

f

. Je-li

f (n) = 0

, potom se rovnice nazývá homogenní, jinak nehomogenní.

Věta. Množina posloupností

ℂ^{ω} = (ℕ \to ℂ)

tvoří lineární prostor nad tělesem

ℂ

Důkaz. Triviální.

Věta. Množina

M = {a \in ℂ^{ω} | a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i} = 0}

tvoří podprostor

ℂ^{ω}

Důkaz.

$\vec{0} = (n \mapsto 0) \in M$ .
Nechť $a, b \in M$ a $γ \in ℂ$ . Potom $γ a + b \in M$ , neboť pro všechna $n \in ℕ$ $a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) (γ a_{n + i} + b_{n + i}) = γ (a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i}) + (a_{n + k} + \sum_{i = 0}^{k - 1} α_{i} (n) a_{n + i}) = 0$

Věta.

\dim M = k

Důkaz. Pro

i \in {0, \dots, k - 1}

definujme posloupnosti

e_{i}

takové, aby

e_{i} (i) = 1

\forall j \in {0, \dots, k - 1} ∖ {i}, e_{i} (j) = 0

. Zbytek členů dopočítáme tak, aby každé

e_{i}

patřilo do

M

. Tyto posloupnosti zřejmě tvoří bázi

M

Definice. Rovnice

λ^{k} + \sum_{i = 0}^{k - 1} α_{i} λ^{i} = 0

se nazývá charakteristická rovnice lineární rekurence.

Věta. Nechť

α_{i}

jsou konstanty a

λ \in ℂ ∖ {0}

. Potom

(n \mapsto λ^{n}) \in M

právě tehdy, pokud řeší charakteristickou rovnici.