Изменения

|id=Лемма1|statement=Фибоначчиево дерево с вершиной степени Для всех целых <tex> k \geqslant 2</tex> содержит не менее <tex> F_k = 1 + \sum\limits_{i=0}^{k-2} F_i </tex> вершин, где <tex> F_k </tex> {{---}} <tex> k </tex> число Фибоначчи, определяемое формулой: <tex> F_0 F_k = F_1 \begin{cases} 0, & k = 0 \\ 1, & k = 1 \\quad F_n = F_{nk-1} + F_{nk-2}, & k \geqslant 2\end{cases} </tex>

Рассмотрим дерево степени при <tex> k = 2</tex>

Оно в худшем случае (удален ребенок со степенью <tex> k - F_2 = 1 + \sum\limits_{i=0}^0 F_i = 1 + 0 = 1 </tex>) содержит , что действительно верно.По индукции предполагаем, что <tex> F_{k-1} = 1 + F_1 + F_2 + \dots + F_sum\limits_{i=0}^{k-23} 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>