693
правки
Изменения
→Представление в виде отношения многочленов производящей функции для последовательности чисел Фибоначчи
Введём обозначения:
Последовательность задаётся следующим образом:
:<tex>f_0 = f_1 = 1</tex>, :<tex>f_n = f_{n-1} + f_{n-2}</tex>, <tex>n \geq 2</tex>.
Здесь <tex>k=2</tex> и <tex>c_1 = c_2 = 1</tex>, следовательно <tex>Q(t) = 1 - t - t^2</tex>.
К числителю применим формулу <tex>P(t) = F(t) \cdot Q(t) \mathrm{\ mod\ } t^2</tex>. Чтобы получить ответ, требуется всего лишь найти <tex>p_0</tex> и <tex>p_1</tex>.
:<tex>p_0 = f_0 \cdot q_0 = 1 \cdot 1 = 1</tex>, :<tex>p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 0</tex>.
Таким образом, <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex>.
