Изменения
Нет описания правки
{{Задача
|definition = Доказать, что <tex>f_0 + f_1 + f_2 \ldots f_n = f_{n + 2} + - 1</tex>, где <tex>f_n</tex> {{---}} <tex>n</tex>-ое число Числа Фибоначчи
}}
Найдём производящую функцию последовательности <tex>A: f_0, f_0 + f_1, f_0 + f_1 + f_2, \ldots, \sum\limits_{k = 0}^{n} f_k, \ldots</tex>. Согласно утверждению [[Использование производящих функций для доказательства тождеств#lemma1 | леммы]], её производящая функция <tex>\dfrac{F(t)}{1 - t}</tex>, где <tex>F(t)</tex> {{---}} производящая функция последовательности Фибоначчи.
Найдём производящую функцию последовательности <tex>B: f_2 + - 1, f_3 + - 1, \ldots, f_{n + 2} + - 1, \ldots</tex>. Будем искать её в виде <tex>B(t) = \sum\limits_{n = 0}^{\infty} (f_{n + 2} + - 1) \cdot t^n = \sum\limits_{n = 0}^{\infty} f_{n + 2} \cdot t^n + - \sum\limits_{n = 0}^{\infty} t^n = (f_2 + f_3 \cdot t + f_4 \cdot t^2 + \ldots f_{n + 2} \cdot t^n + \ldots) + - \dfrac{1}{1 - t} = </tex>
<tex>= \dfrac{f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots}{t^2} + - \dfrac{1}{1 - t} = </tex>
<tex> = \dfrac{(f_0 + f_1 \cdot t + f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots) - f_1 \cdot t - f_0}{t^2} + - \dfrac{1}{1 - t} = </tex>
<tex>= \dfrac{(f_0 + f_1 \cdot t + f_2 \cdot t^2 + f_3 \cdot t^3 + f_4 \cdot t^4 + \ldots f_{n + 2} \cdot t^{n + 2} + \ldots) - t - 1}{t^2} + - \dfrac{1}{1 - t} = \dfrac{(\sum\limits_{n = 0}^{\infty} f_n \cdot t^n) - t - 1}{t^2} + - \dfrac{1}{1 - t} = </tex>
<tex>= \dfrac{F(t) - t - 1}{t^2} + - \dfrac{1}{1 - t}</tex>
Теперь проверим, что производящие функции последовательностей <tex>A</tex> и <tex>B</tex> совпадают.
Согласно [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности#Примеры применения теоремы| теореме о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]], производящая функция последовательности Фибоначчи имеет вид <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex> Тогда <tex>A(t) = \dfrac{F(t)}{1 - t} = \dfrac{\dfrac{1}{1 - t - t^2}}{1 - t} = \dfrac{1}{(1 - t - t^2) \cdot (1 - t)}</tex> <tex>B(t) = \dfrac{F(t) - t - 1}{t^2} - \dfrac{1}{1 - t} = \dfrac{\dfrac{1}{1 - t - t^2} - t - 1}{t^2} - \dfrac{1}{1 - t}</tex>
