Изменения

== Необходимые определения Нахождение асимптотики рекуррентной последовательности =={{Определение|id=def_linear. |definition=Последовательность Здесь будет рассмотрен метод поиска функции, которая имеет одинаковую асимптотику<texref>a_0, a_1, \ldots, a_n, \ldots <[https://tex> называется '''линейной рекуррентной последовательностью''' (англru.wikipedia. ''constant-recursive sequence''), если её члены <tex>a_0 \ldots a_{k - 1} <org/wiki/tex> заданы, а <tex>\forall n \geqslant k %D0%90%D1%81%D0%B8%D0%BC%D0%BF%D1%82%D0%BE%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D0%B2%D0%B5%D0%BD%D1%81%D1%82%D0%B2%D0%BE Асимптотическое равенство]</texref> выполняется с <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>}} {{Определение|id=def_asymp_equal. |definition=Функции <tex>f: \;\mathbb{N} \rightarrow \mathbb{R}</tex> и <tex>g: \;\mathbb{N} \rightarrow \mathbb{R}</tex> ''имеют одинаковую асимптотику'', или ''одинаковый рост'', то есть при <tex>n \rightarrow \infty</tex>, если существует предел <tex>\displaystyle\lim_{n \rightarrow \infty}{\dfrac{f(n)}{g(n)}}</tex>, и он равен <tex>1</tex>.}} Здесь будет рассмотрен метод поиска функции <tex>g(n)</tex>, такой что <tex>g(n)</tex> имеет одинаковую асимптотику с отличаться от <tex>a_n</tex>в константу раз. Из [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%81%D0%B2%D1%8F%D0%B7%D0%B8_%D0%BC%D0%B5%D0%B6%D0%B4%D1%83_%D1%80%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D1%8F%D1%89%D0%B5%D0%B9_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8_%D0%B8_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B9_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C%D1%8E_%D0%B7%D0%B0%D0%B4%D0%B0%D0%B2%D0%B0%D0%B5%D0%BC%D0%BE%D0%B9_%D0%B5%D0%B9_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8&oldid=74516 теоремы о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности] известно, что последовательность, заданная рекуррентным соотношением, представима в виде дробно-рациональной производящей функции в следующем виде: <tex>A(t)=\dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k c_s \cdot t^ks</tex>, <tex>deg(P) < k</tex>. == Алгоритм ==Пусть последовательность задана дробно-рациональной функцией <tex>A(t) = \dfrac{P(t)}{Q(t)}s</tex>, тогда <tex>Q(t)</tex> — многочлен конечной степени, и мы можем найти его обратные корни <tex>r_1следовательно, r_2, \dots, r_s</tex> с кратностью соответственно он имеет <tex>f_1, f_2, \dots, f_ss</tex>. ''' Существует единственный максимальный обратный корень: <tex>\exists i: \: \forall j \neq i \; |r_i| > |r_j|</tex>''' Тогда корней <tex>r_i t_i\in \mathbb{RC}</tex>, в этом случае каждый из которых имеет некоторую кратность <tex>a_n \sim n^{f_i - 1} \cdot r_{i}^{n}</tex> ''' Существует несколько максимальных по модулю обратных корней '''.

Возьмем те из них, кратность которых максимальна, тогда имеем Найдем обратные корни к <tex>r_1, r_2, \dots, r_lt_i</tex>, у каждого из которых кратность то есть <tex>fr_i = \dfrac{1}{t_i}</tex>.Тогда имеем набор <tex>r_1, r_2, \forall j \in 1,\dots l :\; r_j = z e^{i \phi_j}, , r_s</tex> обратных корней <tex>Q(t)</tex>, где с кратностью соответственно <tex>zf_1, f_2, \,\dots\, , f_s</tex> — модуль каждого из корней. :

# Существует единственный максимальный обратный корень: <tex>\exists i: \: \forall j \neq i \; |r_i| > |r_j|</tex>.<br/> Тогда <tex>r_i \in \mathbb{R}</tex>, в этом случае <tex>a_n \sim n^{f_i - 1} \cdot r_{i}^{n}</tex>.# Существует несколько максимальных по модулю обратных корней:<br/> Найдем коэффициенты корней <tex>c_i</tex>, которые можно получить разложением <tex>A(t)</tex> на сумму простых дробей в вида <tex>\dfrac{c_i}{(1 - r_i t)^{f_i}}</tex>. <br/> Возьмем те обратные корни, кратность которых максимальна, тогда имеем <tex>r_1, r_2, \,\dots\, , r_l</tex>, у каждого из которых некоторая максимальность кратность <tex>f</tex>. Тогда <tex>\forall j \in 1 \,\dots\, l :\; r_j = z e^{i \phi_j}</tex>, где <tex>z</tex> — модуль каждого из корней. <br/>Значит <tex>\displaystyle a_n \sim n^{f - 1} \sum_{j = 1}^{l} {c_j \cdot r_j^n} = 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}}</tex>, где <tex>c_j</tex> — коэффициенты, полученные при разбиении дробно-рациональной функции на простые дроби.

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

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

Данная В этом примере оценка учитывает включает в себя все обратные корни с их коэффициентами, поэтому она является представлением коэффициента производящей функции в форме квазимногочлена<ref>[https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D0%90%D0%B4%D0%B0%D0%BC%D0%B0%D1%80%D0%B0_%D1%80%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D1%8F%D1%89%D0%B8%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9 #lemma1 Лемма о представлении коэффициента рациональной производящей функции в форме квазимногочлена]</ref>. Это значит, поэтому что вместо знака <tex>\sim</tex> можно поставить знак равенства.

* Graham, Knuth, and Patashnik: Concrete Mathematics, p. 340