10.67. Производящие функции
Фибоначчи (1202) ввел известную последовательность, известную ныне как последовательность Фибоначчи
в которой каждый член (после первых двух) является суммой двух предыдущих членов. Несмотря на этот простой закон образования, очевидной формулы для 
члена последовательности нет. Такая формула была открыта лишь спустя 500 с лишним лет де Муавром (1730), и открывая ее, де Муавр ввел новое мощное применение бесконечного ряда, метод производящих функций. Этот метод, который имеет большое значение в комбинаторике, теории вероятностей и теории чисел, будет проиллюстрирован с использованием самой последовательности Фибоначчи.
Технически удобно начать с 
затем принять последующие члены как указано выше (поэтому 
), определяя
Это пример линейного рекуррентного соотношения, и именно для решения таких соотношений в теории вероятностей де Муавр ввел производящие функции. Производящая функция для последовательности Фибоначчи имеет вид
Мы замечаем, что
Следовательно,
то есть, 
потому что все коэффициенты 
по определению последовательности
Фибоначчи. Таким образом,
и используя корни 
чтобы разложить на множители знаменатель, мы получаем
Затем разбив на элементарные дроби
и используя разложения в геометрический ряд
мы, наконец, получаем
Приравнивание этого к определению 
дает
Не удивительно, что формулу для 
было трудно найти! Как правило, не ожидаешь, что иррациональное число 
входит в целочисленную функцию 
Объяснение состоит в том, что последовательность Фибоначчи фактически определяет 
потому что 
(золотое отношение) по мере того, как 
поэтому (1), в сущности, определяет отдельные члены последовательности Фибоначчи в понятиях последовательности в целом (или, если предпочитаете, на основе поведения последовательности в бесконечности). Замечательный факт, что определение 
становится скорее явным, чем рекурсивным, когда оно выражено в понятиях 
есть следствие простоты производящей функции 
которая кодирует всю последовательность.
Рекурсивное свойство чисел Фибоначчи, использованное в доказательстве де Муавра, заключается в том, что они удовлетворяют линейному рекуррентному соотношению; то есть, 
выражена так определенная линейная комбинация более ранних членов последовательности. Доказательство легко обобщить, чтобы показать, что производящая функция 
любой последовательности 
определенная линейным рекуррентным соотношением, рациональна. Кроме того, доказательство можно обратить, чтобы показать, что степенной ряд любой рациональной функции имеет коэффициенты, которые удовлетворяют линейному рекуррентному соотношению. Тагам образом, рациональные функции можно охарактеризовать на основе их степенных рядов, факт, который был замечен Кронекером (1881), Раздел IX.
Упражнения
(см. скан)
