Карлукова M32342 временная статья — различия между версиями
(→Вычисление коэффициентов ряда \dfrac{1}{(1-t)^2} с помощью теоремы о связи рекуррентности и рациональности) |
|||
Строка 101: | Строка 101: | ||
* Для начальных значений равенства выполнены: <tex>a_0=1=0+1</tex>, <tex>a_1=2=1+1</tex>; | * Для начальных значений равенства выполнены: <tex>a_0=1=0+1</tex>, <tex>a_1=2=1+1</tex>; | ||
<!------*: Чтобы узнать, работает ли формула для <tex>n</tex>, больших <tex>2</tex> найдём <tex>a_2</tex>: <tex>a_2 = 2a_1 - a_0 = 2\cdot 2 - 1 = 3 = 2+1</tex>.--------> | <!------*: Чтобы узнать, работает ли формула для <tex>n</tex>, больших <tex>2</tex> найдём <tex>a_2</tex>: <tex>a_2 = 2a_1 - a_0 = 2\cdot 2 - 1 = 3 = 2+1</tex>.--------> | ||
− | * Будем считать предыдущие | + | * Будем считать предыдущие равенства базой индукции. То есть существует такое число <tex>n\geq 1</tex>, что до него проверяемая формула работала. Для следующего числа <tex>n+1</tex> верно <tex>a_{n+1}=2\cdot a_{n} - a_{n-1}</tex>. Предыдущие значения известны. Они подчинялись равенству <tex>a_{n}=n+1</tex>. Раскроем формулу: |
*: <tex>a_{n+1}=2\cdot a_{n} - a_{n-1} = 2\cdot (n+1) - n = 2\cdot n + 2 - n = n+2 = (n+1) + 1</tex>. | *: <tex>a_{n+1}=2\cdot a_{n} - a_{n-1} = 2\cdot (n+1) - n = 2\cdot n + 2 - n = n+2 = (n+1) + 1</tex>. | ||
: Методом математической индукции показали, что нет такого <tex>n</tex>, на котором действие формулы <tex>a_{n}=n+1</tex> заканчивается, и установили, что результаты нахождения коэффициентов <tex>A(t)</tex> методами дифференцирования и выражения через рекуррентную связь совпали. | : Методом математической индукции показали, что нет такого <tex>n</tex>, на котором действие формулы <tex>a_{n}=n+1</tex> заканчивается, и установили, что результаты нахождения коэффициентов <tex>A(t)</tex> методами дифференцирования и выражения через рекуррентную связь совпали. |
Версия 15:36, 1 июня 2020
Примечание: в редактируемой статье указано, что достаточно рассматривать . :)
Содержание
Теорема о связи этих понятий
Теорема: |
Последовательность является линейной рекуррентной последовательностью с первыми заданными членами, определяемыми коэффициентами её производящая функция является дробно-рациональной, причём представимой в виде , где , . |
Доказательство: |
Пусть — коэффициенты, задающие линейную рекуррентную последовательность , то есть первые членов заданы, а для следующих справедливо соотношение .Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов: Сложим все равенства и получим Для всех выполняется равенство , поэтому в правой части все коэффициенты при степенях, начиная с , обнулятся, а равенство будет выглядеть следующим образом:
Заметим, что второй множитель в левой части равен в точности , а степень правой части не превосходит . Получили требуемое построение.Замечание. Многочлен можно найти по формуле как числитель получившейся дроби. К результату можно применить взятие его по модулю . Это действие не испортит многочлен, так как его степень строго меньше . При этом мы сократим число операций при вычислении , поскольку достаточно найти только первых членов результирующего ряда, а для этого можно обойтись только первыми слагаемыми степенных рядов, соответствующих производящей функции и столькими же для .Итак, .
Пусть , , .Перепишем первое равенство, выразив через и : .Так как произведения степенных рядов, получаем . , выполнено для любого . Расписывая по определениюРазобьём полученную сумму на две: . Так как известно, можем определить, чему равны эти суммы. Для первой выполняются равенства:
Вторая же компонента равна нулю, поскольку . Тогда .Развернём выражение для :
Перенесём все слагаемые, кроме , вправо:
|
Примеры
Представление в виде отношения многочленов производящей функции для последовательности чисел Фибоначчи
Введём обозначения:
- — производящая функция для чисел Фибоначчи,
- .
Последовательность задаётся следующим образом:
- ,
- .
Здесь
и , следовательно .К числителю применим формулу
. Чтобы получить ответ, требуется всего лишь найти и .- ,
- .
Таким образом,
.Вычисление коэффициентов ряда с помощью теоремы о связи рекуррентности и рациональности
Найдём коэффициенты ряда
через построение рекуррентного соотношения.Имеем
- ,
- .
Второе равенство позволяет найти
и коэффициенты . В нашем примере , , .Зная, что
, найдём первые два коэффициента ряда, соответствующего функции . Подставим в равенство известные значения:- . Отсюда , .
Итак, коэффициенты
задаются соотношением- , ,
- .
Известно, что
. Такой результат можно получить, например, продифференцировав ряд функции . Проверим, что нахождение рекуррентного соотношения для исходной дроби даёт такой же результат, то есть для всех выполняется .- Для начальных значений равенства выполнены: , ;
- Будем считать предыдущие равенства базой индукции. То есть существует такое число
- .
, что до него проверяемая формула работала. Для следующего числа верно . Предыдущие значения известны. Они подчинялись равенству . Раскроем формулу:
- Методом математической индукции показали, что нет такого , на котором действие формулы заканчивается, и установили, что результаты нахождения коэффициентов методами дифференцирования и выражения через рекуррентную связь совпали.