Question

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

Обозначим через $F(z)$ производящую функцию последовательности чисел Фибоначчи ∑∞/n=0 $B_{n}$ $z^{n}$. Докажите, что $F(z) = 1 + zF(z) + z^{2} F(z)$, и найдите отсюда $F(z)$.

Answer 1

Ответ:

$F(z)=\dfrac{1}{1-z-z^2}$

Пошаговое объяснение:

$B_1=0,B_1=1,B_{n+2}=B_{n+1}+B_{n} \Rightarrow B_{n+2}z^{n+2}=z\cdot B_{n+1}z^{n+1}+z^2\cdot B_{n}z^{n}\Rightarrow \\ \Rightarrow \sum\limits_{n=0}^\infty B_{n+2}z^{n+2}=z\cdot\sum\limits_{n=0}^\infty B_{n+1}z^{n+1}+z^2\cdot \sum\limits_{n=0}^\infty B_{n}z^{n}\Rightarrow\\ \Rightarrow F(z)-B_1 z-B_0=z\cdot (F(z)-B_0)+z^2\cdot F(z)\\ F(z)- z-1=z\cdot (F(z)-1)+z^2\cdot F(z)\\ F(z)=1+z\cdot F(z)+z^2\cdot F(z)$

Ч.т.д.

Отсюда

$F(z)\cdot (1-z-z^2)=1\Rightarrow F(z)=\dfrac{1}{1-z-z^2}$