1302
правки
Изменения
м
→Фибоначчиева куча
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex>
Поскольку <tex>\left\vert (-\varphi)^{-1} \right\vert < 1</tex>, то выполняются неравенства <tex dpi="160">\frac {(-\varphi)^{-n}} {\sqrt 5} < \frac {1} {\sqrt 5} < \frac {1} {2}</tex>. Таким образом, <tex>n</tex>-е ое число Фибоначчи равно <tex dpi="160">\frac {\varphi^{n}} {\sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_n =\Theta(\varphi^n)</tex>.
}}
