Участник:Nkorzh

Необходимые определения

Определение:

Последовательность [math]a_0, a_1, \ldots, a_n, \ldots [/math] называется линейной рекуррентной последовательностью (англ. constant-recursive sequence), если её члены [math]a_0 \ldots a_{k - 1} [/math] заданы, а [math]\forall n \geqslant k [/math] выполняется [math] a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}[/math]

<определение через большую омега>

Здесь будет рассмотрен метод поиска функции [math]g(n)[/math], такой что [math]a_{n} \in \Omega(g(n))[/math].

Из теоремы о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности известно, что последовательность, заданная рекуррентным соотношением, представима в виде дробно-рациональной производящей функции в следующем виде: [math]A(t)=\dfrac{P(t)}{Q(t)}[/math], где [math]Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k[/math], [math]deg(P) \lt k[/math].

Алгоритм

Пусть последовательность задана дробно-рациональной функцией [math]A(t) = \dfrac{P(t)}{Q(t)}[/math], тогда [math]Q(t)[/math] — многочлен конечной степени, и мы можем найти его обратные корни [math]r_1, r_2, \dots, r_s[/math] с кратностью соответственно [math]f_1, f_2, \dots, f_s[/math].

Существует максимальный обратный корень: [math]\exists i: \: \forall j \neq i \; |r_i| \gt |r_j|[/math]

Тогда [math]r_i \in \mathbb{R}[/math], в этом случае [math]a_n \sim n^{f_i - 1} \cdot r_{i}^{n}[/math]