Изменения

|statement=Для всех целых <tex> k n \geqslant 2</tex><tex> F_k F_n = 1 + \sum\limits_{i=0}^{kn-2} F_i </tex>,где <tex> F_k F_n </tex> {{---}} <tex> k n </tex> число Фибоначчи, определяемое формулой:

F_k F_n =

0, & k n = 0 \\ 1, & k n = 1 \\ F_{kn-1} + F_{kn-2}, & k n \geqslant 2

при <tex>k n = 2</tex>

По индукции предполагаем, что <tex>F_{kn-1} = 1 + \sum\limits_{i=0}^{kn-3} F_i </tex>. Тогда

<tex>F_k F_n = F_{kn-1} + F_{kn-2} = 1 + \sum\limits_{i=0}^{kn-3} F_i + F_{kn-2} = 1 + \sum\limits_{i=0}^{kn-2} F_i</tex>

|statement= <tex>F_k F_n =\Theta(\varphi^kn)</tex>, где <tex dpi="160"> \varphi = \frac {1 + \sqrt 5} {2}</tex>

Для начала докажем, что <tex>F_k F_n =</tex> <tex dpi="160">\frac {\varphi^k n - (-\varphi)^{-kn}} {\sqrt 5}</tex>

При <tex>k n = 0</tex>

По индукции предполагаем, что <tex>F_{kn-1} =</tex> <tex dpi="160">\frac {\varphi^{kn-1} - (-\varphi)^{1-kn}} {\sqrt 5}</tex> и <tex>F_{kn-2} =</tex> <tex dpi="160">\frac {\varphi^{kn-2} - (-\varphi)^{2-kn}} {\sqrt 5}</tex>. Тогда

<tex>F_k F_n = F_{kn-1} + F_{kn-2} =</tex> <tex dpi="160">\frac {\varphi^{kn-1} - (-\varphi)^{1-kn}} {\sqrt 5} + \frac {\varphi^{kn-2} - (-\varphi)^{2-kn}} {\sqrt 5} =</tex>

<tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{kn-1} - (-\varphi)^{1-kn} + \varphi^{kn-2} - (-\varphi)^{2-kn}) </tex> <tex dpi="160">= \frac {1} {\sqrt 5}</tex> <tex>(\varphi^{kn}(\varphi^{-1} + \varphi^{-2}) - (-\varphi)^{-kn}(-\varphi + \varphi^{2}))</tex>

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

Поскольку <tex> F_k {{Лемма|id=Лемма3|statement= \Omega(\varphi^k) Фибоначчиево дерево порядка </tex>, где <tex> \varphi = \frac {1 + \sqrt 5}2 n</tex>, то максимальная степень вершины в фибоначчиевой куче с содержит не менее <tex> N F_n</tex> вершинами есть вершин.|proof=Докажем это утверждение по индукции.Пусть <tex> O(\log N) s_n</tex>{{---}} минимальный размер фибоначчиева дерева порядка n. Обозначим эту величину за  При <tex> D[H] n = 0</tex>.

Каждая вершина <tex> x </tex> знает своего родителя (<tex> p[x] </tex>) и какого-нибудь своего ребенка(<texs_0 = 1 > child[x] F_0</tex>).

Дети любой вершины связаны в циклический двусвязный список. Такие списки удобны по двум причинам: из такого списка можно удалить вершину, и два таких списка можно связать в один за При <tex> O(n = 1) </tex>

Также <tex>s_1 = 1 = F_1</tex>. Предположим по индукции, что для всех <tex>i < n \ s_i \geqslant F_i</tex>.Пусть в любой вершине хранятся поля нашем дереве удалено поддерево порядка <tex>n - 1</tex> degree. Тогда <tex>s_n = 1 + \sum\limits_{i=0}^{n-2} s_i \geqslant 1 + \sum\limits_{i=0}^{n-2} F_i</tex> Но по [x[#Лемма1|лемме], ] <tex>1 + \sum\, mark[x] limits_{i=0}^{n-2} F_i = F_n</tex>: степень вершины(число ее детей) и пометка о том. Следовательно, потеряла ли вершина <tex> x s_n \geqslant F_n</tex> ребенка после того, как она в последний раз сделалась чьим-либо потомком.}}