Участник: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]f: \;\mathbb{N} \rightarrow \mathbb{R}[/math] и [math]g: \;\mathbb{N} \rightarrow \mathbb{R}[/math] имеют одинаковую асимптотику, или одинаковый рост, при [math]n \rightarrow \infty[/math], если существует предел [math]\displaystyle\lim_{n \rightarrow \infty}{\dfrac{f(n)}{g(n)}}[/math], и он равен [math]1[/math].

Здесь будет рассмотрен метод поиска функции [math]g(n)[/math], такой что [math]g(n)[/math] имеет одинаковую асимптотику с [math]a_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]

Существует несколько максимальных по модулю обратных корней

Возьмем те из них, кратность которых максимальна, тогда имеем [math]r_1, r_2, \dots, r_l[/math], у каждого из которых кратность [math]f[/math]. Тогда [math]\forall j \in 1\dots l :\; r_j = z e^{i \phi_j}[/math], где [math]z[/math] — модуль каждого из корней.

Значит [math]\displaystyle a_n \sim n^{f - 1} \sum_{j = 1}^{l} {c_j \cdot (z\cdot e^{i \phi_j})^{n}} = n^{f - 1} z^n \sum_{j = 1}^{l} {c_j \cdot e^{i \phi_j n}}[/math], где [math]c_j[/math] — коэффициенты, полученные при разбиении дробно-рациональной функции на простые дроби.

Примеры задач

Задача:

Оцените асимптотическое поведение коэффициента [math]a_n[/math] производящей функции [math]A(t)=\dfrac{t^2}{1 - 2t - t^2 + 2t^3}[/math] при [math]n \rightarrow \infty[/math]

Найдем корни знаменателя производящей функции: [math]Q(t) = 1 - 2t - t^2 + 2t^3 = (1 - 2t)(1 - t)(1 + t)[/math], тогда обратные корни: [math]r_1 = 2,\,f_1 = 1;\; r_2 = 1,\, f_2 = 1;\; r_3 = -1,\, f_3 = 1[/math].

Выберем максимальный по модулю [math]r_1 = 2[/math], тогда [math]a_n \sim n^{f_1 - 1} \cdot r_{1}^{n} = 2^n[/math].

Задача:

Оцените асимптотическое поведение коэффициента [math]a_n[/math] производящей функции [math]A(t)=\dfrac{1}{(1 - 2t)(1 + 4t^2)}[/math] при [math]n \rightarrow \infty[/math]

Найдем корни знаменателя производящей функции: [math]Q(t) = (1 - 2t)(1 + 4t^2)[/math]: [math]t_1 = \dfrac{1}{2},\, t_2 = \dfrac{1}{2i},\, t_3 = -\dfrac{1}{2i}[/math], тогда обратные корни: [math]r_1 = 2,\,f_1 = 1;\; r_2 = 2i,\, f_2 = 1;\; r_3 = -2i,\, f_3 = 1[/math]. Все три обратных корня имеют одинаковый модуль [math]z = 2[/math] и кратность [math]f = 1[/math].

Для определения доминирующего коэффициента разложим производящую функцию на простые дроби, например, с помощью метода неопределенных коэффициентов, так мы найдем [math]c_i:[/math]

[math]A(t) = \dfrac{\frac{1}{4}}{\frac{1}{2} - t} + \dfrac{\frac{1 - i}{4}}{t + \frac{1}{2i}} + \dfrac{\frac{1 + i}{4}}{t - \frac{1}{2i}},\; c_1 = \dfrac{1}{4},\, c_2 = \dfrac{1 - i}{4},\, c_3 = \dfrac{1 + i}{4}[/math]

[math]\displaystyle a_n \sim n^{f - 1} \sum_{i = 1}^{3} {c_i \cdot r_i^{n}} = n^{1 - 1} \cdot \left(\dfrac{1}{4} \cdot 2^n + \dfrac{1 - i}{4} \cdot (2i)^n + \dfrac{1 + i}{4} \cdot (-2i)^n \right) = 2^{n - 2}\cdot (1 + (1 - i)\cdot i^n + (1 + i) \cdot (-i)^n)[/math].

Данная оценка учитывает все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме квазимногочлена, поэтому вместо знака [math]\sim[/math] можно поставить знак равенства.

См. также

• Производящая функция
• Произведение Адамара рациональных производящих функций

Источники информации

• Graham, Knuth, and Patashnik: Concrete Mathematics
• Wikipedia — Asymptotic growth of a sequence