403
правки
Изменения
→Фибоначчиевы деревья
Подставив вместо <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)^{-k}} {\sqrt 5} < \frac {1} {\sqrt 5} < \frac {1} {2}</tex>. Таким образом, <tex>k</tex>-е число Фибоначчи равно <tex dpi="160">\frac {\varphi^{k}} {\sqrt 5}</tex>, округленному до ближайшего целого числа. Следовательно, <tex>F_k =\Theta(\varphi^k)</tex>.
}}
