Использование рекуррентных соотношений

1.11.1. Пусть f (n.m) – число сочетаний с повторениями из n по m (задача 8.4). Проверьте, что

1.11.2. f (n. 0)=1, f (n. 1)= n, f (n.m)= f (n -1 .m)+ f (n.m -1) при 1≤ m ≤ n -1.

1.11.3. Пусть A_n (z)= . Проверьте, что A_n (z)= A_{n- 1}(z)/(1- z).

1.11.4. Получите формулу для A_n (z), не содержащую A_i (z) при i<z. Сравните с задачей 1.10.6.

1.11.5. Числа Фибоначчи определяются следующим образом. B ₀= B ₁=1, B_n= B_{n -1}+ B_{n -2} при n =2,3,…. (Фибоначчи – псевдоним итальянского купца 12 века Леонардо Пизанского, который между торговыми операциями занимался своим хобби – математикой. И достиг на этом поприще очень многого…). Обозначим через F (z) производящую функцию последовательности чисел Фибоначчи . Докажите, что F (z)=1+ zF (z)+ z ² F (z) и найдите отсюда F (z).

1.11.6. Пользуясь разложением полученной рациональной дроби на простейшие и разложением функции в степенной ряд при , получите выражение для B_n.

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