Самостоятельная работа №1 План: Аксиоматические теории множеств. Нечеткие множества

Умножим каждую строчку на z⁰, z¹, ..., zⁿ соответственно:

z⁰ ⋅ F₀ = 0,
z¹ ⋅ F₁ = z,
zⁿ ⋅ F_n = zⁿ ⋅ F_n-1 + zⁿ ⋅ F_n-2, n ≥ 2

Просуммируем эти равенства


Обозначим левую часть 

Рассмотрим каждое из слагаемых в правой части:



Имеем следующее уравнение G(z) = z + z G(z) + z² G(z) решая которое относительно G(z) находим

 — производящая функция для последовательности чисел Фибоначчи.

Разложим её на сумму простейших дробей, для этого найдем корни уравнения  . Решая это простое квадратное уравнение, получаем:  . Тогда нашу производящую функцию можно разложить следующим образом:


Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:


Подставляя в это уравнение значение z = z₁ и z = z₂, находим 

Напоследок немного преобразуем выражение для производящей функции



Теперь каждая из дробей представляет собой сумму геометрической прогрессии.

По формуле  находим 

Но ведь мы искали G(z) в виде  . Отсюда делаем вывод, что



Эту формулу можно переписать в другом виде не используя «золотое сечение»:



что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

1. 
   Запишите одно уравнение, выражающее gn через другие элементы последовательности. Это уравнение должно оставаться справедливым для всех целых n с учетом того, что g_-1=g_-2=....=0.
   
2. 
   Умножьте обе части уравнения на zⁿ и просуммируйте по всем n. В левой части получится сумма  , которая равна производящей функции G(z). Правую часть следует преобразовать так, чтобы она превратилась в какое-то другое выражение, включающее G(z).
   
3. 
   Решите полученное уравнение, получив для G(z) выражение в замкнутом виде.
   
4. 
   Разложите G(z) в степенной ряд и прочитайте коэффициент при zⁿ, это и будет замкнутый вид для g_n.
   

Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность g_n и это представление допускает многие преобразования.
Прежде чем переходить к следующему примеру, рассмотрим 2 операции, совершаемые над производящими функциями, которые часто оказываются полезными.

Дифференцирование и интегрирование производящих функций

Для производящих функций обычное определение производной можно записать следующим образом.
Пусть G = G(z) – производящая функция. Производной этой функции называется функция  . Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем


Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g₀ + g₁z + g₂z² + g₃z³ +… дает G΄(z) = g₁ + 2g₂z + 3g₃z² + 4g₄z³ +….

Интегралом называется функция


Операция дифференцирования обратна операции интегрирования:

Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, отличается от исходной функции,

Нетрудно заметить, что для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом

Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:
g₀ = 1,
g₁ = 1,
g_n = g_n-1 + 2g_n-2 + (-1)ⁿ
Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

z⁰⋅ g₀ = 1,
z¹ ⋅ g₁ = z,
zⁿ ⋅ g_n = zⁿ ⋅ g_n-1 + 2zⁿ ⋅ g_n-2 + (-1)ⁿ ⋅ zⁿ


Левая часть  представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:





Составляем уравнение:

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:



Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придется чуть повозиться. Используя правило дифференцирования производящих функций имеем:


Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

С одной стороны мы искали G(z) в виде  , с другой стороны  .
Значит,  .
Вместо заключения
Производящие функции нашли большое применение в математике, поскольку являются мощным оружием при решении многих практических задач, связанных, например, с перечислением, распределением и разбиением множеств объектов различной природы. Кроме того применение производящих функций позволяет доказать некоторые комбинаторные формулы, которые иначе получить очень трудно. Например, разложение функции  в степенной ряд имеет вид  , то есть справедливо равенство:


Возводя в квадрат обе части этого равенства получим



Приравнивая коэффициенты при xⁿ в левой и правой частях, получаем



Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.