Карлукова M32342 временная статья — различия между версиями
(→Представление в виде отношения многочленов производящей функции для последовательности чисел Фибоначчи) |
(→Представление в виде отношения многочленов производящей функции для последовательности чисел Фибоначчи) |
||
Строка 80: | Строка 80: | ||
<tex>f_n = f_{n-1} + f_{n-2}</tex>, <tex>n \geq 2</tex>. | <tex>f_n = f_{n-1} + f_{n-2}</tex>, <tex>n \geq 2</tex>. | ||
− | Здесь <tex>k=2</tex> и <tex>c_1 = c_2 = 1</tex>, следовательно <tex>Q(t) = 1 - | + | Здесь <tex>k=2</tex> и <tex>c_1 = c_2 = 1</tex>, следовательно <tex>Q(t) = 1 - t - t^2</tex>. |
К числителю применим формулу <tex>P(t) = F(t) \cdot Q(t) \mathrm{\ mod\ } t^2</tex>. Чтобы получить ответ, требуется всего лишь найти <tex>p_0</tex> и <tex>p_1</tex>. | К числителю применим формулу <tex>P(t) = F(t) \cdot Q(t) \mathrm{\ mod\ } t^2</tex>. Чтобы получить ответ, требуется всего лишь найти <tex>p_0</tex> и <tex>p_1</tex>. | ||
Строка 88: | Строка 88: | ||
<tex>p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 0</tex>. | <tex>p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 0</tex>. | ||
− | Таким образом, <tex>F(t) = \dfrac{1}{1 - | + | Таким образом, <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex>. |
<!-----=== Здесь может быть Ваш пример...))) ===-------> | <!-----=== Здесь может быть Ваш пример...))) ===-------> |
Версия 01:48, 1 июня 2020
Примечание: в редактируемой статье указано, что достаточно рассматривать . :)
Теорема о связи этих понятий
Теорема: |
Последовательность является линейной рекуррентной последовательностью с первыми заданными членами, определяемыми коэффициентами её производящая функция является дробно-рациональной, причём представимой в виде , где , . |
Доказательство: |
Пусть — коэффициенты, задающие линейную рекуррентную последовательность , то есть первые членов заданы, а для следующих справедливо соотношение .Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов:
Сложим все равенства и получим
Для всех выполняется равенство , поэтому в правой части все коэффициенты при степенях, начиная с , обнулятся, а равенство будет выглядеть следующим образом:. Заметим, что второй множитель в левой части равен в точности , а степень правой части не превосходит . Получили требуемое построение.Замечание. Многочлен можно найти по формуле как числитель получившейся дроби. К результату можно применить взятие его по модулю . Это действие не испортит многочлен, так как его степень строго меньше . При этом мы сократим число операций при вычислении , поскольку достаточно найти только первых членов результирующего ряда, а для этого можно обойтись только первыми слагаемыми степенных рядов, соответствующих производящим функциям и .Итак, .
Пусть , , .Перепишем первое равенство, выразив через и : .Так как произведения степенных рядов, получаем . , выполнено для любого . Расписывая по определениюРазобьём полученную сумму на две: . Так как известно, можем определить, чему равны эти суммы. Для первой выполняются равенства:, для всех за исключением нуля. Вторая же компонента равна нулю, поскольку . Тогда .Развернём выражение для :. Перенесём все слагаемые, кроме , вправо:Видим, что . — член линейной рекуррентной последовательности, заданной коэффициентами , причём это выполнено для всех , так как индекс , удовлетворяющий данному условию, выбирался произвольно. |
Примеры
Представление в виде отношения многочленов производящей функции для последовательности чисел Фибоначчи
Введём обозначения:
— производящая функция для чисел Фибоначчи, .
Последовательность задаётся следующим образом:
,
, .
Здесь
и , следовательно .К числителю применим формулу
. Чтобы получить ответ, требуется всего лишь найти и .,
.
Таким образом,
.