403
правки
Изменения
→Фибоначчиевы деревья
<tex>F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1</tex>, что действительно верно.
По индукции предполагаем, что <tex>F_{k-1} = 1 + \sum\limits_{i=0}^{k-3} F_i </tex>. Тогда
<tex>F_k = F_{k-1} + F_{k-2} = 1 + \sum\limits_{i=0}^{k-3} F_i + F_{k-2} = 1 + \sum\limits_{i=0}^{k-2} F_i</tex>
}}
{{Лемма
|id=Лемма2
|statement= <tex>F_k =\Theta(\varphi^k)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex>
|proof=
Для начала докажем, что <tex>F_k =</tex> <tex dpi="160">\frac {\varphi^k - (-\varphi)^{-k}} {\sqrt 5}</tex>
Используем для этого математическую индукцию.
При <tex>k = 0</tex>
<tex>F_0 =</tex> <tex dpi="160">\frac {\varphi^0 - (-\varphi)^0} {\sqrt 5} = \frac {1 - 1} {\sqrt 5} = 0</tex>, что верно.
При <tex>k = 1</tex>
<tex>F_1 =</tex> <tex dpi="160">\frac {\varphi^1 - (-\varphi)^{-1}} {\sqrt 5} = \frac {\frac {1 + \sqrt 5} {2} - \frac {1 - \sqrt 5} {2}} {\sqrt 5} = \frac {2\sqrt 5} {2\sqrt 5} = 1</tex>, что также верно.
По индукции предполагаем, что <tex>F_{k-1} =</tex> <tex dpi="160">\frac {\varphi^{k-1} - (-\varphi)^{1-k}} {\sqrt 5}</tex> и <tex>F_{k-2} =</tex> <tex dpi="160">\frac {\varphi^{k-2} - (-\varphi)^{2-k}} {\sqrt 5}</tex>. Тогда
<tex>F_k = F_{k-1} + F_{k-2} =</tex> <tex dpi="160">\frac {\varphi^{k-1} - (-\varphi)^{1-k}} {\sqrt 5} + \frac {\varphi^{k-2} - (-\varphi)^{2-k}} {\sqrt 5} =</tex>
<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{k-1} - (-\varphi)^{1-k} + \varphi^{k-2} - (-\varphi)^{2-k}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{k}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-k}(-\varphi + \varphi^{2}))</tex>
Подставив вместо <tex>\varphi</tex> его значение, нетрудно убедится, что <tex>\varphi^{-1} + \varphi^{-2} = -\varphi + \varphi^{2} = 1</tex>
}}
