Řešení lineární rekurence — pokračování

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

Věta. Má-li charakteristický polynom

k

různých kořenů, potom posloupnosti

n \mapsto λ_{i}^{n}

jsou lineárně nezávislé.

Důkaz. Sestavme matici soustavy pro prvních

k

členů a ur4eme její determinant:

| \begin{array}{cccc} 1 & 1 & \dots & 1 \\ λ_{1} & λ_{2} & \dots & λ_{k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ λ_{1}^{k - 1} & λ_{2}^{k - 1} & \dots & λ_{k}^{k - 1} \end{array} | = \prod_{1 \leq i < j \leq k} (λ_{i} - λ_{j}) \neq 0

Věta. Jestliže má charakteristický polynom

l \leq k

různých kořenů s násobnostmi

γ_{i}

. Potom soubor lineárně nezávislých posloupností je

n \mapsto n^{j} \cdot λ_{i}^{n}

pro každé

i \in 1, \dots, l

j \in 0, \dots, γ_{i} - 1