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

P_h(0), P_h (1), P_h (2), × × × равна .

Доказательство. Произведение равно

(1 +x+x ² + × × ×)(1 +x ² +x ⁴ + × × ×)(1 + x ³ + x ⁶ + × × ×)× × ×(1 + x^h + x ^{2 h} + × × ×).

Если перемножить содержимое скобок, то получим многочлен, равный сумме одночленов . Отсюда коэффициент при xⁿ равен числу последовательностей (l ₁, l ₂, × × ×, l_h), для которых l ₁ ×1 + l ₂ ×2 + × × ×+ l_h × h = n. Он будет равен числу разбиений n на слагаемые, не большие чем h.

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

P(0), P(1), P(2), × × × равна .

Числа Фибоначчи

Вычислим производящую функцию F(x) чисел Фибоначчи

F₀ = F₁ = 1, F_n+1 = F_n + F_n-1 при n ³ 1.

Т.о. числа Фибоначчи – это последовательность чисел 1, 1, 2, 3, 5... Имеют место соотношения:

.

Приходим к уравнению F(x)=1 + x + x² + x(F(x)-1) для . Решая это уравнение, получаем , для некоторых A, B, при , . Отсюда мы видим, что ряд F(x) равен сумме геометрических прогрессий. Находим , . Следовательно, . Отсюда получаем формулу для вычисления k –го числа Фибоначчи, , для всех k = 0, 1, 2, ∙ ∙ ∙.

 

Рекуррентные уравнения

Рассмотрим обобщение последовательностей Фибоначчи. Формула

u_{n + r} = c₁ u_{n + r – 1} + c₂ u_{n + r – 2} + ∙ ∙ ∙ + c_r u_n

называется однородным линейным рекуррентным уравнением порядка r. Ее решением является последовательность {u_n}, однозначно определенная начальными значениями u₀, u₁, u₂, ∙ ∙ ∙, u_{r –1} . Решение такого уравнения называется возвратной или рекуррентной последовательностью порядка r.

Пример 1. Геометрическая прогрессия является решением уравнения u_n+1=qu_n. Ее члены описываются формулой u_n= u₀qⁿ. Отсюда геометрическая прогрессия является возвратной последовательностью порядка 1.

Пример 2. Арифметическая прогрессия u_n = u₀ + nd удовлетворяет соотношению u_n+1 - u_n = u_n+2 - u_n+1. Получаем однородное рекуррентное уравнение u_n+2 = 2u_n+1 - u_n. Начальные данные задаются значениями u₀ и u₁=u₀+d. Отсюда арифметическая прогрессия является возвратной последовательностью порядка 2.

Пример 3. Произвольная периодическая последовательность является возвратной последовательностью порядка p, удовлетворяющей рекуррентному соотношению

u_{n + p}=u_n. Здесь p – период последовательности.

Для заданного рекуррентного уравнения

u_{n + r} = c₁ u_{n + r – 1} + c₂ u_{n + r – 2} + ∙ ∙ ∙ + c_r u_n

найдем производящую функцию возвратной последовательности { u_n }. Обозначим K(x)=1- c₁x - c₂x² - ∙ ∙ ∙ - c_rx^r.

Теорема 1. Произведение u(x)K(x) = D(x) является многочленом степени меньшей, чем r.

Доказательство. Вычислим коэффициент ряда D(x) при x^{n+ r} . Он при n ≥ 0 будет равен u_{n + r} - (c₁ u_{n + r – 1} + c₂ u_{n + r – 2} + ∙ ∙ ∙ + c_r u_n) = 0. Отсюда D(x) – многочлен степени меньшей, чем n.